背景知識：
##############################################################
運(yùn)算符重載：
在類中調(diào)用一個符號時，這個符號是有特定的函數(shù)名稱的，我們可以在類中對此函數(shù)進(jìn)行定義，那么在遇到這個符號調(diào)用時，python會自動調(diào)用這個方法。
比如，進(jìn)行索引運(yùn)算時，出現(xiàn)符號“[ ]”，就會自動調(diào)用 getitem方法，返回的就是index的平方。

class Indexer(object):
        def __getitem__(self,index):
                return index ** 2
X = Indexer()
X[2]

同樣，setitem代表的運(yùn)算操作，就是對item進(jìn)行賦值操作。有點(diǎn)類似于字典，只要類中定義了這個方法，那么這個類對象就可以進(jìn)行這個操作，通過重載的運(yùn)算符實(shí)現(xiàn)。

##############################################################

一、二叉搜索樹的應(yīng)用

在二叉搜索樹中，左子節(jié)點(diǎn)總是小于或等于根節(jié)點(diǎn)，而右子節(jié)點(diǎn)總是大于或等于根節(jié)點(diǎn)。我們可以平均在O(logn)的時間內(nèi)根據(jù)數(shù)值在二叉搜索樹中找到一個節(jié)點(diǎn)。

可見，二叉搜索樹，就是搜索數(shù)據(jù)，根據(jù)key找到value。

我們之前已經(jīng)學(xué)習(xí)過了兩種ADT MAP的實(shí)現(xiàn)方式，一種是列表的二分查找，一種是散列表。

同樣是搜索，根據(jù)鍵key來搜索值value。這里我們將要學(xué)習(xí)第三種方式：二叉搜索樹。

注意，二叉搜索樹也是一種數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)跟字典非常相似，所以也是三步走：

• 二叉搜索樹的操作
• 二叉搜索樹的結(jié)構(gòu)
• 二叉搜索樹的操作的代碼實(shí)現(xiàn)

二、二叉搜索樹的操作

• Map() 建立一個新的空map。
• put(key,val) 在map中增加了一個新的鍵值對。如果這個鍵已經(jīng)在這個map中了， 那么就用新的數(shù)據(jù)來代替舊的數(shù)據(jù)。
• get(key) 提供一個鍵，返回map中保存的數(shù)據(jù)，否則返回None。
• del 用del map[key]這種形式從map中刪除鍵值對。
• len() 返回map中保存的鍵值對的數(shù)目.
• in 對給定的鍵是否存在map中進(jìn)行判斷，如果所給的鍵在map中，返回True

三、二叉搜索樹的結(jié)構(gòu)

一個二叉搜索樹，如果左子樹中鍵值Key都小于父節(jié)點(diǎn)，而右子樹中鍵值Key都大于父節(jié)點(diǎn)，我們將這種樹稱為BST搜索樹。

四、二叉搜索樹的實(shí)現(xiàn)

實(shí)現(xiàn)二叉搜索樹，我們將使用節(jié)點(diǎn)和引用方法，這類似于一個我們用來實(shí)現(xiàn)鏈表和表達(dá)式樹的過程。但是，因?yàn)槲覀儽仨毮軌騽?chuàng)建和使用一個空二叉搜索樹，所以我們的實(shí)現(xiàn)將使用兩個類： 第一個類我們稱為BinarySearchTree，第二個類我們稱之為TreeNode。

這兩個類的實(shí)現(xiàn)代碼如下：

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__()

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

4.1、put()方法

對put方法的解讀

• 如果根節(jié)點(diǎn)存在，則遞歸調(diào)用_put方法
• 如果根節(jié)點(diǎn)不存在，則直接調(diào)用treenode類，作為根節(jié)點(diǎn)。
  由構(gòu)造函數(shù)添加一個樹節(jié)點(diǎn)，并且會輸入此節(jié)點(diǎn)的key與val。

對_put方法的解釋：

