参考自 MOOC数据结构与算法Python版

目录

一、二叉查找树Binary Search Tree1.1 二叉查找树BST的性质：1.2 ADT Map的相关操作 二、 二叉搜索树的实现2.1 节点和链接结构2.2 BST.put方法2.2.1 put(key, val)2.2.2 _put(key, val, currentNode)2.2.3 用put实现索引赋值 2.3 BST.get方法2.3.1 get(self,key)和_get(self,key,currentNode)方法2.3.2 get实现索引和归属判断 2.3 迭代器2.4 BST.delete方法2.5 BST.remove方法2.5.1 没有子节点的情况 直接删除2.5.2 被删节点有1个子节点，将这个唯一的子节点上移，替换掉被删节点的位置2.5.3 被删节点有2个子节点，找到另一个合适的节点来替换被删节点2.5.4 TreeNode类：寻找后继节点 三、实例

一、二叉查找树Binary Search Tree

在ADT Map的实现方案中， 可以采用不同的数据结构和搜索算法来保存和查找Key， 前面已经实现了两个方案:

有序表数据结构+二分搜索算法散列表数据结构+散列及冲突解决算法

下面我们来试试用二叉查找树保存key，实现key的快速搜索。

1.1 二叉查找树BST的性质：

比父节点小的key都出现在左子树， 比父节点大的key都出现在右子树。 【例】按照70,31,93,94,14,23,73的顺序插入。 首先插入的70成为树根 31比70小，放到左子节点 93比70大，放到右子节点 94比93大，放到右子节点 14比31小，放到左子节点 23比14大，放到其右 73比93小，放到其左 注意：插入顺序不同， 生成的BST也不同

1.2 ADT Map的相关操作

函数含义Map()创建一个空映射put(key, val)将key-val关联对加入映射中，如果key已经存在，则将val替换旧关联值get(key)给定key，返回关联的数据值，如不存在，则返回Nonedel通过del map[key]的语句形式删除keyval关联len()返回映射中key-val关联的数目in通过key in map的语句形式，返回key是否存在于关联中，布尔值

二、 二叉搜索树的实现

2.1 节点和链接结构

需要用到BST和TreeNode两个类， BST的root成员引用根节点TreeNode 【代码实现】：

