algorithm/binary_tree.py at master · SMZCC/algorithm · 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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#! /usr/bin/env python
#coding:utf-8

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)

deflookup(self, data, parent=None):
"""
 遍历二叉树
 """
ifdata<self.data:
ifself.leftisNone:
returnNone, None
returnself.left.lookup(data, self)
elifdata>self.data:
ifself.rightisNone:
returnNone, None
returnself.right.lookup(data, self)
else:
returnself, parent

defdelete(self, data):
"""
 删除节点
 """
node, parent=self.lookup(data) #已有节点
ifnodeisnotNone:
children_count=node.children_count() #判断子节点数
ifchildren_count==0:
# 如果该节点下没有子节点，即可删除
ifparent.leftisnode:
parent.left=None
else:
parent.right=None
delnode
elifchildren_count==1:
# 如果有一个子节点，则让子节点上移替换该节点（该节点消失)
ifnode.left:
n=node.left
else:
n=node.right
ifparent:
ifparent.leftisnode:
parent.left=n
else:
parent.right=n
delnode
else:
# 如果有两个子节点，则要判断节点下所有叶子
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

defcompare_trees(self, node):
"""
 比较两棵树
 """
ifnodeisNone:
returnFalse
ifself.data!=node.data:
returnFalse
res=True
ifself.leftisNone:
ifnode.left:
returnFalse
else:
res=self.left.compare_trees(node.left)
ifresisFalse:
returnFalse
ifself.rightisNone:
ifnode.right:
returnFalse
else:
res=self.right.compare_trees(node.right)
returnres

defprint_tree(self):
"""
 按顺序打印数的内容
 """
ifself.left:
self.left.print_tree()
printself.data,
ifself.right:
self.right.print_tree()

deftree_data(self):
"""
 二叉树数据结构
 """
stack= []
node=self
whilestackornode:
ifnode:
stack.append(node)
node=node.left
else:
node=stack.pop()
yieldnode.data
node=node.right

defchildren_count(self):
"""
 子节点个数
 """
cnt=0
ifself.left:
cnt+=1
ifself.right:
cnt+=1
returncnt