摘要：圖展示了二叉搜索樹(shù)的這一特性，顯示的鍵沒(méi)有關(guān)聯(lián)任何的值。因?yàn)槲覀儽仨毮軌騽?chuàng)建和使用一個(gè)空的二叉搜索樹(shù)，所以我們將使用兩個(gè)類來(lái)實(shí)現(xiàn)，第一個(gè)類我們稱之為，第二個(gè)類我們稱之為。圖說(shuō)明了將新節(jié)點(diǎn)插入到一個(gè)二叉搜索樹(shù)的過(guò)程。

我們已經(jīng)知道了在一個(gè)集合中獲取鍵值對(duì)的兩種不同的方法?；貞浺幌逻@些集合是如何實(shí)現(xiàn)ADT（抽象數(shù)據(jù)類型）MAP的。我們討論兩種ADT MAP的實(shí)現(xiàn)方式，基于列表的二分查找和哈希表。在這一節(jié)中，我們將要學(xué)習(xí)二叉搜索樹(shù)，這是另一種鍵指向值的Map集合，在這種情況下我們不用考慮元素在樹(shù)中的實(shí)際位置，但要知道使用二叉樹(shù)來(lái)搜索更有效率。

在我們研究這種實(shí)現(xiàn)方式之前，讓我們回顧一下ADT MAP提供的接口。我們會(huì)注意到，這種接口和Python的字典非常相似。
Map() 創(chuàng)建了一個(gè)新的空Map集合。
put(key,val) 在Map中增加了一個(gè)新的鍵值對(duì)。如果這個(gè)鍵已經(jīng)在這個(gè)Map中了，那么就用新的值來(lái)代替舊的值。
get(key) 提供一個(gè)鍵，返回Map中保存的數(shù)據(jù)，或者返回None。
del 使用del map[key]這條語(yǔ)句從Map中刪除鍵值對(duì)。
len() 返回Map中保存的鍵值對(duì)的數(shù)目
in 如果所給的鍵在Map中，使用key in map這條語(yǔ)句返回True。

一個(gè)二叉搜索樹(shù)，如果具有左子樹(shù)中的鍵值都小于父節(jié)點(diǎn)，而右子樹(shù)中的鍵值都大于父節(jié)點(diǎn)的屬性，我們將這種樹(shù)稱為BST搜索樹(shù)。如之前所述的，當(dāng)我們實(shí)現(xiàn)Map時(shí)，BST方法將引導(dǎo)我們實(shí)現(xiàn)這一點(diǎn)。圖 1 展示了二叉搜索樹(shù)的這一特性，顯示的鍵沒(méi)有關(guān)聯(lián)任何的值。注意這種屬性適用于每個(gè)父節(jié)點(diǎn)和子節(jié)點(diǎn)。所有在左子樹(shù)的鍵值都小于根節(jié)點(diǎn)的鍵值，所有右子樹(shù)的鍵值都大于根節(jié)點(diǎn)的鍵值。

圖 1：一個(gè)簡(jiǎn)單的二叉搜索樹(shù)

現(xiàn)在你知道什么是二叉搜索樹(shù)了，我們?cè)賮?lái)看如何構(gòu)造一個(gè)二叉搜索樹(shù)，我們?cè)谒阉鳂?shù)中按圖 1 顯示的節(jié)點(diǎn)順序插入這些鍵值，圖 1 搜索樹(shù)存在的節(jié)點(diǎn)：70,31,93,94,14,23,73。因?yàn)?70 是第一個(gè)被插入到樹(shù)的值，它是根節(jié)點(diǎn)。接下來(lái)，31 小于 70，因此是 70 的左子樹(shù)。接下來(lái)，93 大于 70，因此是 70 的右子樹(shù)。我們現(xiàn)在填充了該樹(shù)的兩層，所以下一個(gè)鍵值，將會(huì)是 31 或者 93 的左子樹(shù)或右子樹(shù)。由于 94 大于 70 和 93，就變成了 93 的右子樹(shù)。同樣，14 小于 70 和 31，因此成為了 31 的左子樹(shù)。23 也小于 31，因此必須是 31 的左子樹(shù)。然而，它大于 14，所以是 14 的右子樹(shù)。

