二叉树的遍历

这期视频我们看一下如何遍历二叉树。

遍历二叉树是指从根节点开始，访间树中所有的节点。它是其它一些算法的基础，例如深度优先搜索。

对于二叉树、每个节点有左右两个子节点，对于是先访问左子节点、还是当前节点，或是右子节点，可以把遍历分为前序中序和后序三种。接下来我们分别看一下这三种形式。

先看前序遍历，前序遍历会先访问当前节点的值，之后访问左子节点或右子节点，这里假定先访问左子节点，然后再访问右子节点，对于每个子节点都是做同样的操作。

中序遍历则是先访问左子节点，再访问当前节点，最后访问右子节点，对于每个子节点也是重复这个过程。

后序遍历则是先访问左子节点的值，再访问右子节点的值，最后访问当前节点的值。对于每个子节点也是同样的操作。

二叉树遍历的代码实现，最简单直观的方法就是使用递归。

对于前序遍历，我们先打印出当前节点的值，然后递归的调用自己，传递左节点，再调用自己传递右节点。当子节点为 null 时退出递归。

traversePreOrder(treeNode) {
  if (!treeNode) {
    return;
  }

  console.log(treeNode.value);
  this.traversePreOrder(treeNode.left);
  this.traversePreOrder(treeNode.right);
}

中序遍历只需要把打印当前节点的代码放到中间就可以了。

  traverseInOrder(treeNode) {
    if (!treeNode) {
      return;
    }

    this.traverseInOrder(treeNode.left);
    console.log(treeNode.value);
    this.traverseInOrder(treeNode.right);
  }

后序遍历则是放到末尾。

  traversePostOrder(treeNode) {
    if (!treeNode) {
      return;
    }

    this.traversePostOrder(treeNode.left);
    this.traversePostOrder(treeNode.right);
    console.log(treeNode.value);
  }

我们来看一下前序遍历的例子，把调用栈显示出来方便查看递归情况。

假如有这样一棵二叉树需要遍历。

tree.traversePreOrder(root);

traversePreOrder(treeNode) {
    if (!treeNode) {
      return;
    }

    console.log(treeNode.value);
    this.traversePreOrder(treeNode.left);
    this.traversePreOrder(treeNode.right);
  }

代码：

1. 调用 traversePreOrder() 遍历 root | [traversePreOrder(13)]
2. 第一行先打印出根节点的值 13。| [traversePreOrder(13)]
3. 接下来，执行到遍历左节点的方法 traversePreOrder(6)，放入调用栈并执行，打印出 6，此时因为遍历左节点的方法还未 return，所以遍历右子节点的函数调用还不能执行 | 调用栈：[traversePreOrder(6), traversePreOrder(13)]。
4. 接着，递归调用 traversePreOrder() 遍历 6 的左子节点，函数压入调用栈并执行，打印出 3 | 调用栈：[traversePreOrder(3), traversePreOrder(6), traversePreOrder(13) ]。
5. 接着递归调用 traversePreOrder(treeNode.left) 遍历 3 的左子节点|调用栈：[traversePreOrder(null)，traversePreOrder(3), traversePreOrder(6) , traversePreOrder(13)]
6. 此时，执行 traversePreOrder(null)，treeNode 为 null，函数执行到 if 后，直接 return 了|调用栈：[traversePreOrder(3), traversePreOrder(6) , traversePreOrder(13)]
7. 那么接下来就从调用栈拿出最顶部的函数 traversePreOrder(3)，继续执行，调用 traversePreOrder(treeNode.right) |调用栈：[traversePreOrder(null), traversePreOrder(3), traversePreOrder(6) , traversePreOrder(13)]
8. treeNode.right 也是 null，所以函数直接返回 |调用栈：[ traversePreOrder(3), traversePreOrder(6) , traversePreOrder(13)]。
9. 接着继续执行 traversePreOrder(3)，后面没有代码了，所以 traversePreOrder(3) 函数返回。| [ traversePreOrder(6) , traversePreOrder(13)]
10. 接着执行 traversePreOrder(6)，调用它里边的 traversePreOrder(treeNode.right) | [traversePreOrder(9), traversePreOrder(6) , traversePreOrder(13)]。
11. 执行打印出 9 | 调用栈 [traversePreOrder(9), traversePreOrder(6) , traversePreOrder(13)]。
12. 接着调用 9 里的 traversePreOrder(treeNode.left) | [traversePreOrder(7), traversePreOrder(9), traversePreOrder(6) , traversePreOrder(13)]。
13. 执行打印出 7。后面它没有子节点，所以它里边的 traversePreOrder(treeNode.left) 和 traversePreOrder(treeNode.right) 直接返回，这里就不演示，它本身到这里也执行结束了。| [traversePreOrder(9), traversePreOrder(6) , traversePreOrder(13)]。
14. 又回到节点 9，它没有右节点，所以也执行结束并返回。| [traversePreOrder(6) , traversePreOrder(13)]。
15. 到了 traversePreOrder(6)，它的代码也执行完毕了，返回。| [ traversePreOrder(13)]
16. 现在开始继续执行 13 根节点的 traversePreOrder(treeNode.right) 方法了，这里边的执行顺序和之前一样，我们简单过一下。
17. 调用 traversePreOrder(20) 打印出 20 | [traversePreOrder(20), traversePreOrder(13)]。
18. 遍历左节点并打印出 15。 | [traversePreOrder(15), traversePreOrder(20), traversePreOrder(13)]。
19. 15 没有子节点直接返回，遍历 20 的右节点，打印出 28。| [traversePreOrder(28), traversePreOrder(20), traversePreOrder(13)]。
20. 28 没有左子节点，遍历右子节点，打印出 32 并返回。| [traversePreOrder(32), traversePreOrder(20), traversePreOrder(13)]。
21. 20 节点遍历完毕并返回。| [traversePreOrder(13)]。
22. 13 根节点遍历完毕并返回 | []。

此时，前序遍历就完成了，结果是：

13  6  3  9  7  20  15 28  32

再看中序遍历：

tree.traverseInOrder(root);

  traverseInOrder(treeNode) {
    if (!treeNode) {
      return;
    }

    this.traverseInOrder(treeNode.left);
    console.log(treeNode.value);
    this.traverseInOrder(treeNode.right);
  }

这里简单过一下：

1. 调用 traverseInOrder(root) 开始遍历根节点 13 | [traverseInOrder(13)]。
2. 这里注意，traverseInOrder() 的第一行代码不再是 console.log()，而是直接调用 traverseInOrder(treeNode.left) 遍历左子节点。
3. 调用 traverseInOrder(treeNode.left) 遍历 6。| [traverseInOrder(6), traverseInOrder(13)]。
4. 调用节点 6 的 traverseInOrder(treeNode.left) ，遍历 3，| [traverseInOrder(3), traverseInOrder(6), traverseInOrder(13)]。
5. 3 里边没有子节点，所以它调用 traverseInOrder(treeNode.left)，直接返回，这里调用栈就不演示了。
6. 执行 console.log 打印出 3，之后调用 traverseInOrder(treeNode.right) 也是直接返回，此时遍历 3 完成。| [traverseInOrder(6), traverseInOrder(13)]。
7. 接着继续执行 traverseInOrder(6)，打印出 6， 遍历它的右子节点 9。| [traverseInOrder(9), traverseInOrder(6), traverseInOrder(13)]。
8. 遍历 9 的左子节点 7 | [traverseInOrder(7), traverseInOrder(9), traverseInOrder(6), traverseInOrder(13)]。
9. 7 没有子节点，所以遍历左子节点直接返回，再打印出 7，遍历右子节点直接返回，遍历 7 节点完成。| [traverseInOrder(9), traverseInOrder(6), traverseInOrder(13)]。
10. 继续执行 traverseInOrder(9), 打印出 9，9 没有右子节点，所以遍历完成。| [traverseInOrder(6), traverseInOrder(13)]。
11. 6 遍历完成。| [traverseInOrder(13)]。
12. 继续执行 traverseInOrder(13)，打印出 13。
13. 遍历它的右子节点 20 。 | [traverseInOrder(20)， traverseInOrder(13)]。
14. 遍历 20 的左子节点 15。| [traverseInOrder(15)，traverseInOrder(20)， traverseInOrder(13)]。
15. 15 没有子节点，打印出 15，并返回。| [traverseInOrder(20)， traverseInOrder(13)]。
16. 继续执行 traverseInOrder(20)，打印出 20，遍历右子节点 28：| [traverseInOrder(28)，traverseInOrder(20)， traverseInOrder(13)]。
17. 28 没有左子节点，打印出 28，遍历右子节点 32 | [traverseInOrder(32)， traverseInOrder(28)，traverseInOrder(20)， traverseInOrder(13)]。
18. 打印出 32，后面所有的函数就都执行完毕并返回了。

中序遍历的结果就是：

3  6  7  9  13  15  20  28  32

再看后序遍历：

tree.traversePostOrder(root)

  traversePostOrder(treeNode) {
    if (!treeNode) {
      return;
    }

    this.traversePostOrder(treeNode.left);
    this.traversePostOrder(treeNode.right);
    console.log(treeNode.value);
  }

1. 遍历根节点 13， | [traversePostOrder(13)]。
2. 遍历 13 的 左子节点 6。| [traversePostOrder(6), traversePostOrder(13)]。
3. 遍历 6 的左子节点 3。
4. 3 没有子节点，打印出 3，并返回。
5. 继续执行 traversePostOrder(6)，遍历右子节点 9。
6. 遍历 9 的左子节点 7.
7. 7 没有子节点，打印出 7 并返回。
8. 继续执行 traversePostOrder(9)，9 没有右子节点，打印出 9 并返回。
9. 继续执行 traversePostOrder(6)，打印出 6，返回。
10. 继续执行 traversePostOrder(13)，遍历右子节点 20。
11. 遍历 20 的左子节点 15。
12. 15 没有子节点，打印出 15，并返回。
13. 遍历 20 的右子节点，28。
14. 28 没有左子节点，遍历 28 的右子节点 32.
15. 32 没有子节点，打印出 32 之后返回。
16. 继续执行 traversePostOrder(28)，打印出 28，返回。
17. 继续执行 traversePostOrder(20)，打印出 20，返回。
18. 继续执行 traversePostOrder(13)，打印出 13，返回。

这样，后序遍历就完成了，结果是：

3  7  9  6  15  32  28  20  13

小结

好了，这个就是二叉树的前序、中序和后序遍历过程，利用递归，调整 console.log 也就是遍历节点相关的逻辑，就可以快速的实现三种次序的遍历过程。你学会了吗？如果有帮助请三连，想学更多有用的前端开发知识，请关注峰华前端工程师，感谢观看！