前言
树是数据结构中非常重要的一种，主要的用途是用来提高查找效率，对于要重复查找的情况效果更佳，如二叉排序树、fp-树。另外可以用来提高编码效率，如哈弗曼树。
用 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
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
|
# -*- coding=utf-8 -*-class node(object): """节点类""" def __init__(self, element=-1, l_child=none, r_child=none): self.element = element self.l_child = l_child self.r_child = r_childclass tree(object): """树类""" def __init__(self): self.root = node() self.queue = [] def add_node(self, element): """为树添加节点""" node = node(element) # 如果树是空的，则对根节点赋值 if self.root.element == -1: self.root = node self.queue.append(self.root) else: tree_node = self.queue[0] # 此结点没有左子树，则创建左子树节点 if tree_node.l_child is none: tree_node.l_child = node self.queue.append(tree_node.l_child) else: tree_node.r_child = node self.queue.append(tree_node.r_child) # 如果该结点存在右子树，将此节点丢弃 self.queue.pop(0) def front_recursion(self, root): """利用递归实现树的前序遍历""" if root is none: return print root.element, self.front_recursion(root.l_child) self.front_recursion(root.r_child) def middle_recursion(self, root): """利用递归实现树的中序遍历""" if root is none: return self.middle_recursion(root.l_child) print root.element, self.middle_recursion(root.r_child) def back_recursion(self, root): """利用递归实现树的后序遍历""" if root is none: return self.back_recursion(root.l_child) self.back_recursion(root.r_child) print root.element, @staticmethod def front_stack(root): """利用堆栈实现树的前序遍历""" if root is none: return stack = [] node = root while node or stack: # 从根节点开始，一直找它的左子树 while node: print node.element, stack.append(node) node = node.l_child # while结束表示当前节点node为空，即前一个节点没有左子树了 node = stack.pop() # 开始查看它的右子树 node = node.r_child @staticmethod def middle_stack(root): """利用堆栈实现树的中序遍历""" if root is none: return stack = [] node = root while node or stack: # 从根节点开始，一直找它的左子树 while node: stack.append(node) node = node.l_child # while结束表示当前节点node为空，即前一个节点没有左子树了 node = stack.pop() print node.element, # 开始查看它的右子树 node = node.r_child @staticmethod def back_stack(root): """利用堆栈实现树的后序遍历""" if root is none: return stack1 = [] stack2 = [] node = root stack1.append(node) # 这个while循环的功能是找出后序遍历的逆序，存在stack2里面 while stack1: node = stack1.pop() if node.l_child: stack1.append(node.l_child) if node.r_child: stack1.append(node.r_child) stack2.append(node) # 将stack2中的元素出栈，即为后序遍历次序 while stack2: print stack2.pop().element, @staticmethod def level_queue(root): """利用队列实现树的层次遍历""" if root is none: return queue = [] node = root queue.append(node) while queue: node = queue.pop(0) print node.element, if node.l_child is not none: queue.append(node.l_child) if node.r_child is not none: queue.append(node.r_child)if __name__ == '__main__': """主函数""" # 生成十个数据作为树节点 elements = range(10) tree = tree() for elem in elements: tree.add_node(elem) print '队列实现层次遍历:' tree.level_queue(tree.root) print '\n\n递归实现前序遍历:' tree.front_recursion(tree.root) print '\n递归实现中序遍历:' tree.middle_recursion(tree.root) print '\n递归实现后序遍历:' tree.back_recursion(tree.root) print '\n\n堆栈实现前序遍历:' tree.front_stack(tree.root) print '\n堆栈实现中序遍历:' tree.middle_stack(tree.root) print '\n堆栈实现后序遍历:' tree.back_stack(tree.root) |
需要源码的小伙伴可自行下载：代码传送门
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对服务器之家的支持。
原文链接：https://juejin.im/post/5cdd5f5ee51d453a6c23b0af