為了實(shí)現(xiàn)二叉搜索樹(shù)，我們將使用節(jié)點(diǎn)和引用的方法，這類似于我們實(shí)現(xiàn)鏈表和表達(dá)式樹(shù)的過(guò)程。因?yàn)槲覀儽仨毮軌騽?chuàng)建和使用一個(gè)空的二叉搜索樹(shù)，所以我們將使用兩個(gè)類來(lái)實(shí)現(xiàn)，第一個(gè)類我們稱之為 BinarySearchTree，第二個(gè)類我們稱之為TreeNode。BinarySearchTree類有一個(gè)TreeNode類的引用作為二叉搜索樹(shù)的根，在大多數(shù)情況下，外部類定義的外部方法只需檢查樹(shù)是否為空，如果在樹(shù)上有節(jié)點(diǎn)，要求BinarySearchTree類中含有私有方法把根定義為參數(shù)。在這種情況下，如果樹(shù)是空的或者我們想刪除樹(shù)的根，我們就必須采用特殊操作。BinarySearchTree類的構(gòu)造函數(shù)以及一些其他函數(shù)的代碼如Listing 1 所示。

Listing 1

class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

TreeNode類提供了許多輔助函數(shù)，使得BinarySearchTree類的方法更容易實(shí)現(xiàn)過(guò)程。如Listing 2 所示，一個(gè)樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)，是由這些輔助函數(shù)實(shí)現(xiàn)的。正如你看到的那樣，這些輔助函數(shù)可以根據(jù)自己的位置來(lái)劃分一個(gè)節(jié)點(diǎn)作為左或右孩子和該子節(jié)點(diǎn)的類型。TreeNode類非常清楚地跟蹤了每個(gè)父節(jié)點(diǎn)的屬性。當(dāng)我們討論刪除操作的實(shí)現(xiàn)時(shí)，你將明白為什么這很重要。

對(duì)于Listing 2 中的TreeNode實(shí)現(xiàn)，另一個(gè)有趣的地方是，我們使用Python的可選參數(shù)。可選的參數(shù)很容易讓我們?cè)趲追N不同的情況下創(chuàng)建一個(gè)樹(shù)節(jié)點(diǎn)，有時(shí)我們想創(chuàng)建一個(gè)新的樹(shù)節(jié)點(diǎn)，即使我們已經(jīng)有了父節(jié)點(diǎn)和子節(jié)點(diǎn)。與現(xiàn)有的父節(jié)點(diǎn)和子節(jié)點(diǎn)一樣，我們可以通過(guò)父節(jié)點(diǎn)和子節(jié)點(diǎn)作為參數(shù)。有時(shí)我們也會(huì)創(chuàng)建一個(gè)包含鍵值對(duì)的樹(shù)，我們不會(huì)傳遞父節(jié)點(diǎn)或子節(jié)點(diǎn)的任何參數(shù)。在這種情況下，我們將使用可選參數(shù)的默認(rèn)值。

Listing 2

class TreeNode:
   def __init__(self,key,val,left=None,right=None,
                                       parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self

現(xiàn)在，我們擁有了BinarySearchTree和TreeNode類，是時(shí)候?qū)懸粋€(gè)put方法使我們能夠建立二叉搜索樹(shù)。put方法是BinarySearchTree類的一個(gè)方法。這個(gè)方法將檢查這棵樹(shù)是否已經(jīng)有根。如果沒(méi)有，我們將創(chuàng)建一個(gè)新的樹(shù)節(jié)點(diǎn)并把它設(shè)置為樹(shù)的根。如果已經(jīng)有一個(gè)根節(jié)點(diǎn)，我們就調(diào)用它自己，進(jìn)行遞歸，用輔助函數(shù)_put按下列算法來(lái)搜索樹(shù)：

從樹(shù)的根節(jié)點(diǎn)開(kāi)始，通過(guò)搜索二叉樹(shù)來(lái)比較新的鍵值和當(dāng)前節(jié)點(diǎn)的鍵值，如果新的鍵值小于當(dāng)前節(jié)點(diǎn)，則搜索左子樹(shù)。如果新的關(guān)鍵大于當(dāng)前節(jié)點(diǎn)，則搜索右子樹(shù)。

當(dāng)搜索不到左（或右）子樹(shù)，我們?cè)跇?shù)中所處的位置就是設(shè)置新節(jié)點(diǎn)的位置。

向樹(shù)中添加一個(gè)節(jié)點(diǎn)，創(chuàng)建一個(gè)新的TreeNode對(duì)象并在這個(gè)點(diǎn)的上一個(gè)節(jié)點(diǎn)中插入這個(gè)對(duì)象。