• 如果新的值小于當(dāng)前節(jié)點(diǎn)，那就對左子樹進(jìn)行搜索
  1、如果有左子樹，那么再遞歸調(diào)用_put，直到新節(jié)點(diǎn)放到正確的位置為止。
  2、如果沒有左子樹，則直接將點(diǎn)調(diào)用treenode，并且賦予key和val。
• 如果新的值大于當(dāng)前節(jié)點(diǎn)，那么就對右子樹進(jìn)行搜索
  下面執(zhí)行與上述1、2相同的步驟

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)

用運(yùn)算符重載的方法，使類對象可以進(jìn)行類似于字典的賦值操作。

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

隨著put方法的定義，我們可以很容易地重載[ ]作為操作符，通過添加 setitem的方法來調(diào)用put方法。

定義這個方法以后，這使我們能夠編寫比如myZTiptree['plymouth’] = 55446一樣的python語句，這看上去就像Python字典。

但是上面的put方法還是有一個bug。
bug是因?yàn)?，若是出現(xiàn)重復(fù)的key，那么在_put中，key就不滿足小于當(dāng)前的key，而是else條件語句的大于等于當(dāng)前節(jié)點(diǎn)，這樣新的鍵值對就會被添加在當(dāng)前節(jié)點(diǎn)的右子樹上。這樣在根據(jù)key查找數(shù)據(jù)是，永遠(yuǎn)只會找到最上面的key對應(yīng)的value。因此正確的做法應(yīng)該是有相同的key時，應(yīng)該去覆蓋這個key對應(yīng)的value。

4.2 、get（）方法

樹已經(jīng)被構(gòu)建成功。接下來任務(wù)是給定鍵，實(shí)現(xiàn)對值的檢索。（二叉搜索樹的意義）

get方法比put更容易，因?yàn)樗f歸地搜索子樹，直到發(fā)現(xiàn)無匹配的葉節(jié)點(diǎn)或找到一個匹配的鍵。當(dāng)一個匹配的鍵被發(fā)現(xiàn)后，存儲在節(jié)點(diǎn)的值被返回。

get方法

• 若根節(jié)點(diǎn)為空，則返回None，不為空，則遞歸調(diào)用_get進(jìn)行查找操作。若找到key，則返回val。

_get方法
遞歸調(diào)用自身，若找到了key鍵，就返回對應(yīng)的val，找不到就返回None。

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)

通過實(shí)施getitem方法，我們可以寫若干Python語句，使它們看起來就像我們訪問字典一樣，而事實(shí)上我們只是在用一個二叉搜索樹，例如Z = myziptree [ 'fargo’]。如你可以看到，所有的getitem方法都是調(diào)用get。

調(diào)用get函數(shù)時，我們可以為BinarySearchTree寫contains方法從而能夠使用操作符in。contains會簡單的調(diào)用get，當(dāng)get返回值的時候就返回True，如果get返回None就返回False。

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

4.3 、刪除節(jié)點(diǎn)

刪除節(jié)點(diǎn)的步驟：

• 1、找到要刪除的搜索樹的節(jié)點(diǎn)。
  a、如果樹有一個以上的節(jié)點(diǎn)，我們使用_get方法搜索找到需要刪除的TreeNode;
  b、如果樹只有一個節(jié)點(diǎn)，這意味著我們要移除樹的根，但是我們?nèi)匀槐仨殭z查以確保根的鍵是否匹配要刪除的鍵。
• 2、在以上兩種情況下，如果未發(fā)現(xiàn)鍵值，del操作符就會報錯。
  以下是刪除節(jié)點(diǎn)的主函數(shù)的代碼：

def delete(self,key):
   if self.size > 1:
      nodeToRemove = self._get(key,self.root)
      if nodeToRemove:
          self.remove(nodeToRemove)
          self.size = self.size-1
      else:
          raise KeyError('Error, key not in tree')
   elif self.size == 1 and self.root.key == key:
      self.root = None
      self.size = self.size - 1
   else:
      raise KeyError('Error, key not in tree')

def __delitem__(self,key):
    self.delete(key)

而對于其中的nodeToRemove函數(shù)的具體操作，因?yàn)橐獎h除的節(jié)點(diǎn)有三種不同的情況，因此對應(yīng)的操作也不盡相同。
下面是，要刪除的節(jié)點(diǎn)要有的三種情況：

