chapter 12-二叉搜索树

  1 class TreeNode():
  2     def __init__(self,key,p=None,left=None,right=None):
  3         self.key=key
  4         self.p=p
  5         self.left=left
  6         self.right=right
  7 
  8 class BinarySearchTree():
  9     #中序遍历
 10     def inorderWalk(self,x):
 11         if x!=None:
 12             self.inorderWalk(x.left)
 13             print(x.key,end=" ")
 14             self.inorderWalk(x.right)
 15     #查找给定节点
 16     def treeSearh(self,x,k):
 17         if x==None or x.key==k:
 18             return x
 19         if k<x.key:
 20             return self.treeSearh(x.left,k)
 21         else: return self.treeSearh(x.right,k)
 22     #最小关键元素
 23     def treeMinimum(self,x):
 24         while x.left!=None:
 25             x=x.left
 26         return x
 27     #最大关键元素
 28     def treeMaximum(self,x):
 29         while x.right!=None:
 30             x=x.right
 31         return x
 32     #后继节点
 33     def treeSuccessor(self,x):
 34         if x.right!=None:
 35             return self.treeMinimum(x.right)
 36         y=x.p
 37         while y and x==y.right:
 38             x=y
 39             y=y.p
 40         return y
 41     #前驱节点
 42     def treePredecessor(self,x):
 43         if x.left!=None:
 44             return self.treeMaximum(x.left)
 45         y=x.p
 46         while y and x==y.left:
 47             x=y
 48             y=y.p
 49         return y
 50     def treeInsert(self,T,z):
 51         y=None
 52         x=T
 53         while x:
 54             y=x
 55             if z.key<x.key:
 56                 x=x.left
 57             else:x=x.right
 58         z.p=y
 59         if y==None:
 60             T=z
 61         elif z.key<y.key:
 62             y.left=z
 63         else: y.right=z
 64     #移动子树
 65     def transPlant(self,T,u,v):
 66         if u.p==None:
 67             T=v
 68         elif u==u.p.left:
 69             u.p.left=v
 70         else:
 71             u.p.right=v
 72         if v:
 73             v.p=u.p
 74     #删除给定节点
 75     def treeDelete(self,T,z):
 76         if z.left==None:
 77             self.transPlant(T,z,z.right)
 78         elif z.right==None:
 79             self.transPlant(T,z,z.left)
 80         else:
 81             y=self.treeMinimum(z.right)
 82             if y.p!=z:
 83                 self.transPlant(T,y,y.right)
 84                 y.right=z.right
 85                 y.right.p=y
 86             self.transPlant(T,z,y)
 87             y.left=z.left
 88             y.left.p=y
 89 
 90 if __name__=="__main__":
 91     node1=TreeNode(15)
 92     node2=TreeNode(6)
 93     node3=TreeNode(18)
 94     node4=TreeNode(3)
 95     node5=TreeNode(7)
 96     node6=TreeNode(17)
 97     node7=TreeNode(20)
 98     node8=TreeNode(2)
 99     node9=TreeNode(4)
100     node10=TreeNode(13)
101     node11=TreeNode(9)
102     bstree=BinarySearchTree()
103     bstree.treeInsert(node1,node2)
104     bstree.treeInsert(node1,node3)
105     bstree.treeInsert(node1, node4)
106     bstree.treeInsert(node1, node5)
107     bstree.treeInsert(node1, node6)
108     bstree.treeInsert(node1, node7)
109     bstree.treeInsert(node1, node8)
110     bstree.treeInsert(node1, node9)
111     bstree.treeInsert(node1, node10)
112     bstree.treeInsert(node1, node11)
113     bstree.inorderWalk(node1)
114     node=bstree.treeSearh(node1,7)
115     print("")
116     print(node.key,node.p.key,node.right.key)
117     min_node=bstree.treeMinimum(node1)
118     max_node=bstree.treeMaximum(node1)
119     print(min_node.key,max_node.key)
120     su_node1=bstree.treeSuccessor(node1)
121     print(su_node1.key)
122     su_node2=bstree.treeSuccessor(node10)
123     print(su_node2.key)
124     su_node3 = bstree.treePredecessor(node11)
125     print(su_node3.key)
126     su_node4 = bstree.treePredecessor(node2)
127     print(su_node4.key)
128     z=TreeNode(8)
129     bstree.treeInsert(node1,z)
130     bstree.inorderWalk(node1)
131     bstree.treeDelete(node1,node2)
132     print("")
133     bstree.inorderWalk(node1)