Listing 3 顯示了在樹(shù)中插入新節(jié)點(diǎn)的Python代碼。_put函數(shù)要按照上述的步驟編寫遞歸算法。注意，當(dāng)一個(gè)新的子樹(shù)插入時(shí)，當(dāng)前節(jié)點(diǎn)（CurrentNode）作為父節(jié)點(diǎn)傳遞給新的樹(shù)。

我們執(zhí)行插入的一個(gè)重要問(wèn)題是重復(fù)的鍵值不能被正確的處理，我們的樹(shù)實(shí)現(xiàn)了鍵值的復(fù)制，它將在右子樹(shù)創(chuàng)建一個(gè)與原來(lái)節(jié)點(diǎn)鍵值相同的新節(jié)點(diǎn)。這樣做的后果是，新的節(jié)點(diǎn)將不會(huì)在搜索過(guò)程中被發(fā)現(xiàn)。我們用一個(gè)更好的方式來(lái)處理插入重復(fù)的鍵值，舊的值被新鍵關(guān)聯(lián)的值替換。我們把這個(gè)錯(cuò)誤的修復(fù)，作為練習(xí)留給你。

Listing 3

def put(self,key,val):
    if self.root:
        self._put(key,val,self.root)
    else:
        self.root = TreeNode(key,val)
    self.size = self.size + 1

def _put(self,key,val,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
               self._put(key,val,currentNode.leftChild)
        else:
               currentNode.leftChild = TreeNode(key,val,parent=currentNode)
    else:
        if currentNode.hasRightChild():
               self._put(key,val,currentNode.rightChild)
        else:
               currentNode.rightChild = TreeNode(key,val,parent=currentNode)

隨著put方法的實(shí)現(xiàn)，我們可以很容易地通過(guò)__setitem__方法重載[]作為操作符來(lái)調(diào)用put方法（參見(jiàn)Listing 4）。這使我們能夠編寫像myZipTree["Plymouth"] = 55446一樣的python語(yǔ)句，這看上去就像Python的字典。

Listing 4

def __setitem__(self,k,v):
    self.put(k,v)

圖 2 說(shuō)明了將新節(jié)點(diǎn)插入到一個(gè)二叉搜索樹(shù)的過(guò)程?；疑?jié)點(diǎn)顯示了插入過(guò)程中遍歷樹(shù)節(jié)點(diǎn)順序。

圖 2: 插入一個(gè)鍵值 = 19 的節(jié)點(diǎn)

一旦樹(shù)被構(gòu)造，接下來(lái)的任務(wù)就是為一個(gè)給定的鍵值實(shí)現(xiàn)檢索。get方法比put方法更容易因?yàn)樗恍柽f歸搜索樹(shù)，直到發(fā)現(xiàn)不匹配的葉節(jié)點(diǎn)或找到一個(gè)匹配的鍵值。當(dāng)找到一個(gè)匹配的鍵值后，就會(huì)返回節(jié)點(diǎn)中的值。

Listing 5 顯示了get，_get和__getitem__的代碼。用_get方法搜索的代碼與put方法具有相同的選擇左或右子樹(shù)的邏輯。請(qǐng)注意，_get方法返回TreeNode中get的值，_get就可以作為一個(gè)靈活有效的方式，為BinarySearchTree的其他可能需要使用TreeNode里的數(shù)據(jù)的方法提供參數(shù)。

通過(guò)實(shí)現(xiàn)__getitem__方法，我們可以寫一個(gè)看起來(lái)就像我們?cè)L問(wèn)字典一樣的Python語(yǔ)句，而事實(shí)上我們只是操作二叉搜索樹(shù)，例如Z = myziptree ["fargo"]。正如你所看到的，__getitem__方法都是在調(diào)用get。

Listing 5

def get(self,key):
    if self.root:
        res = self._get(key,self.root)
        if res:
               return res.payload
        else:
               return None
    else:
        return None

def _get(self,key,currentNode):
    if not currentNode:
        return None
    elif currentNode.key == key:
        return currentNode
    elif key < currentNode.key:
        return self._get(key,currentNode.leftChild)
    else:
        return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
    return self.get(key)

使用get，我們可以通過(guò)寫一個(gè)BinarySearchTree的__contains__方法來(lái)實(shí)現(xiàn)操作，__contains__方法簡(jiǎn)單地調(diào)用了get方法，如果它有返回值就返回True，如果它是None就返回False。如Listing 6 所示。

Listing 6

def __contains__(self,key):
    if self._get(key,self.root):
        return True
    else:
        return False

回顧一下__contains__重載的操作符，這允許我們寫這樣的語(yǔ)句：

if "Northfield" in myZipTree:
    print("oom ya ya")