• 1、要刪除的節(jié)點(diǎn)沒有子樹
• 2、要刪除的節(jié)點(diǎn)只有左子樹（或只有右子樹）
• 3、要刪除的節(jié)點(diǎn)，左子樹和右子樹都有。

接下來對于三種情況再做具體的分析：

第一種情況：要刪除的節(jié)點(diǎn)沒有子樹

第一種情況是簡單的。如果當(dāng)前節(jié)點(diǎn)沒有子樹，所有我們需要做的是刪除該節(jié)點(diǎn)并把指向該節(jié)點(diǎn)的引用移動給其父節(jié)點(diǎn)。

if currentNode.isLeaf():
    if currentNode == currentNode.parent.leftChild:
        currentNode.parent.leftChild = None
    else:
        currentNode.parent.rightChild = None

例子：

二叉搜索樹是通過引用來實(shí)現(xiàn)的，所以刪除一個節(jié)點(diǎn)，不能只是單純的刪除數(shù)據(jù)就行了，還要對引用做出修改。
代碼解釋，若當(dāng)前節(jié)是葉節(jié)點(diǎn)，如果是父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么就把父節(jié)點(diǎn)的左子節(jié)點(diǎn)引用改為None。同理于右子節(jié)點(diǎn)。

第二種情況：要刪除的節(jié)點(diǎn)只有左子樹（或只有右子樹）

else: # this node has one child
   if currentNode.hasLeftChild():
      if currentNode.isLeftChild():
          currentNode.leftChild.parent = currentNode.parent
          currentNode.parent.leftChild = currentNode.leftChild
      elif currentNode.isRightChild():
          currentNode.leftChild.parent = currentNode.parent
          currentNode.parent.rightChild = currentNode.leftChild
      else:
          currentNode.replaceNodeData(currentNode.leftChild.key,
                             currentNode.leftChild.payload,
                             currentNode.leftChild.leftChild,
                             currentNode.leftChild.rightChild)
   else:
      if currentNode.isLeftChild():
          currentNode.rightChild.parent = currentNode.parent
          currentNode.parent.leftChild = currentNode.rightChild
      elif currentNode.isRightChild():
          currentNode.rightChild.parent = currentNode.parent
          currentNode.parent.rightChild = currentNode.rightChild
      else:
          currentNode.replaceNodeData(currentNode.rightChild.key,
                             currentNode.rightChild.payload,
                             currentNode.rightChild.leftChild,
                             currentNode.rightChild.rightChild)

例子（當(dāng)前節(jié)點(diǎn)是右節(jié)點(diǎn)，并且只有右子樹的情況下）：

第三種情況：要刪除的節(jié)點(diǎn)有左、右兩個節(jié)點(diǎn)

如果一個節(jié)點(diǎn)有兩個子節(jié)點(diǎn)，我們不可能簡單地其中一個作為提升至父節(jié)點(diǎn)的位置，這就需要尋找一個節(jié)點(diǎn)，用來代替一個計劃刪除的節(jié)點(diǎn)，我們需要的這個節(jié)點(diǎn)，需要保存現(xiàn)有的左、右子樹以及二叉搜索樹關(guān)系。我們稱這個節(jié)點(diǎn)為繼任者。

如何找到這個繼任者呢？
按照上面所說，有一個原則：需要保存現(xiàn)有的左、右子樹以及二叉搜索樹關(guān)系。

那么怎樣能保證上述原則呢？
我們要找到，與當(dāng)前節(jié)點(diǎn)相比，key值只是稍微大一點(diǎn)點(diǎn)的節(jié)點(diǎn)。再具體些，就是，比如一共有10個key，當(dāng)前節(jié)點(diǎn)的key第5大，那么刪除掉第5大的節(jié)點(diǎn)以后，只有用第4大的節(jié)點(diǎn)代替當(dāng)前節(jié)點(diǎn)，才能保證二叉搜索樹的各節(jié)點(diǎn)關(guān)系不變。

比如例子中的5：

