二叉树的遍历详解

发表于 | 分类于 ， ，

本文主要对二叉树的各种遍历方式进行详细的描述，包括深度优先遍历(前序遍历|中序遍历|后序遍历)和广度优先遍历(也叫层序遍历)，同时从递归和非递归的两种角度进行实现，采用Java语言编写。

详细代码实现

首先给出基础的树节点定义，包括一个获取二叉树总节点个数的方法，后面在后序遍历的非递归实现中会用到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

static class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int v) {
        val = v;
    }
}

//获取二叉树的总节点数
public static int size (TreeNode node) {
    if (node==null) {
        return 0;
    }
    return 1 + size(node.left) + size(node.right);
}

本文以下图所示的二叉树为例进行描述。

bianry_tree

该二叉树的各种遍历方式结果如下：

  • 前序遍历：1 2 4 7 3 5 6 8
  • 中序遍历：4 7 2 1 5 3 8 6
  • 后序遍历：7 4 2 5 8 6 3 1
  • 层序遍历：1 2 3 4 5 6 7 8

深度优先遍历

深度优先遍历是指沿着树的深度遍历树的节点，尽可能深的搜索树的分支。对于树的深度优先遍历而言，可进一步按照根节点相对于左右子节点的访问先后来划分。如果把左节点和右节点的位置固定不动，那么根节点放在左节点的左边，称为前序（pre-order）、根节点放在左节点和右节点的中间，称为中序（in-order）、根节点放在右节点的右边，称为后序（post-order）。

因为树结构本身就是递归思想的一种生动的实例，所以递归实现的遍历代码非常简洁清晰。而非递归的实现方式，主要也是用栈结构模拟递归调用实现。

前序遍历

即按照 根节点->左节点->右节点 的顺序进行遍历。

首先给出递归实现：

1
2
3
4
5
6
7
8
9
10
11

//前序遍历 递归实现
public static void preOrderTraversalByRecursion(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.print(" " + node.val);

    preOrderTraversalByRecursion(node.left);
    preOrderTraversalByRecursion(node.right);
}

遍历的递归实现比较简单，不过这个代码可以很好的说明递归实现的思想。递归实现的两个关键条件就是：最小单元和终止条件。

下图就是可以描述树这种数据结构特点的一个最小单元，当我们要遍历整个树的时候，先考虑正确遍历这个最小单元，前序遍历需要按照 “根->左->右” 的顺序进行遍历，所以先输出根节点的值，然后递归处理左节点，右节点，即有了上面递归函数的处理顺序。

而终止条件就是判断递归处理何时应该结束，对于当前遍历实现就是当处理到null节点的时候。

当我们希望利用递归的方式处理更复杂的编程情况时，二叉树的递归遍历是个很好的基础参考。

binary_tree_max_item

下面给出前序遍历的非递归实现，共有两种方式。

非递归实现1如下：

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

//前序遍历 非递归 实现1
public static void preOrderTraversal1(TreeNode root) {
    if (root==null) {
        return;
    }

    System.out.println();
    //初始化一个栈
    Stack<TreeNode> stack = new Stack<TreeNode>();
    //首先将根节点压入栈中
    stack.push(root);

    while(stack.isEmpty()==false) {
        TreeNode node = stack.pop();
        System.out.print(" " + node.val);

        //后入先出 按照先右节点 再左节点的顺序依次压入栈
        if (node.right != null) {
            stack.push(node.right);
        }

        if (node.left != null) {
            stack.push(node.left);
        }
    }
    System.out.println();
}

对于非递归实现1而言：

  1. 初始化一个栈，首先将根节点压入栈中。
  2. 之后进入循环，在循环中，将栈顶的元素弹出，并进行输出，之后因为栈后入先出的属性，因此先压入右节点，再压入左节点。
  3. 下一次循环就会将左节点先弹出，进行同样的处理。
  4. 最后按照 根->左->右 的方式遍历完全部节点即完成。

因为前序遍历的特殊性，首先输出根节点，因此处理完后可以不必再回溯根节点，所以可以按照这种方式进行处理。

非递归实现1和后面的层级遍历的实现具有高度的饿对称性，这个放在层级遍历进行分析。

另一种非递归实现2如下：

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

//前序遍历 非递归 实现2
public static void preOrderTraversal2(TreeNode root) {
    if (root == null) {
        return;
    }

    System.out.println();
    //初始化一个栈
    Stack<TreeNode> stack = new Stack<TreeNode>();
    //建立一个临时节点
    TreeNode node = root;

    while (node != null || stack.isEmpty() == false) {

        //内循环
        while (node != null) {
            //输出节点
            System.out.print(" " +node.val);
            stack.push(node);
            node = node.left;
        }

        node = stack.pop();
        node = node.right;
    }
    System.out.println();
}

对于非递归实现2而言：

  1. 初始化一个栈
  2. 临时节点node起到游标的作用，从根节点root出发。
  3. 之后进入双层循环，对于第一次循环而言，内循环从根节点开始，以上文中的二叉树为例，将1->2->4这一支最左侧子链 依次输出 并压入栈，这一支左子链完结之后从内循环跳出；接下来出栈节点，获取该节点的右子树，进入内循环，按照相同的方式处理。一直到所有的节点处理完毕。
  4. 比较贴切的利用栈模仿了前序遍历的递归实现。

中序遍历

即按照 左节点->根节点->右节点 的顺序进行遍历。

递归实现如下：

1
2
3
4
5
6
7
8
9
10

//中序遍历 递归实现
public static void inOrderTraversalByRecursion(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderTraversalByRecursion(node.left);
    System.out.print(" " + node.val);
    inOrderTraversalByRecursion(node.right);
}

