二叉树的遍历主要有深度遍历和广度遍历两种，深度遍历就是指常见的先序、中序、后序三种遍历方法，广度遍历就是常说的层次遍历。

深度遍历

  • 先序遍历：根节点 ——> 先序遍历左子树 ——> 先序遍历右子树
  • 中序遍历：先序遍历左子树 ——> 根节点 ——> 先序遍历右子树
  • 后序遍历：先序遍历左子树 ——> 先序遍历右子树 ——> 根节点
    下图表示指针沿着图中箭头遍历整个二叉树的整个过程，可以看出对于树的每个节点指针都要经过它3次。若当指针第一次经过该节点时输出，得到的则为先序遍历；若当指针第二次经过该节点时输出，则为中序遍历；若当指针第三次经过该节点时输出，则为后序遍历。

因为树的定义本身是递归定义，所以采用递归的方法实现树的三种基本遍历最容易理解，代码也最简介(本文所有代码基于Python3.6)。
树的节点定义如下

1
2
3
4
5
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

递归遍历

先序遍历

基于先序遍历的流程，先访问根节点，然后左子树，最后右子树

1
2
3
4
5
def recursion_pre_order(root):
    if root is not None:
        print(root.value)
        recursion_pre_order(root.left)
        recursion_pre_orderr(root.right)

中序遍历

根据中序遍历和先序遍历的差别，将访问根节点的代码调整到左右子树之间即可

1
2
3
4
5
def recursion_in_order(root):
    if root is not None:
        recursion_in_order(root.left)
        print(root.value)
        recursion_in_order(root.right)

后序遍历

后序遍历同理

1
2
3
4
5
def recursion_post_order(root):
    if root is not None:
        recursion_post_orde(root.left)
        recursion_post_orde(root.right)
        print(root.value)

非递归遍历

先序遍历

用栈暂存二叉树的节点，根据栈的先进后出的性质，访问二叉树的根节点后先让右子树入栈，然后左子树入栈，即可在栈弹出时左子树先弹出，右子树后弹出，这样就满足了先序遍历的顺序。具体的遍历流程为：
首先需要先从栈顶取出节点，然后访问该节点，如果该节点不为空，则访问该节点，同时把该节点的右子树先入栈，然后左子树入栈

1
2
3
4
5
6
7
8
9
10
11
12
def non_recursion_pre_order(root):
    if root is None:
        return
    s = []
    s.append(root)
    while(len(s) != 0):
        t = s.pop()
        print(t.value)
        if(t.right is not None):
            s.append(t.right)
        if(t.left is not None):
            s.append(t.left)

中序遍历

对于当前树，将自己左边界依次压入栈，然后弹出最左的节点输出，然后对弹出节点的右子树执行相同的操作，若其右子树为空，则继续访问栈顶节点。具体的遍历流程为：
若当前节点为空，栈中弹出一个节点输出，然后继续向右，若当前节点不为空，当前节点压入栈，然后当前节点往左。

1
2
3
4
5
6
7
8
9
10
11
12
def non_recursion_in_order(root):
    if root is None:
        return 
    s = []
    while(len(s) != 0 or root is not None):
        if root is not None:
            s.append(root)
            root = root.left
        else:
            t = s.pop()
            print(t.value)
            root = t.right

后序遍历

后序遍历的顺序为先左子树，然后右子树，最后才是根节点。可以根据非递归的先序遍历先实现先根节点，然后右子树，最后左子树的顺序，然后用另一个辅助栈对该顺序逆序，即可得到先左子树，然后右子树，最后根节点的遍历顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def non_recursion_post_order(root):
    if root is None:
        return
    s = []
    h = []
    s.append(root)
    while(len(s) != 0):
        t = s.pop()
        h.append(t)
        if(t.right is not None):
            s.append(t.right)
        if(t.left is not None):
            s.append(t.left)
    while(len(h) != 0):
        print(h.pop().value)

层次遍历

使用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
# 层次遍历
def level_order(root):
    q = Queue()
    if root is None:
        return
    q.put(root)
    while not q.empty():
        node = q.get()
        print(node.value, end='  ')
        if node.left is not None:
            q.put(node.left)
        if node.right is not None:
            q.put(node.right)

拓展：按层打印二叉树

使用一个变量记录当前遍历节点是否为该层的最右侧节点，如果是则换行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 按层打印二叉树
def printByLevel(root):
    if root is None:
        return
    q = Queue()
    last = root
    q.put(root)
    while not q.empty():
        node = q.get()
        if node.left is not None:
            q.put(node.left)
            nlast = node.left
        if node.right is not None:
            q.put(node.right)
            nlast = node.right
        
        print(node.value, end=' ')
        if last == node:
            print()
            last = nlast