一、二叉树的遍历

在计算机程序中，遍历本身是一个线性操作，而二叉树是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列。以不同的方式遍历，遍历出来的序列顺序也不同。

从节点之间位置关系的角度来看，二叉树的遍历分为4种。

1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层序遍历

从更宏观的角度来看，二叉树的遍历归结为两大类。

1. 深度优先遍历（前序遍历、中序遍历、后序遍历）
2. 广度优先遍历（层序遍历）

 

二、深度优先遍历

所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。

1.前序遍历

二叉树的前序遍历，输出顺序时根节点、左子树、右子树。

前序遍历的顺序是124536.

 

2.中序遍历

二叉树的中序遍历，输出顺序是左子树、根节点、右子树。

 中序遍历的顺序是425136

 

3.后序遍历

二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

后序遍历的顺序是452631.

用代码写二叉树的3种遍历方式：

 1 class TreeNode:
 2     def __init__(self, data):
 3         self.data = data
 4         self.left = left
 5         self.right = right
 6     
 7 def create_binary_tree(input_list=[]):
 8     """
 9     构建二叉树
10     :param input_list: 输入数列
11     """
12     if input_list is None or len(input_list) == 0:
13         return None
14     data = input_list.pop(0)
15     if data is None:
16         return None
17     node = TreeNode(data)
18     node.left = create_binary_tree(input_list)
19     node.right = create_binary_tree(input_list)
20     return node
21 
22 def pre_order_traversal(node):
23     """
24     前序遍历
25     :param node: 二叉树节点
26     """
27     if node is None:
28         return 
29     print(node.data)
30     pre_order_traversal(node.left)
31     pre_order_traversal(node.right)
32     return node
33 
34 def in_order_traversal(node):
35     """
36     中序遍历
37     :param node: 二叉树节点
38     """
39     if node is None:
40         return
41     in_order_traversal(node.left)
42     print(node.data)
43     in_order_traversal(node.right)
44     return node
45 
46 def post_order_traversal(node):
47     """
48     后序遍历
49     :param node: 二叉树节点
50     """
51     if node is None:
52         return
53     post_order_traversal(node.left)
54     post_order_traversal(node.right)
55     print(node.data)
56     return node
57 
58 my_input_list = list([3, 2, 9, None, None, 10, None, None, 8, None, 4])
59 root = create_binary_tree(my_input_list)
60 print("前序遍历：")
61 pre_order_traversal(root)
62 print("中序遍历：")
63 in_order_traversal(root)
64 print("后序遍历：")
65 post_order_traversal(root)

 

4.小结

前序、中序、后序是指根节点在左右孩子的位置，如前序就是在前面，为中左右、中序在中间，为左中右、后序在后面，为左右中。

 

三、广度优先遍历

广度优先遍历与深度优先遍历相反，是先在各个方向上各走出1步，再在各个方向上走出第2步、第3步……一直到各个方向全部走完。

层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。

 

 1 from queue import Queue
 2 
 3 def level_order_traversal(node):
 4     queue = Queue()
 5     queue.put(node)
 6     while not queue.empty():
 7         node = queue.get()
 8         print(node.data)
 9         if node.left is not None:
10             queue.put(node.left)
11         if node.right is not None:
12             queue.put(node.right)