算法系列-二叉树遍历

在内卷潮流的席卷下，身为算法小白的我不得不问自己，是否得踏上征程，征服这座巍巍高山。

从零开始，终点不知何方，取决于自己可以坚持多久。

希望你可以和我一样，克服恐惧，哪怕毫无基础，哪怕天生愚钝，依然选择直面困难。

算法分类

• 递归算法

前言

本篇作为算法系列的开篇，我们将学习二叉树相关算法。

本篇文章的遍历实现采用递归算法。

二叉树

我们先了解下树的概念

树是一种非线性的数据结构，以分层的方式存储数据。常见的树结构有家庭关系图谱，公司组织结构。

我们所说二叉树则是一种特殊的树，它的子节点不超过两个。

二叉树的遍历

概念不多说，我们直接进入算法学习。

二叉树的第一个算法就是遍历算法，而遍历又分为深度优先算法，广度优先算法。其中深度优先算法又分为前序，中序，后序优先。

• 深度优先遍历

• 前序遍历
  
• 中序遍历
  
• 后序遍历
  

• 广度优先遍历
  

下文的代码我们将以下面的二叉树为例，先用树结构来描述它。

const tree = {
  value: 'A',
  left: {
    value: 'B',
    left: {
      value: 'D',
    },
    right: {
      value: 'E'
    }
  },
  right: {
    value: 'C',
    left: {
      value: 'F',
    },
    right: {
      value: 'G'
    }
  }
}
复制代码

深度优先遍历

深度优先即先访问子节点，直到叶子结点。

我们称深度优先遍历为 DFS（Deep First Search） 深度优先搜索。

前序遍历

前序遍历的前序是相对根节点来说的，即访问顺序为

根节点 -> 左节点 -> 右节点

此时，我们的访问顺序依次为

A -> B -> D -> E -> C -> F -> G

const preOrder = (node) => {
  console.log(node.value)
  if (node.left) {
    preOrder(node.left)
  }
  if (node.right) {
    preOrder(node.right)
  }
}
复制代码

我们使用的是递归算法，先访问根节点，则先访问根节点，再处理左右节点即可。

中序遍历

中序遍历的中序是相对根节点来说的，即访问顺序为

左节点 -> 根节点 -> 右节点

此时，我们的访问顺序依次为

D -> B -> E -> A -> F -> C -> G

const inOrder = (node) => {
  if (node.left) {
    inOrder(node.left)
  }
  console.log(node.value)
  if (node.right) {
    inOrder(node.right)
  }
}
复制代码

我们使用的是递归算法，先访问左节点，则先处理左节点，再访问根节点，最后处理右节点即可。

后序遍历

后序遍历的后序是相对根节点来说的，即访问顺序为

左节点 -> 右节点 -> 根节点

此时，我们的访问顺序依次为

D -> E -> B -> F -> G -> C -> A

const postOrder = (node) => {
  if (node.left) {
    postOrder(node.left)
  }
  if (node.right) {
    postOrder(node.right)
  }
  console.log(node.value)
}
复制代码

我们使用的是递归算法，先处理左节点，再处理右节点，最后访问根节点。

深度优先遍历总结

不管前序遍历，中序遍历，后序遍历，其实都是非常相似的。他们的区别仅仅在于处理节点的顺序不同，只要掌握了其中一种，其它的也就依葫芦画瓢即可。

有些同学对不同访问顺序的访问先后可能不太明白，比如不知道前序遍历应该依次访问 A -> B -> D -> E -> C -> F -> G，这个只能通过多加分析训练了。

我们需要 get 其中一个点，对于前序，中序，后序遍历来说，对于每个节点都是如此，如后序遍历，B -> ... -> C -> A，即使它们不相邻。

广度优先遍历

深度优先遍历的实现属于比较简单的，其很符合递归算法的思路，将大问题拆解为小问题，先处理小问题。

相对而言，广度优先遍历会麻烦一些，我们称其为 BFS（Breath First Search） 广度优先搜索。

广度优先遍历也叫层次遍历，即访问顺序为一层一层地访问。

在本例子中，访问先后顺序为 A -> B -> C -> D -> E -> F -> G

const BFS = (nodes) => {
  // 既然要按层次遍历
  // 那我们的思路就是提前梳理下一层的节点
  const nextNodes = []
  for (let i = 0, len = nodes.length; i < len; i++) {
    const node = nodes[i]
    const { value, left, right } = node
    // 按照顺序先访问当前层次节点
    console.log(value)
    // 提取下一节点
    if (left) {
      nextNodes.push(left)
    }
    if (right) {
      nextNodes.push(right)
    }
  }
  // 递归访问下一层次节点
  if (nextNodes.length) {
    BFS(nextNodes)
  }
}
复制代码

BFS 的实现会比 DFS 复杂一些，但相信通过函数实现中的注释，大家还是可以弄明白的。

我们认真思考一下，其实可以发现一些原理

• 
  
• DFS 专注于处理单个节点，包括其左节点，右节点
  
• 
  
• BFS 优先处理同层节点，与此同时需要提取下一层次节点
• 
  

总结

今天我们梳理了二叉树的遍历，我们例子中的二叉树比较特殊，其左右节点完全对称且每个非叶子节点都拥有左右子节点。我们称之为完全二叉树。通过二叉树的遍历，我们掌握了在开发中最常用的算法之一递归算法。

但是如果说二叉树的遍历只有递归算法，那我可就不太同意了。只是递归算法比较符合我们的思维，其拆解问题的思路也相对简单，所以我们优先使用了递归算法，我们将在下一篇文章来学习下，二叉树遍历的非递归实现。