算法系列-二叉树遍历(非递归实现)
在内卷潮流的席卷下，身为算法小白的我不得不问自己，是否得踏上征程，征服这座巍巍高山。
从零开始，终点不知何方，取决于自己可以坚持多久。
希望你可以和我一样，克服恐惧，哪怕毫无基础，哪怕天生愚钝，依然选择直面困难。
数据结构分类
队列
栈
前言
本篇作为二叉树遍历的下篇，我们主要分析如何通过非递归的方式实现二叉树的遍历。
有对二叉树不了解或单纯想知道二叉树的遍历实现的同学，建议先阅读算法系列-二叉树遍历
二叉树的遍历
概念不多说，我们直接进入算法学习。
二叉树的第一个算法就是遍历算法，而遍历又分为深度优先算法，广度优先算法。其中深度优先算法又分为前序，中序，后序优先。
深度优先遍历
前序遍历
中序遍历
后序遍历
广度优先遍历
下文的代码我们将以下面的二叉树为例，先用树结构来描述它。
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) => { const stack = [node] while(stack.length) { const node = stack.pop() console.log(node.value) if (node.right) { stack.push(node.right) } if (node.left) { stack.push(node.left) } } } 复制代码解释一下
我们借用了数据结构栈，先访问根节点，再往栈内推入右节点，左节点，在下一轮循环中则是利用出栈先访问左节点。
中序遍历
中序遍历的中序是相对根节点来说的，即访问顺序为
左节点 -> 根节点 -> 右节点
此时，我们的访问顺序依次为
D -> B -> E -> A -> F -> C -> G
const inOrder = (node) => { const stack = [node]; while(stack.length) { const node = stack.pop() if (node.visited) { console.log(node.value) delete node.visited continue } node.visited = true if (node.right) { stack.push(node.right) } stack.push(node) if (node.left) { stack.push(node.left) } } } 复制代码中序遍历我我们同样使用了栈结构，与前序遍历相比其难点在于我们无法在遇到当前节点时就访问其值，因为我们必须先访问左节点。所以我们这边利用了额外的属性 visited 来标记其，再次访问时则直接访问其值则可。
刚开始的时候一直想不出如何绕过根节点的访问，因为自己觉得不应该往节点添加数据。后面看了别人的实现才发现也是通过额外属性标记实现了，所以也效仿了别人的做法。
当然，后面我又找到了没有引入额外属性的实现方式，果然还是自己太愚蠢了，没有想到 node.left 到 node.right 的转化。
const inOrder = (node) => { const stack = [node]; while(stack.length) { // 先遍历左节点 if (node) { stack.push(node) node = node.left } else { node = stack.pop() console.log(node.value) // 重点在于这 将node转移到右节点 node = node.right } } } 复制代码此算法的利用了左节点同时为根节点的特性，使得我们完成了 左节点 -> 根节点 的遍历，后面在根节点处又使用了 node = node.right 将当前遍历转移到右节点，非常巧妙，这大概就是我想破头没想出来的原因吧！
后序遍历
后序遍历的后序是相对根节点来说的，即访问顺序为
左节点 -> 右节点 -> 根节点
此时，我们的访问顺序依次为
D -> E -> B -> F -> G -> C -> A
const postOrder = (node) => { const stack = [node] while(stack.length) { const node = stack.pop() if (node.visited) { delete node.visited console.log(node.value) continue } node.visited = true stack.push(node) if (node.right) { stack.push(node.right) } if (node.left) { stack.push(node.left) } } } 复制代码实现逻辑和中序遍历相似，这边就不重复解释了
同样，我们来看看另外一种不加额外属性的实现方式
const postOrder = (node) => { const s1 = [node] const s2 = [] while (s1.length) { node = s1.pop() s2.push(node) if (node.left) { s1.push(node.left) } if (node.right) { s1.push(node.right) } } while(s2.length) { console.log(s2.pop().value) } } 复制代码此解法利用了两个栈来实现后序遍历是我万万想不到的，但是如果仔细分析可以发现实际和先序遍历的实现有些相似。
是的，它们本来就是比较相似的两种顺序，先序是 根节点 -> 左右子节点，后序是 左右子节点 -> 根节点
所以多加分析可以发现 s1 实际是模仿先序的实现，s2 则用于反转访问。也就是 s1 实现栈递归，s2 实现访问节点存储。
PS：u1s1，让我想真想不出来
广度优先遍历
相对而言，广度优先遍历会麻烦一些，我们称其为 BFS（Breath First Search） 广度优先搜索。
广度优先遍历也叫层次遍历，即访问顺序为一层一层地访问。
在本例子中，访问先后顺序为 A -> B -> C -> D -> E -> F -> G
const BFS = (nodes) => { for (let i = 0; i < list.length; i++) { const curNode = list[i] const { left, right, value } = curNode console.log(value); if (left) { list.push(left) } if (right) { list.push(right) } } } 复制代码利用迭代实现广度优先反而比深度优先来的简单一些，原理就是利用数据结构队列，先遍历当前层，再将下层节点加入队列中，最后实现按层按顺序遍历。
总结
本篇文章作为上篇文章的续篇，通过代码演示了如何通过迭代的方式遍历二叉树，与递归实现相比，会显得稍微复杂一些。好吧，实际不止一些。
既然递归简单，并且听起来也比较高大上一些，那我们为什么还要研究迭代方式实现呢，其原因在于递归的性能实际是比较差的，感兴趣的朋友们可以去网上搜索相关知识了解下。
对于二叉树的算法实际还有很多，比如根据遍历结构来生成二叉树，也许我们下篇文章会对二叉树的生成算法进行研究。
作者：沐晓
链接：https://juejin.cn/post/7043058642479742984