在内卷潮流的席卷下，身为算法小白的我不得不问自己，是否得踏上征程，征服这座巍巍高山。
从零开始，终点不知何方，取决于自己可以坚持多久。
希望你可以和我一样，克服恐惧，哪怕毫无基础，哪怕天生愚钝，依然选择直面困难。
算法分类
- 递归算法
前言
本篇作为算法系列的开篇，我们将学习二叉树相关算法。
本篇文章的遍历实现采用递归算法。
二叉树
我们先了解下树的概念
树是一种非线性的数据结构，以分层的方式存储数据。常见的树结构有家庭关系图谱，公司组织结构。
我们所说二叉树则是一种特殊的树，它的子节点不超过两个。
二叉树的遍历
概念不多说，我们直接进入算法学习。
二叉树的第一个算法就是遍历算法，而遍历又分为深度优先算法，广度优先算法。其中深度优先算法又分为前序，中序，后序优先。
- 深度优先遍历
- 前序遍历
- 中序遍历
- 后序遍历
- 广度优先遍历
下文的代码我们将以下面的二叉树为例，先用树结构来描述它。
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 优先处理同层节点，与此同时需要提取下一层次节点
总结
今天我们梳理了二叉树的遍历，我们例子中的二叉树比较特殊，其左右节点完全对称且每个非叶子节点都拥有左右子节点。我们称之为完全二叉树。通过二叉树的遍历，我们掌握了在开发中最常用的算法之一递归算法。
但是如果说二叉树的遍历只有递归算法，那我可就不太同意了。只是递归算法比较符合我们的思维，其拆解问题的思路也相对简单，所以我们优先使用了递归算法，我们将在下一篇文章来学习下，二叉树遍历的非递归实现。
