python/binary_tree.py at master · lambdaplus/python · GitHub

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
classNode:

def__init__(self, data):
self.left=None
self.right=None
self.data=data

definsert(self, data):
ifdata<self.data: # 树叉小于节点
ifself.leftisNone: # 并且左面的树叉为空
self.left=Node(data) # 当仁不让的插入
else: # 非空的话
self.left.insert(data) # 以左树叉为节点继续插入

elifdata>self.data:
ifself.rightisNone:
self.right=Node(data)
else:
self.right.insert(data)
else:
self.data=data

defsearch(self, data, parent=None):
'''
 data为目标查询值，同时返回parent(父节点)便于定位。
 '''
ifdata<self.data:
ifself.leftisNone:
returnNone, None
else:
returnself.left.search(data, self)

elifdata>self.data:
ifself.rightisNone:
returnNone, None

returnself.right.search(data, self)
else:
# return self.data, parent.data
returnself, parent

defprint_tree_in(self): # 中序
ifself.left:
self.left.print_tree_in()
print(self.data)
ifself.right:
self.right.print_tree_in()

defprint_tree_pre(self): # 前序
print(self.data)
ifself.left:
self.left.print_tree_pre()
ifself.right:
self.right.print_tree_pre()

defprint_tree_post(self): # 后序
ifself.left:
self.left.print_tree_post()
ifself.right:
self.right.print_tree_post()
print(self.data)

defchrildren(self):
count=0
ifself.left:
count+=1

ifself.right:
count+=1

returncount

defdelete(self, data):
node, parent=self.search(data)
chrildren=node.chrildren() # 子节点数目
ifchrildren==0: # 情况 1， 没有子节点，直接删除即可
ifparent.leftisnode: # 判断目标节点是其父节点的 左or右 节点
parent.left=None
else:
parent.right=None
delnode

elifchrildren==1: # 情况 2， 有一个子节点，用子节点替换其即可
ifnode.left:
tmp=node.left
else:
tmp=node.right
ifparent:
ifparent.leftisnode:
parent.left=tmp
else:
parent.right=tmp
delnode
else:
'''
 第三种情况比较复杂：
 1. 左节点0个子节点
 2. 左节点1个子节点
 3. 左节点2个子节点
 '''
parent=node
successor=node.right
whilesuccessor.left: # 递归思想，直至找到最左的子节点， 保持树的平衡，用右子节点的值替换
parent=successor
successor=successor.left
node.data=successor.data
ifparent.left==successor:
parent.left=successor.right
else:
parent.right=successor.right

# 接下来可以测试以下种的树怎么样啦。
root=Node(11)
root.insert(14)
root.insert(9)
root.insert(9)
root.insert(7)
root.insert(10)
root.insert(4)
root.insert(5)
root.insert(6)
root.insert(8)
value, parent=root.search(10)
print(value.data, parent.data)
root.print_tree_in()
print('*'*20)
root.delete(4)
root.print_tree_in()