非递归实现如下：

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

//中序遍历 非递归
public static void inOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }

    System.out.println();
    //初始化一个栈
    Stack<TreeNode> stack = new Stack<TreeNode>();
    //建立一个临时节点
    TreeNode node = root;

    while (node != null || stack.isEmpty() == false) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        //输出节点
        System.out.print(" " +node.val);

        node = node.right;
    }

    System.out.println();
}

对于非递归实现而言：

  1. 中序遍历的非递归实现和前序遍历的非递归实现2基本相同，只是输出节点的位置不同。
  2. 进入双层循环后，对于第一次循环而言，内循环从根节点开始，以上文中的二叉树为例，将1->2->4这一支最左侧子链依次压入栈，这一支左子链完结之后从内循环跳出；接下来出栈节点，在这里才输出节点，即先输出左子节点，获取该节点的右子树，之后进入内循环，按照相同的方式处理。一直到所有的节点处理完毕。

后序遍历

递归实现如下：

1
2
3
4
5
6
7
8
9
10

//后序遍历 递归实现
public static void postOrderTraversalByRecursion(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderTraversalByRecursion(node.left);
    postOrderTraversalByRecursion(node.right);
    System.out.print(" " + node.val);
}

非递归实现如下：

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

//后序遍历 非递归
public static void postOrderTraversal(TreeNode root){
    if (root == null) {
        return;
    }

    int size = size(root);

    System.out.println();
    //初始化一个栈
    Stack<TreeNode> stack = new Stack<TreeNode>();
    //建立一个临时节点
    TreeNode node = root;
    //初始化一个数组 用于标示对应节点的右节点是否已经处理
    int[] flag = new int[size+1];

    while(node !=null) {
        stack.push(node);
        node = node.left;

        //初始化为0
        flag[stack.size()] = 0;
    }

    while(stack.isEmpty() ==false ) {
        node = stack.peek();
        while(node.right != null && flag[stack.size()] == 0) {
            //该节点的右节点有值 并且还没被处理过
            node = node.right;
            flag[stack.size()] = 1;

            while(node != null) {
                stack.push(node);
                node = node.left;
                flag[stack.size()] = 0;
            }

            node = stack.peek();
        }

        node = stack.pop();
        //输出节点
        System.out.print(" " +node.val);
    }

    System.out.println();
}

后序遍历的非递归处理比较复杂一些。主要原因在于后序遍历的顺序是：左->右->根，那就意味着输出左节点之后，需要回溯到根节点，借由根节点先去输出右节点，最后再回溯输出根节点。相当于回溯了两次根节点，那么关键就是要区别出这两次回溯。

这里采用了一个记录回溯状态的数组flag，当某个节点存在右子树并且已经处理过右子树之后，就置为1。等到处理完右节点之后的第二次回溯就可以输出该节点了，不用再进行右节点的处理。

分步骤看后序遍历的非递归实现：

  1. 首先初始化一个栈，之后利用一个循环将根节点的最左侧子链依次压入栈中。
  2. 然后进入一个三层循环，在第一层循环中，peek一下栈顶元素，若该元素拥有右子树并且还没被处理(flag标志为0)。有右子树说明该栈顶元素就是自己这一层级的根节点，所以进入第二层循环先处理该栈顶元素的右节点。
  3. 在第二层循环中，传入的右节点相对于自己的层级就是根节点，还是要先把左子树压入，之后peek一下栈顶元素，若这个栈顶元素还有右子树且还没被处理，其实又再次进入二层循环的处理。
  4. 直到碰到没有右子树或者右子树已处理的情况，就输出节点。
  5. 按照这种方式输出 正是 左->右->根 的顺序输出。

广度优先遍历(层级遍历)

广度有限遍历即层次遍历是从根节点开始，沿着树的宽度遍历树的节点。从根节点到叶子节点，一层一层按照从左到右的顺序依次遍历节点。

广度优先遍历的实现方式如下：

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

//广度优先遍历
public static void BFS(TreeNode root) {
    if (root == null) {
        return;
    }

    System.out.println();
    //初始化一个队列
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    //将root根节点入队
    queue.offer(root);

    while(queue.isEmpty() == false) {
        //出队
        TreeNode node = queue.poll();
        System.out.print(" "+node.val);

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    System.out.println();
}

对于广度优先遍历的实现而言：

  1. 首先初始化一个队列，将根节点入队
  2. 进入循环，第一次循环时，将队首的根节点出队并输出（第一层就输出完毕了），由于队列是先进先出的属性，所以先将左子节点入队，再将右子节点入队。在下一次循环中，第二层就会按照从左到右的顺序依次出队，并且第三层的元素按照从左到右的顺序依次进入队列…最后按照层级输出了全部节点。

回过头来再对比下层级遍历的实现和前序遍历的非递归实现1，会发现两处代码非常对称，只是在暂存节点选择的结构上，层级遍历用了队列，前序遍历的非递归实现1用了栈，以及压入左右节点的顺序正好相反。

综上，本文详细对比介绍了树的几种遍历方式，同时对比了递归和非递归的实现。从中可以发现，只要理清楚了树的最小单元的处理，把握好终止条件，推而广之，不管是采用递归还是循环，都能够优雅的遍历树的所有节点。

参考：

https://zh.wikipedia.org/w/index.php?title=%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2&oldid=50694063

https://zh.wikipedia.org/w/index.php?title=%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2&oldid=50946557

http://biaobiaoqi.github.io/blog/2013/04/27/travsal-binary-tree/