JavaScript中的树型数据结构
实现和遍历技术
作者：Anish Kumar 译者：同学小强 起源：stackfull
Tree 是一种乏味的数据结构，它在各个领域都有宽泛的利用，例如:
- DOM 是一种树型数据结构
- 咱们操作系统中的目录和文件能够示意为树
- 家族层次结构能够示意为一棵树
树有很多变体(如堆、 BST 等) ，可用于解决与调度、图像处理、数据库等相干的问题。许多简单的问题可能看起来和树没有关系，然而实际上能够示意为一个问题。咱们还将探讨这些问题(在本系列前面的局部中) ，看看树是如何使看似简单的问题更容易了解和解决的。
引言
为二叉树实现一个节点是非常简单的。
function Node(value){ this.value = value this.left = null this.right = null}// usageconst root = new Node(2)root.left = new Node(1)root.right = new Node(3)因而，这几行代码将为咱们创立一个二叉树，它看起来像这样:
2 / \ / \ 1 3 / \ / \null null null null这很简略。当初，咱们如何应用这个呢？
遍历
让咱们从试图遍历这些连贯的树节点(或整颗树)开始。就像咱们能够迭代一个数组一样，如果咱们也能够“迭代”树节点就更好了。然而，树并不是像数组那样的线性数据结构，因而遍历这些数据结构的办法不止一种。咱们能够将遍历办法大抵分为以下几类:
- 广度优先遍历
- 深度优先遍历
广度优先搜寻/遍历（BFS）
在这种办法中，咱们逐层遍历树。咱们将从根开始，而后笼罩所有的子级，以及笼罩所有的二级子级，以此类推。例如，对于下面的树，遍历会失去如下后果:
2, 1, 3上面是一个稍微简单的树的例子，使得这个更容易了解:
要实现这种模式的遍历，咱们能够应用一个队列（先进先出）数据结构。上面是整个算法的样子:
- 初始化一个蕴含 root 的队列
- 从队列中删除第一项
- 将弹出项的左右子项推入队列
- 反复步骤2和3，直到队列为空
上面是这个算法实现后的样子:
function walkBFS(root){ if(root === null) return const queue = [root] while(queue.length){ const item = queue.shift() // do something console.log(item) if(item.left) queue.push(item.left) if(item.right) queue.push(item.right) }}咱们能够略微批改下面的算法来返回一个二维数组，其中每个外部数组代表一个蕴含元素的层级：
function walkBFS(root){ if(root === null) return const queue = [root], ans = [] while(queue.length){ const len = queue.length, level = [] for(let i = 0; i < len; i++){ const item = queue.shift() level.push(item) if(item.left) queue.push(item.left) if(item.right) queue.push(item.right) } ans.push(level) } return ans}深度优先搜寻/遍历（DFS）
在 DFS 中，咱们取一个节点并持续摸索它的子节点，直到深度达到齐全耗尽。这能够通过以下办法之一来实现:
root node -> left node -> right node // pre-order traversal left node -> root node -> right node // in-order traversal left node -> right node -> root node // post-order traversal所有这些遍历技术都能够迭代和递归形式实现，让咱们进入实现细节:
前序遍历
上面是一颗树的前序遍历的样子:
root node -> left node -> right node窍门：
咱们能够应用这个简略的技巧手动地找出任何树的前序遍历: 从根节点开始遍历整个树，放弃本人在右边。
实现：
让咱们深入研究这种遍历的理论实现。 递归办法 相当直观。
function walkPreOrder(root){ if(root === null) return // do something here console.log(root.val) // recurse through child nodes if(root.left) walkPreOrder(root.left) if(root.right) walkPreOrder(root.right)}前序遍历的迭代办法与 BFS 十分类似，不同之处在于咱们应用堆栈而不是队列，并且咱们首先将左边的子元素放入堆栈:
function walkPreOrder(root){ if(root === null) return const stack = [root] while(stack.length){ const item = stack.pop() // do something console.log(item) // Left child is pushed after right one, since we want to print left child first hence it must be above right child in the stack if(item.right) stack.push(item.right) if(item.left) stack.push(item.left) }}中序遍历
上面是一颗树的中序遍历的样子:
left node -> root node -> right node窍门：
咱们能够应用这个简略的技巧手动地找出任何树的中序遍历: 在树的底部程度搁置一个平面镜像，并对所有节点进行投影。
实现：
递归：
function walkInOrder(root){ if(root === null) return if(root.left) walkInOrder(root.left) // do something here console.log(root.val) if(root.right) walkInOrder(root.right)}迭代: 这个算法起初可能看起来有点神秘。但它相当直观的。让咱们这样来看: 在中序遍历中，最右边的子节点首先被打印，而后是根节点，而后是右节点。所以咱们首先想到的是:
const curr = rootwhile(curr){ while(curr.left){ curr = curr.left // get to leftmost child } console.log(curr) // print it curr = curr.right // now move to right child}在上述办法中，咱们无奈回溯，即返回到最左侧节点的父节点，所以咱们须要一个堆栈来记录它们。因而，咱们订正后的办法可能看起来如下:
const stack = []const curr = rootwhile(stack.length || curr){ while(curr){ stack.push(curr) // keep recording the trail, to backtrack curr = curr.left // get to leftmost child } const leftMost = stack.pop() console.log(leftMost) // print it curr = leftMost.right // now move to right child}当初咱们能够应用下面的办法来制订最终的迭代算法:
function walkInOrder(root){ if(root === null) return const stack = [] let current = root while(stack.length || current){ while(current){ stack.push(current) current = current.left } const last = stack.pop() // do something console.log(last) current = last.right }}后序遍历
上面是一颗树的后序遍历的样子:
left node -> right node -> root node窍门：
对于任何树的疾速手动后序遍历：一个接一个地提取所有最右边的叶节点。
实现：
让咱们深入研究这种遍历的理论实现。
递归：
function walkPostOrder(root){ if(root === null) return if(root.left) walkPostOrder(root.left) if(root.right) walkPostOrder(root.right) // do something here console.log(root.val)}迭代：咱们曾经有了用于前序遍历的迭代算法。 咱们能够用那个吗？ 因为后序遍历仿佛只是前序遍历的逆序。 让咱们来看看：
// PreOrder:root -> left -> right// Reverse of PreOrder:right -> left -> root// But PostOrder is:left -> right -> root这里有一个轻微的区别。然而咱们能够通过略微批改前序算法，而后对其进行逆序，从而失去后序后果。总体算法如下:
// record result using root -> right -> left// reverse resultleft -> right -> root应用与下面的迭代前序算法相似的办法，应用长期
堆栈。- 惟一的例外是咱们应用
root-> right-> left而不是root-> left-> right
- 惟一的例外是咱们应用
- 将遍历序列记录在一个数组
后果中 后果的逆序给出了后序遍历
function walkPostOrder(root){ if(root === null) return [] const tempStack = [root], result = [] while(tempStack.length){ const last = tempStack.pop() result.push(last) if(last.left) tempStack.push(last.left) if(last.right) tempStack.push(last.right) } return result.reverse()}额定：JavaScript 提醒
如果咱们能够通过以下形式遍历树该多好：
for(let node of walkPreOrder(tree) ){ console.log(node) }看起来真的很好，而且很容易浏览，不是吗？ 咱们所要做的就是应用一个 walk 函数，它会返回一个迭代器。
以下是咱们如何批改下面的 walkPreOrder 函数，使其依照下面共享的示例运行：
function* walkPreOrder(root){ if(root === null) return const stack = [root] while(stack.length){ const item = stack.pop() yield item if(item.right) stack.push(item.right) if(item.left) stack.push(item.left) }}举荐理由
本文（配有多图）介绍了树结构在 JavaScript 语言外面如何遍历，写得浅显易懂，解释了广度优先、深度优先等多种办法的实现，翻译不免有出入，欢送斧正！
原文：https://stackfull.dev/tree-da...
往期精彩
不必递归生成有限层级的树
基于qiankun微前端实战部署