class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def lenth(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.val = val self.left = left self.right= right self.parent = parent def hasLeftChild(self): return self.left def hasRightChild(self): return self.right def isLeftChild(self): return self.parent and self.parent.left == self def isRightChild(self): return self.parent and self.parent.right== self def isRoot(self): return not self.parent def isLeaf(self): return not (self.right or self.left) def hasAnyChild(self): return self.left or self.right def hasBothChild(self): return self.left and self.right def replaceNodeData(self,key,value,lc,rc): self.key = key self.val =value self.left= lc self.right = rc if self.left: self.left.parent = self if self.right: self.right.parent = self

2.2 BST.put方法

2.2.1 put(key, val)

首先看BST是否为空，如果一个节点都没有，那么key成为根节点root；

【代码】

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

2.2.2 _put(key, val, currentNode)

否则，就调用一个递归函数_put(key, val,root)来放置key。

def _put(self, key, val,currentNode): #如果key比currentNode小，那么_put到左子树 if key < currentNode.key: #但如果没有左子树，那么key就成为左子节点 if currentNode.left: self._put(key,val,currentNode.left)#递归查找空左子树 else: currentNode.left = TreeNode(key,val,parent = currentNode) #如果key比currentNode大，那么_put到右子树 else: #但如果没有右子树，那么key就成为右子节点 if currentNode.right: self._put(key,val,currentNode.right) #递归右子树 else: currentNode.right = TreeNode(key,val,parent = currentNode)

2.2.3 用put实现索引赋值

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

BST.put图示 插入key=19， currentNode的变化过程（灰色）

从根节点17开始，比17大，分到右节点比35小，插入左节点比29小，插入左节点

2.3 BST.get方法

在树中找到key所在的节点取到payload

2.3.1 get(self,key)和_get(self,key,currentNode)方法

def get(self,key): if self.root: #判断是否是空树 res = self._get(key,self.root) #递归查找 if res: return res.val else: return None else: return None def _get(self,key,currentNode): if not currentNone: return None elif currentNode.key == key: return currentNone elif key < currentNode.key: #进入左子树查找 return self._get(key,currentNode.left) else: return self._get(key,currentNode.right)

2.3.2 get实现索引和归属判断

__getitem__特殊方法 实现val= myZipTree[‘PKU’]__contains__特殊方法 实现’PKU’ in myZipTree的归属判断运算符in

【代码】

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

2.3 迭代器

我们可以用for循环枚举字典中的所有key ADT Map也应该实现这样的迭代器功能特殊方法__iter__可以用来实现for迭代 BST类中的__iter__方法直接调用了TreeNode中的同名方法TreeNode类中的__iter__迭代器 迭代器函数中用了for迭代，实际上是递归函数yield是对每次迭代的返回值中序遍历的迭代 def __iter__(self): if self: if self.left: for elem in self.left: #其实是递归调用 yield elem yield self.key if self.right: for elem in self.right: yield elem

2.4 BST.delete方法

有增就有减， 最复杂的delete方法：用_get找到要删除的节点，然后调用remove来删除，找不到则提示错误 【代码】 def delete(self,key): if self.size > 1: nodeToRemove = self._get(key, self.root) if nodeToRemove: self.remove(nodeToRemove) 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 -= 1 else: raise KeyError("Erro, key not in tree") #实现del myZipTree['PKU']这样的语句操作 def __delitem__(self,key): self.delete(key)

在delete中， 最复杂的是找到key对应的节点之后的remove节点方法

2.5 BST.remove方法

从BST中remove一个节点， 还要求仍然保持BST的性质， 分以下3种情形：

这个节点没有子节点这个节点有1个子节点这个节点有2个子节点

2.5.1 没有子节点的情况 直接删除

if currentNode.isLeaf(): if currentNode == currentNode.parent.left: currentNode.parent.left = None else: currentNode.parent.right = None

2.5.2 被删节点有1个子节点，将这个唯一的子节点上移，替换掉被删节点的位置

但替换操作需要区分几种情况：

被删节点的子节点是左？还是右子节点？被删节点本身是其父节点的左？还是右子节点？被删节点本身就是根节点？ else: if currentNode.left: #被删的节点有一个左子节点 if currentNode.isLeftChild(): #被删的节点本身也是左子节点 currentNode.left.parent = currentNode.parent currentNode.parent.left = currentNode.left elif currentNode.isRightChild(): #右子节点删除 currentNode.left.parent = currentNode.parent currentNode.parent.right = currentNode.left else: #根节点删除 currentNode.replaceNodeData(currentNode.left.key, currentNode.left.val, currentNode.left.left, currentNode.left.right) else:#被删的节点有一个右子节点 if currentNode.isLeftChild(): currentNode.right.parent = currentNode.parent currentNode.parent.left = currentNode.left elif currentNode.isRightChild(): currentNode.right.parent = currentNode.parent currentNode.parent.right = currentNode.right else: currentNode.replaceNodeData(currentNode.right.key, currentNode.right.val, currentNode.right.left, currentNode.right.right)

2.5.3 被删节点有2个子节点，找到另一个合适的节点来替换被删节点

这个合适节点就是被删节点的下一个key值节点，即被删节点右子树中最小的那个，称为“后继”。可以肯定这个后继节点最多只有1个子节点（本身是叶节点，或仅有右子树）。将这个后继节点摘出来（也就是删除了），替换掉被删节点。

elif currentNode.hasBothChildren(): succ = currentNode.findSuccessor() succ.spliceOut() currentNode.key = succ.key currentNode.val = succ.val

2.5.4 TreeNode类：寻找后继节点

def findSuccessor(self): succ = None if self.right: succ = self.right.findMin() #找到右子节点的最小值 else: #这段代码可以不用 if self.parent: if self.isLeftChild(): succ = self.parent else: self.parent.right = None succ = self.parent.findSuccessor() self.parent.right = self return succ def findMin(self): current = self while current.left: current = current.left return current def spliceOut(self): if self.isLeaf(): if self.isLeftChild(): #如果是叶节点，摘出 self.parent.left = None else:#这段代码可以不用 self.parent.right = None elif self.hasAnyChildren(): if self.left:#这段代码可以不用 if self.isLeftChild(): self.parent.left = self.left else: self.parent.right = self.left self.left.aprent = self.parent else:#如果带有一个右子节点，摘出 if self.isLeftChild(): self.parent.left= self.right else:#这段代码可以不用 self.parent.right= self.right self.right.parent = self.parent

三、实例

【全部代码实现】

class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def lenth(self): return self.size def __len__(self): return self.size def __iter__(self): return self.root.__iter__() 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): # 如果key比currentNode小，那么_put到左子树 if key < currentNode.key: # 但如果没有左子树，那么key就成为左子节点 if currentNode.left: self._put(key, val, currentNode.left) # 递归查找空左子树 else: currentNode.left = TreeNode(key, val, parent=currentNode) # 如果key比currentNode大，那么_put到右子树 else: # 但如果没有右子树，那么key就成为右子节点 if currentNode.right: self._put(key, val, currentNode.right) # 递归右子树 else: currentNode.right = TreeNode(key, val, parent=currentNode) def __setitem__(self, k, v): self.put(k, v) def get(self, key): if self.root: # 判断是否是空树 res = self._get(key, self.root) # 递归查找 if res: return res.val 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.left) else: return self._get(key, currentNode.right) def __getitem__(self, key): return self.get(key) def __contains__(self, key): if self._get(key, self.root): return True else: return False def delete(self, key): if self.size > 1: nodeToRemove = self._get(key, self.root) if nodeToRemove: self.remove(nodeToRemove) 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 -= 1 else: raise KeyError("Erro, key not in tree") def __delitem__(self, key): self.delete(key) def remove(self, currentNode): if currentNode.isLeaf(): if currentNode == currentNode.parent.left: currentNode.parent.left = None else: currentNode.parent.right = None elif currentNode.hasBothChildren(): succ = currentNode.findSuccessor() succ.spliceOut() currentNode.key = succ.key currentNode.val = succ.val else: if currentNode.left: # 被删的节点有一个左子节点 if currentNode.isLeftChild(): # 被删的节点本身也是左子节点 currentNode.left.parent = currentNode.parent currentNode.parent.left = currentNode.left elif currentNode.isRightChild(): # 右子节点删除 currentNode.left.parent = currentNode.parent currentNode.parent.right = currentNode.left else: # 根节点删除 currentNode.replaceNodeData(currentNode.left.key, currentNode.left.val, currentNode.left.left, currentNode.left.right) else: # 被删的节点有一个右子节点 if currentNode.isLeftChild(): currentNode.right.parent = currentNode.parent currentNode.parent.left = currentNode.left elif currentNode.isRightChild(): currentNode.right.parent = currentNode.parent currentNode.parent.right = currentNode.right else: currentNode.replaceNodeData(currentNode.right.key, currentNode.right.val, currentNode.right.left, currentNode.right.right) def findSuccessor(self): succ = None if self.right: succ = self.right.findMin() # 找到右子节点的最小值 else: # 这段代码可以不用 if self.parent: if self.isLeftChild(): succ = self.parent else: self.parent.right = None succ = self.parent.findSuccessor() self.parent.right = self return succ def findMin(self): current = self while current.left: current = current.left return current def spliceOut(self): if self.isLeaf(): if self.isLeftChild(): # 如果是叶节点，摘出 self.parent.left = None else: # 这段代码可以不用 self.parent.right = None elif self.hasAnyChildren(): if self.left: # 这段代码可以不用 if self.isLeftChild(): self.parent.left = self.left else: self.parent.right = self.left self.left.aprent = self.parent else: # 如果带有一个右子节点，摘出 if self.isLeftChild(): self.parent.left = self.right else: # 这段代码可以不用 self.parent.right = self.right self.right.parent = self.parent class TreeNode: def __init__(self, key, val, left=None, right=None, parent=None): self.key = key self.val = val self.left = left self.right = right self.parent = parent def hasLeftChild(self): return self.left def hasRightChild(self): return self.right def isLeftChild(self): return self.parent and self.parent.left == self def isRightChild(self): return self.parent and self.parent.right == self def isRoot(self): return not self.parent def isLeaf(self): return not (self.right or self.left) def hasAnyChild(self): return self.left or self.right def hasBothChildren(self): return self.left and self.right def replaceNodeData(self, key, value, lc, rc): self.key = key self.payload = value self.left = lc self.right = rc if self.left: self.left.parent = self if self.right: self.right.parent = self def __iter__(self): if self: if self.left: # for elem in self.left: yield elem yield self.key if self.right: for elem in self.right: yield elem mytree = BinarySearchTree() mytree[3] = "jusitin" mytree[4] = "bilish" mytree[7] = "leslie" mytree[8] = "eason" print(3 in mytree) print(mytree[7]) del mytree[3] print(mytree[2]) for key in mytree: print(key, mytree[key]) ''' True leslie None 4 bilish 7 leslie 8 eason '''