對(duì)于二叉查找樹的每個(gè)節(jié)點(diǎn)Node，它的左子樹中所有的關(guān)鍵字都小于Node的關(guān)鍵字，而右子樹中的所有關(guān)鍵字都大于Node的關(guān)鍵字。
二叉查找樹的平均深度是O(log N)。
1.初始化
class BinarySearchTree(object): def __init__(self,key): self.key=key self.left=None self.right=None
2.Find
def find(self,x): if x==self.key: return self elif x<self.key and self.left: return self.left.find(x) elif x>self.key and self.right: return self.right.find(x) else: return None
3.FindMin和FindMax
分別返回樹中的最小元素與最大元素的位置。FindMin，從根開始并且只要有左兒子就向左進(jìn)行查找，終止點(diǎn)是最小元素。FindMax則向右進(jìn)行。
def findMin(self): if self.left: return self.left.findMin() else: return self def findMax(self): tree=self if tree: while tree.right: tree=tree.right return tree
4.Insert
為了將x插入到樹Tree中，先用find查找，如果找到x，則什么也不做。否則，將x插入到遍歷路徑的最后一點(diǎn)。
來自《PRoblem Solving with Algorithms and Data Structures》的圖片：
def insert(self,x): if x<self.key: if self.left: self.left.insert(x) else: tree=BinarySearchTree(x) self.left=tree elif x>self.key: if self.right: self.right.insert(x) else: tree=BinarySearchTree(x) self.right=tree
5.Delete
刪除某節(jié)點(diǎn)有3種情況：
5.1 如果節(jié)點(diǎn)是一片樹葉，那么可以立即被刪除。
來自《Problem Solving with Algorithms and Data Structures》的圖片：
5.2 如果節(jié)點(diǎn)只有一個(gè)兒子，則將此節(jié)點(diǎn)parent的指針指向此節(jié)點(diǎn)的兒子，然后刪除。
來自《Problem Solving with Algorithms and Data Structures》的圖片：
5.3 如果節(jié)點(diǎn)有兩個(gè)兒子，則將其右子樹的最小數(shù)據(jù)代替此節(jié)點(diǎn)的數(shù)據(jù)，并將其右子樹的最小數(shù)據(jù)（不可能有左兒子，只有一個(gè)右兒子）刪除。
來自《Problem Solving with Algorithms and Data Structures》的圖片：
def delete(self,x): if self.find(x): if x<self.key: self.left=self.left.delete(x) return self elif x>self.key: self.right=self.right.delete(x) return self elif self.left and self.right: key=self.right.findMin().key self.key=key self.right=self.right.delete(key) return self else: if self.left: return self.left else: return self.right else: return self
全部代碼
class BinarySearchTree(object): def __init__(self,key): self.key=key self.left=None self.right=None def find(self,x): if x==self.key: return self elif x<self.key and self.left: return self.left.find(x) elif x>self.key and self.right: return self.right.find(x) else: return None def findMin(self): if self.left: return self.left.findMin() else: return self def findMax(self): tree=self if tree: while tree.right: tree=tree.right return tree def insert(self,x): if x<self.key: if self.left: self.left.insert(x) else: tree=BinarySearchTree(x) self.left=tree elif x>self.key: if self.right: self.right.insert(x) else: tree=BinarySearchTree(x) self.right=tree def delete(self,x): if self.find(x): if x<self.key: self.left=self.left.delete(x) return self elif x>self.key: self.right=self.right.delete(x) return self elif self.left and self.right: key=self.right.findMin().key self.key=key self.right=self.right.delete(key) return self else: if self.left: return self.left else: return self.right else: return self
上述寫法的缺點(diǎn)是很難處理空樹的情況。
另一種類似于鏈表的寫法
class TreeNode(object): def __init__(self,key,left=None,right=None,parent=None): self.key=key 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==selfclass BSTree(object): def __init__(self): self.root=None self.size=0 def length(self): return self.size def insert(self,x): node=TreeNode(x) if not self.root: self.root=node self.size+=1 else: currentNode=self.root while True: if x<currentNode.key: if currentNode.left: currentNode=currentNode.left else: currentNode.left=node node.parent=currentNode self.size+=1 break elif x>currentNode.key: if currentNode.right: currentNode=currentNode.right else: currentNode.right=node node.parent=currentNode self.size+=1 break else: break def find(self,key): if self.root: res=self._find(key,self.root) if res: return res else: return None else: return None def _find(self,key,node): if not node: return None elif node.key==key: return node elif key<node.key: return self._find(key,node.left) else: return self._find(key,node.right) def findMin(self): if self.root: current=self.root while current.left: current=current.left return current else: return None def _findMin(self,node): if node: current=node while current.left: current=current.left return current def findMax(self): if self.root: current=self.root while current.right: current=current.right return current else: return None def delete(self,key): if self.size>1: nodeToRemove=self.find(key) 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('Error, key not in tree') def remove(self,node): if not node.left and not node.right: #node為樹葉 if node==node.parent.left: node.parent.left=None else: node.parent.right=None elif node.left and node.right: #有兩個(gè)兒子 minNode=self._findMin(node.right) node.key=minNode.key self.remove(minNode) else: #有一個(gè)兒子 if node.hasLeftChild(): if node.isLeftChild(): node.left.parent=node.parent node.parent.left=node.left elif node.isRightChild(): node.left.parent=node.parent node.parent.right=node.left else: #node為根 self.root=node.left node.left.parent=None node.left=None else: if node.isLeftChild(): node.right.parent=node.parent node.parent.left=node.right elif node.isRightChild(): node.right.parent=node.parent node.parent.right=node.right else: #node為根 self.root=node.right node.right.parent=None node.right=None
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
