43 def createNode(self, data):
44 return Node(data)
45
46 def printTree (self):
47 """中序遍历"""
48 if self.left:
49 self.left.printTree()
50 print self.data
51 if self.right:
52 self.right.printTree()
53
54 def maxNode(self):
55 if self.right:
56 return self.right.maxNode()
57 else:
58 return self
59
60 def minNode (self):
61 if self.left:
62 return self.left.maxNode()
63 else:
64 return self
65
66 def lookup(self, data):
67 if self.data == data:
68 return self
69
70 if self.data > data:
71 if self.left:
72 return self.left.lookup(data)
73 else:
74 return None
75 else:
76 if self.right:
77 return self.right.lookup(data)
78 else:
79 return None
80
81 def successor(self):
82 """
83 有右子树时,很容易理解, 取右子树的最小值
84 没有右子树时, 也就是说该节点是当前子树的最大节点, 该节点的后继
为把该子树作为左子树的最近的根节点
85 如果要取前驱, 道理一样
86 """
87 n= self
88 if n.right:
89 return n.right.minNode()
90 else:
91 p = n.parent
92 while p and p.right == n:
93 n = p
94 p = p.parent
95 return p
96
97 def delete(self, root):
98 """
99 对于没有子树,或只有一个子树, 都很好处理
100 如果有两个子树, 做法是把节点后继节点拷贝到当前节点, 然后删除后
继节点
101 这不是唯一的做法, 但这样做对树原有的平衡性破坏最小
102 当root被删除时, root会变, 所以需要返回新的root
103 """
104 n= self
105
106 if n.left and n.right:
107 s = n.right.minNode()
108 n.data = s.data