树和图的数据结构，就很有意思啦。
|
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
|
# coding = utf-8
class BinaryTree:
def __init__(self, root_obj):
self.key = root_obj
self.left_child = None
self.right_child = None
def insert_left(self, new_node):
node = BinaryTree(new_node)
if self.left_child is None:
self.left_child = node
else:
node.left_child = self.left_child
self.left_child = node
def insert_right(self, new_node):
node = BinaryTree(new_node)
if self.right_child is None:
self.right_child = node
else:
node.right_child = self.right_child
self.right_child = node
def get_right_child(self):
return self.right_child
def get_left_child(self):
return self.left_child
def set_root_val(self, obj):
self.key = obj
def get_root_val(self):
return self.key
root = BinaryTree('a')
print(root.get_root_val())
print(root.get_left_child())
root.insert_left('b')
print(root.get_left_child())
print(root.get_left_child().get_root_val())
root.insert_right('c')
print(root.get_right_child())
print(root.get_right_child().get_root_val())
root.get_right_child().set_root_val('hello')
print(root.get_right_child().get_root_val())
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
C:\Users\Sahara\.virtualenvs\test\Scripts\python.exe C:/Users/Sahara/PycharmProjects/test/python_search.py
a
None
<__main__.BinaryTree object at 0x00000000024139B0>
b
<__main__.BinaryTree object at 0x00000000024139E8>
c
hello
Process finished with exit code 0
|
Python实现二叉树遍历的递归和非递归算法
前序遍历
|
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
|
# -----------前序遍历 ------------
# 递归算法
def pre_order_recursive(self, T):
if T == None:
return
print(T.root, end=' ')
self.pre_order_recursive(T.lchild)
self.pre_order_recursive(T.rchild)
# 非递归算法
def pre_order_non_recursive(self, T):
"""借助栈实现前驱遍历
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
print(T.root, end=' ')
T = T.lchild
else:
T = stack[-1]
stack.pop()
T = T.rchild
|
中序遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
# -----------中序遍历 ------------
# 递归算法
def mid_order_recursive(self, T):
if T == None:
return
self.mid_order_recursive(T.lchild)
print(T.root, end=' ')
self.mid_order_recursive(T.rchild)
# 非递归算法
def mid_order_non_recursive(self, T):
"""借助栈实现中序遍历
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
T = T.lchild
else:
T = stack.pop()
print(T.root, end=' ')
T = T.rchild
|
后序遍历
|
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
|
# -----------后序遍历 ------------
# 递归算法
def post_order_recursive(self, T):
if T == None:
return
self.post_order_recursive(T.lchild)
self.post_order_recursive(T.rchild)
print(T.root, end=' ')
# 非递归算法
def post_order_non_recursive(self, T):
"""借助两个栈实现后序遍历
"""
if T == None:
return
stack1 = []
stack2 = []
stack1.append(T)
while stack1:
node = stack1.pop()
if node.lchild:
stack1.append(node.lchild)
if node.rchild:
stack1.append(node.rchild)
stack2.append(node)
while stack2:
print(stack2.pop().root, end=' ')
return
|
层次遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
# -----------层次遍历 ------------
def level_order(self, T):
"""借助队列（其实还是一个栈）实现层次遍历
"""
if T == None:
return
stack = []
stack.append(T)
while stack:
node = stack.pop(0) # 实现先进先出
print(node.root, end=' ')
if node.lchild:
stack.append(node.lchild)
if node.rchild:
stack.append(node.rchild)
|
完整代码
|
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
class NodeTree:
def __init__(self, root=None, lchild=None, rchild=None):
"""创建二叉树
Argument:
lchild: BinTree
左子树
rchild: BinTree
右子树
Return:
Tree
"""
self.root = root
self.lchild = lchild
self.rchild = rchild
class BinTree:
# -----------前序遍历 ------------
# 递归算法
def pre_order_recursive(self, T):
if T == None:
return
print(T.root, end=' ')
self.pre_order_recursive(T.lchild)
self.pre_order_recursive(T.rchild)
# 非递归算法
def pre_order_non_recursive(self, T):
"""借助栈实现前驱遍历
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
print(T.root, end=' ')
T = T.lchild
else:
T = stack[-1]
stack.pop()
T = T.rchild
# -----------中序遍历 ------------
# 递归算法
def mid_order_recursive(self, T):
if T == None:
return
self.mid_order_recursive(T.lchild)
print(T.root, end=' ')
self.mid_order_recursive(T.rchild)
# 非递归算法
def mid_order_non_recursive(self, T):
"""借助栈实现中序遍历
"""
if T == None:
return
stack = []
while T or len(stack) > 0:
if T:
stack.append(T)
T = T.lchild
else:
T = stack.pop()
print(T.root, end=' ')
T = T.rchild
# -----------后序遍历 ------------
# 递归算法
def post_order_recursive(self, T):
if T == None:
return
self.post_order_recursive(T.lchild)
self.post_order_recursive(T.rchild)
print(T.root, end=' ')
# 非递归算法
def post_order_non_recursive(self, T):
"""借助两个栈实现后序遍历
"""
if T == None:
return
stack1 = []
stack2 = []
stack1.append(T)
while stack1:
node = stack1.pop()
if node.lchild:
stack1.append(node.lchild)
if node.rchild:
stack1.append(node.rchild)
stack2.append(node)
while stack2:
print(stack2.pop().root, end=' ')
return
# -----------层次遍历 ------------
def level_order(self, T):
"""借助队列（其实还是一个栈）实现层次遍历
"""
if T == None:
return
stack = []
stack.append(T)
while stack:
node = stack.pop(0) # 实现先进先出
print(node.root, end=' ')
if node.lchild:
stack.append(node.lchild)
if node.rchild:
stack.append(node.rchild)
# ----------- 前序遍历序列、中序遍历序列 —> 重构二叉树 ------------
def tree_by_pre_mid(self, pre, mid):
if len(pre) != len(mid) or len(pre) == 0 or len(mid) == 0:
return
T = NodeTree(pre[0])
index = mid.index(pre[0])
T.lchild = self.tree_by_pre_mid(pre[1:index + 1], mid[:index])
T.rchild = self.tree_by_pre_mid(pre[index + 1:], mid[index + 1:])
return T
# ----------- 后序遍历序列、中序遍历序列 —> 重构二叉树 ------------
def tree_by_post_mid(self, post, mid):
if len(post) != len(mid) or len(post) == 0 or len(mid) == 0:
return
T = NodeTree(post[-1])
index = mid.index(post[-1])
T.lchild = self.tree_by_post_mid(post[:index], mid[:index])
T.rchild = self.tree_by_post_mid(post[index:-1], mid[index + 1:])
return T
if __name__ == '__main__':
# ----------- 测试：前序、中序、后序、层次遍历 -----------
# 创建二叉树
nodeTree = NodeTree(1,
lchild=NodeTree(2,
lchild=NodeTree(4,
rchild=NodeTree(7))),
rchild=NodeTree(3,
lchild=NodeTree(5),
rchild=NodeTree(6)))
T = BinTree()
print('前序遍历递归\t')
T.pre_order_recursive(nodeTree) # 前序遍历-递归
print('\n')
print('前序遍历非递归\t')
T.pre_order_non_recursive(nodeTree) # 前序遍历-非递归
print('\n')
print('中序遍历递归\t')
T.mid_order_recursive(nodeTree) # 中序遍历-递归
print('\n')
print('中序遍历非递归\t')
T.mid_order_non_recursive(nodeTree) # 中序遍历-非递归
print('\n')
print('后序遍历递归\t')
T.post_order_recursive(nodeTree) # 后序遍历-递归
print('\n')
print('后序遍历非递归\t')
T.post_order_non_recursive(nodeTree) # 后序遍历-非递归
print('\n')
print('层次遍历\t')
T.level_order(nodeTree) # 层次遍历
print('\n')
print('==========================================================================')
# ----------- 测试：由遍历序列构造二叉树 -----------
T = BinTree()
pre = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
mid = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
post = ['C', 'B', 'E', 'H', 'G', 'I', 'F', 'D', 'A']
newT_pre_mid = T.tree_by_pre_mid(pre, mid) # 由前序序列、中序序列构造二叉树
T.post_order_recursive(newT_pre_mid) # 获取后序序列
print('\n')
newT_post_mid = T.tree_by_post_mid(post, mid) # 由后序序列、中序序列构造二叉树
T.pre_order_recursive(newT_post_mid) # 获取前序序列
|
运行结果
前序遍历递归
1 2 4 7 3 5 6前序遍历非递归
1 2 4 7 3 5 6中序遍历递归
4 7 2 1 5 3 6中序遍历非递归
4 7 2 1 5 3 6后序遍历递归
7 4 2 5 6 3 1后序遍历非递归
7 4 2 5 6 3 1层次遍历
1 2 3 4 5 6 7==========================================================================
C B E H G I F D AA B C D E F G H I
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://www.cnblogs.com/aguncn/p/10693337.html