Python实现和遍历二叉树

先思考:

  1. 怎么表示一棵树(如二叉树)
  2. 树有哪几种遍历方式,怎么实现
  3. 给定其中N种遍历结果,如何还原树

树的表示可以用节点来表示,树由N个节点组成。

树的遍历有两大种,深度优先(先序遍历、中序遍历、后序遍历)和广度优先遍历(层次遍历)。

深度优先一般用递归,一般能用递归实现的也能由堆栈实现。广度优先一般用队列。

构建树可以用递归的方法,也可以用节点直接初始化。

二叉树用递归去理解和实现都比较直观方便。

以下代码给出二叉树的构建、递归实现先中后序遍历、队列实现层次遍历、已知先中序遍历如何还原树:

# 二叉树的实现与遍历 Python 3
class Node:
"""节点 树由N个节点组成"""
def __init__(self, data, left_child=None, right_child=None):
self.data = data
self.left_child = left_child
self.right_child = right_child
def append_node(tree, node):
"""将节点node添加到一棵树上 递归实现 用于生成树时调用。
构建策略是:值越大越是在右下角,越小越在左下角 策略1
"""
if node.data < tree.data:
if tree.left_child:
append_node(tree.left_child, node)
else:
tree.left_child = node
else:
if tree.right_child:
append_node(tree.right_child, node)
else:
tree.right_child = node
def build_tree(sequence):
"""利用序列生成一棵树 策略1"""
# 初始化树
tree = Node(sequence[0])
for i in sequence[1:]:
append_node(tree, Node(i))
return tree
def preorder_traversal(tree):
"""递归实现 先序遍历"""
if tree:
print(tree.data)
preorder_traversal(tree.left_child)
preorder_traversal(tree.right_child)
def inorder_traversal(tree):
"""递归实现 中序遍历"""
if tree:
inorder_traversal(tree.left_child)
print(tree.data)
inorder_traversal(tree.right_child)
def postorder_traversal(tree):
"""递归实现 后序遍历"""
if tree:
postorder_traversal(tree.left_child)
postorder_traversal(tree.right_child)
print(tree.data)
def level_traversal(tree, length):
"""递归实现 层次遍历 广度优先
可以优化成一个参数 去掉第二个长度参数
"""
q = [tree] # 用列表模拟先进先出的队列
# length = len(tree) # tree并没实现 __len__
# 遍历一次就打印一个节点上的值,共遍历length次
for i in range(length):
print(q[i])
# 将当前节点的左右子节点分别入队 如此实现广度优先
if q[i].left_child:
q.append(q[i].left_child)
if q[i].right_child:
q.append(q[i].right_child)
def reconstruct_tree(preorder, inorder):
"""已知先序遍历和中序遍历 重建二叉树 用递归实现"""
if not preorder or not inorder:
return None
data = preorder[0]
i = inorder.index(data)
left_child = reconstruct_tree(preorder[1:i+1], inorder[:i])
right_child = reconstruct_tree(preorder[i+1:], inorder[i+1:])
return Node(data, left_child, right_child)
if __name__ == '__main__':
# 序列构建树 策略1
sequence = [3, 4, 2, 6, 7, 1, 8, 5]
tree1 = build_tree(sequence)
print('tree1先序遍历如下:')
preorder_traversal(tree1)
print('tree1中序遍历如下:')
inorder_traversal(tree1)
print('tree1后序遍历如下:')
postorder_traversal(tree1)
print('tree1层次遍历如下:')
level_traversal(tree1, len(sequence))
# 直接Node节点构建树 策略2
tree2 = Node(3, Node(2, Node(1)), Node(4, right_child=Node(6, Node(5), Node(7, right_child=Node(8)))))
print('tree2先序遍历如下:')
preorder_traversal(tree2)
print('tree2中序遍历如下:')
inorder_traversal(tree2)
print('tree2后序遍历如下:')
postorder_traversal(tree2)
print('tree2层次遍历如下:')
level_traversal(tree2, len(sequence))
# 已知先序遍历和中序遍历 重建二叉树
preorder = [1, 2, 4, 7, 3, 5, 6, 8]
inorder = [4, 7, 2, 1, 5, 3, 8, 6]
tree3 = reconstruct_tree(preorder, inorder)
print('tree3先序遍历如下:')
preorder_traversal(tree3)
print('tree3中序遍历如下:')
inorder_traversal(tree3)
print('tree3后序遍历如下:')
postorder_traversal(tree3)
print('tree3层次遍历如下:')
level_traversal(tree3, len(preorder))

输出结果:

tree1先序遍历如下:
3
2
1
4
6
5
7
8
tree1中序遍历如下:
1
2
3
4
5
6
7
8
tree1后序遍历如下:
1
2
5
8
7
6
4
3
tree1层次遍历如下:
3
2
4
1
6
5
7
8
tree2先序遍历如下:
3
2
1
4
6
5
7
8
tree2中序遍历如下:
1
2
3
4
5
6
7
8
tree2后序遍历如下:
1
2
5
8
7
6
4
3
tree2层次遍历如下:
3
2
4
1
6
5
7
8
tree3先序遍历如下:
1
2
4
7
3
5
6
8
tree3中序遍历如下:
4
7
2
1
5
3
8
6
tree3后序遍历如下:
7
4
2
5
8
6
3
1
tree3层次遍历如下:
1
2
3
4
5
6
7
8

参考资料: