按照顺序规则的不同，遍历方式有以下四种：

1. 先序遍历
2. 中序遍历
3. 后序遍历
4. 层次遍历

按照实现方式的不同，遍历方式可分为：

1. 递归遍历（先、中、后序遍历）
2. 迭代遍历（层次遍历）

提示

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。

递归

递归简单来说就是函数自己调用自己。千万不要小看它，它是我们学习后续算法的基础，后面你所看到的算法基本都使用到了递归，所以你必须掌握它。

递归函数的编写要点:

• 递归式 - 指的是你每一次重复的内容是什么。
• 递归边界 - 指的是什么时候停下来

从上面寥寥数语来看，可能很难理解递归。递归确实很难理解，需要配合大量的习题才能真正理解。

这里我们摘抄一篇我认为对递归讲解不错的文章，详细请阅读 对于递归有没有什么好的理解方法 (opens new window)。

写递归之前要明确三个要素：

• 明确你写的这个函数是要干什么的；
• 寻找递归结束条件； 这句话的意思就是说当参数为什么的时候，递归结束，直接返回结果。此时，我们必须可以从这个参数中直接看出结果。
• 找出函数的等价关系式； 不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。

二叉树遍历

“先序”、“中序”和“后序”，“先”、“中”、“后”其实就是指根结点的遍历时机。

• 根结点 -> 左子树 -> 右子树
• 左子树 -> 根结点 -> 右子树
• 左子树 -> 右子树 -> 根结点

上面这三种顺序中，根结点的遍历分别被安排在了首要位置、中间位置和最后位置。

先序遍历

先序遍历的顺序：根结点 -> 左子树 -> 右子树

动画展示： 先序遍历代码如下：

const root = {
  val: "A",
  left: {
    val: "B",
    left: {
      val: "D"
    },
    right: {
      val: "E"
    }
  },
  right: {
    val: "C",
    right: {
      val: "F"
    }
  }
};

// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
  // 递归边界，root 为空
  if(!root) {
    return 
  }
    
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val)  
  // 递归遍历左子树 
  preorder(root.left)  
  // 递归遍历右子树  
  preorder(root.right)
}

中序遍历

中序遍历顺序：左子树 -> 根结点 -> 右子树

// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
  // 递归边界，root 为空
  if(!root) {
    return 
  }
    
  // 递归遍历左子树 
  inorder(root.left)  
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val)  
  // 递归遍历右子树  
  inorder(root.right)
}

后序遍历

后序遍历顺序：左子树 -> 右子树 -> 根结点

function postorder(root) {
  // 递归边界，root 为空
  if(!root) {
    return 
  }
    
  // 递归遍历左子树 
  postorder(root.left)  
  // 递归遍历右子树  
  postorder(root.right)
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val)  
}