上面說的有些籠統(tǒng)，具體的怎么去確定這個繼任者呢？
有三種情況需要考慮：

• 1. 如果節(jié)點(diǎn)有右子節(jié)點(diǎn)，那么繼任者是在右子樹中最小的鍵。
• 2. 如果節(jié)點(diǎn)沒有右子節(jié)點(diǎn)，是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么父節(jié)點(diǎn)是繼任者。
• 3. 如果節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)，而本身無右子節(jié)點(diǎn)，那么該節(jié)點(diǎn)的繼任者是其父節(jié)點(diǎn)的繼任者，不包括這個節(jié)點(diǎn)。

其中比較常用的是第三種情況中的第一種情況。
刪除第三種情況的節(jié)點(diǎn)（有兩個子節(jié)點(diǎn)）的代碼分為兩步：

• 1、找到繼任者（findSuccessor和findMin）
• 2、根據(jù)找到點(diǎn)以后，確認(rèn)繼任者的幾種情況（繼任者節(jié)點(diǎn)是否具有子節(jié)點(diǎn)，有幾個子節(jié)點(diǎn)等）再進(jìn)行相應(yīng)的操作。spliceOut

elif currentNode.hasBothChildren(): #interior
        succ = currentNode.findSuccessor()
        succ.spliceOut()
        currentNode.key = succ.key
        currentNode.payload = succ.payload

上述代碼中用到的方法的代碼：

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        succ = self.rightChild.findMin()
    else:
        if self.parent:
               if self.isLeftChild():
                   succ = self.parent
               else:
                   self.parent.rightChild = None
                   succ = self.parent.findSuccessor()
                   self.parent.rightChild = self
    return succ

def findMin(self):
    current = self
    while current.hasLeftChild():
        current = current.leftChild
    return current

def spliceOut(self):
    if self.isLeaf():
        if self.isLeftChild():
               self.parent.leftChild = None
        else:
               self.parent.rightChild = None
    elif self.hasAnyChildren():
        if self.hasLeftChild():
               if self.isLeftChild():
                  self.parent.leftChild = self.leftChild
               else:
                  self.parent.rightChild = self.leftChild
               self.leftChild.parent = self.parent
        else:
               if self.isLeftChild():
                  self.parent.leftChild = self.rightChild
               else:
                  self.parent.rightChild = self.rightChild
               self.rightChild.parent = self.parent

4.4 、iter:按順序簡單地遍歷樹上所有的鍵值。

最后的一個接口方法，就是按順序簡單的遍歷書上所有的鍵值。

這是我們用字典所做能的事，為什么不在樹也實(shí)現(xiàn)呢?我們已經(jīng)知道如何使用中序遍歷二叉樹，然而，寫一個迭代器需要更多一點(diǎn)的工作，因?yàn)槊看握{(diào)用迭代器時，一個迭代器只返回一個節(jié)點(diǎn)。

Python提供了一個非常強(qiáng)大的函數(shù)yield，使用時創(chuàng)建一個迭代器。yield和return相似，它也返回一個值給調(diào)用者。yield也有額外的步驟來記住函數(shù)運(yùn)行目前的狀態(tài)，以便下次調(diào)用函數(shù)時，繼續(xù)從當(dāng)前狀態(tài)執(zhí)行。創(chuàng)建可迭代對象的函數(shù)被成為生成器。

二叉樹的中序迭代器代碼如下所示。仔細(xì)看看這個代碼：乍一看，你可能會認(rèn)為代碼是非遞歸的。但是請記住，iter重寫for x in的操作符來實(shí)現(xiàn)迭代，所以它確實(shí)是遞歸!因?yàn)樗菍reeNode進(jìn)行遞歸，iter_在TreeNode類中定義。

def __iter__(self):
   if self:
      if self.hasLeftChild():
             for elem in self.leftChiLd:
                yield elem
      yield self.key
      if self.hasRightChild():
             for elem in self.rightChild:
                yield elem

至此，基本的二叉搜索樹的結(jié)構(gòu)與性質(zhì)已經(jīng)實(shí)現(xiàn)了。