对于二叉查找树的每个节点Node，它的左子树中所有的关键字都小于Node的关键字，而右子树中的所有关键字都大于Node的关键字。
二叉查找树的平均深度是O(log N)。
1.初始化
|
1
2
3
4
5 |
class
BinarySearchTree(object): def
__init__(self,key): self.key=key self.left=None self.right=None |
2.Find
|
1
2
3
4
5
6
7
8
9 |
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，从根开始并且只要有左儿子就向左进行查找，终止点是最小元素。FindMax则向右进行。
|
1
2
3
4
5
6
7
8
9
10
11 |
def findMin(self): if
self.left: return
self.left.findMin() else: return
selfdef findMax(self): tree=self if
tree: while
tree.right: tree=tree.right return
tree |
4.Insert
为了将x插入到树Tree中，先用find查找，如果找到x，则什么也不做。否则，将x插入到遍历路径的最后一点。
来自《Problem Solving with Algorithms and Data Structures》的图片：
|
1
2
3
4
5
6
7
8
9
10
11
12
13 |
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
删除某节点有3种情况：
5.1 如果节点是一片树叶，那么可以立即被删除。
来自《Problem Solving with Algorithms and Data Structures》的图片：
5.2 如果节点只有一个儿子，则将此节点parent的指针指向此节点的儿子，然后删除。
来自《Problem Solving with Algorithms and Data Structures》的图片：
5.3 如果节点有两个儿子，则将其右子树的最小数据代替此节点的数据，并将其右子树的最小数据（不可能有左儿子，只有一个右儿子）删除。
来自《Problem Solving with Algorithms and Data Structures》的图片：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
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 |
全部代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 |
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 |
另一种类似于链表的写法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133 |
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 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: #有两个儿子 minNode=self._findMin(node.right) node.key=minNode.key self.remove(minNode) else: #有一个儿子 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 |
Python数据结构————二叉查找树的实现,布布扣,bubuko.com
原文：http://www.cnblogs.com/linxiyue/p/3624597.html