JavaScript中的树数据结构实现与遍历技术作者：AnishKumar译者：小强同学来源：stackfullTree是一个有趣的数据结构，在各个领域有着广泛的应用，例如：DOMis一个树型的数据结构，我们操作系统中的目录和文件可以表示为一个树族层次结构可以表示为一棵树树有很多变体（如堆，BST等），可以用来求解和调度、图像处理、数据库等相关问题。很多复杂的问题看似与树无关，但实际上可以表述为一个问题。我们还将讨论这些问题（在本系列的后面部分）并了解树如何使看似复杂的问题更容易理解和解决。简介为二叉树实现节点非常简单。functionNode(value){this.value=valuethis.left=nullthis.right=null}//usageconstroot=newNode(2)root.left=newNode(1)root.right=newNode(3)因此，这几行代码将为我们创建一个如下所示的二叉树：2/\/\13/\/\nullnullnullnull这非常简单。现在，我们如何使用它？遍历让我们从尝试遍历这些连接的树节点（或整棵树）开始。就像我们可以遍历数组一样，如果我们也可以“遍历”树节点就好了。然而，树并不是像数组那样的线性数据结构，因此遍历这些数据结构的方法不止一种。我们大致可以将遍历方法分为以下几类：广度优先遍历深度优先遍历广度优先搜索/遍历（BFS）在这种方法中，我们逐层遍历树。我们将从根开始，然后覆盖所有子级和所有二级子级，依此类推。例如，对于上面的树，遍历将产生以下结果：2,1,3下面是一个稍微复杂的树的示例，以便于理解：要实现这种形式的遍历，我们可以使用队列（先进先出）数据结构。整个算法如下所示：初始化一个包含根的队列从队列中删除第一项将弹出窗口的左右子项推入队列重复步骤2和3直到队列为空这是算法完成后的样子实现：functionwalkBFS(root){if(root===null)returnconstqueue=[root]while(queue.length){constitem=queue.shift()//做一些事情console.log(item)if(item.left)queue.push(item.left)if(item.right)queue.push(item.right)}}我们可以稍微修改上面的算法返回一个二维数组，其中每个内部数组代表一个层次结构包含元素：functionwalkBFS(root){if(root===null)returnconstqueue=[root],ans=[]while(queue.length){constlen=queue.length,level=[]for(leti=0;i左节点->右节点//前序遍历左节点->根节点->右节点//中序遍历左节点->右节点->rootnode//post-ordertraversal所有这些遍历技术都可以迭代和递归地实现，让我们进入实现细节：pre-ordertraversal下面是树的pre-ordertraversal看起来像：rootnode->leftnode->rightnodetrick：我们可以使用这个简单的技巧手动找出任何树的前序遍历：从根节点开始并遍历整个树，保持我们自己在左边。实现：让我们深入研究这个遍历的实际实现。递归方法相当直观。functionwalkPreOrder(root){if(root===null)return//在这里做点什么console.log(root.val)//通过子节点递归if(root.left)walkPreOrder(root.left)if(root.right)walkPreOrder(root.right)}前序遍历的迭代方式和BFS很相似，不同的是我们用的是栈而不是队列，我们??先把右边的子元素入栈：functionwalkPreOrder(root){if(root===null)returnconststack=[root]while(stack.length){constitem=stack.pop()//做一些事情console.log(item)//左孩子在右孩子之后被压入，因为我们想先打印左孩子，因此它必须在堆栈中的右孩子之上if(item.right)stack.push(item.right)if(item.left)stack.push(item.left)}}Inordertraversal下面是树的中序遍历：左节点->根节点->右节点技巧：我们可以手动找出任何树的中序遍历使用这个简单的技巧：在树镜像的底部水平放置一个平面并投影所有节点。实现：递归：functionwalkInOrder(root){if(root===null)returnif(root.left)walkInOrder(root.left)//dosomethinghereconsole.log(root.val)if(root.right)walkInOrder(root.right)}iterations：这个算法起初看起来有点神秘。但它相当直观。让我们这样看：在中序遍历中，首先打印最左边的孩子，然后是根节点，然后是右节点。所以我们的第一个想法是：constcurr=rootwhile(curr){while(curr.left){curr=curr.left//到达最左边的孩子}console.log(curr)//打印它curr=curr.right//nowmovetorightchild}在上面的方法中，我们不能回溯，即回到最左边节点的父节点，所以我们需要一个栈来记录它们。所以我们修改后的方法可能看起来像这样：conststack=[]constcurr=rootwhile(stack.length||curr){while(curr){stack.push(curr)//继续记录轨迹，回溯curr=curr.left//到最左边的孩子}constleftMost=stack.pop()console.log(leftMost)//打印它curr=leftMost.right//现在移到右边的孩子}现在我们可以使用上面的方法来制定最后一个迭代算法：current=current.left}constlast=stack.pop()//dosomethingconsole.log(last)current=last.right}}后序遍历下面是树的后序遍历：->右节点->根节点诀窍：对于任何树的快速手动后序遍历：一个一个地提取所有最左边的叶节点。实现：让我们深入研究这个遍历的实际实现。递归：functionwalkPostOrder(root){if(root===null)returnif(root.left)walkPostOrder(root.left)if(root.right)walkPostOrder(root.right)//在这里做点什么console.log(root.val)}迭代：我们已经有了一个用于前序遍历的迭代算法。我们可以用那个吗？由于后序遍历似乎只是前序遍历的逆过程。让我们看看：//PreOrder:root->left->right//PreOrder的逆序：right->left->root//但PostOrder是：left->right->root这里有一个细微的区别。但是我们可以通过对前序算法稍作修改，然后逆向得到后序结果。整体算法如下：//recordresultusingroot->right->left//reverseresultleft->right->root使用了类似上面迭代预序算法的方法，使用临时栈。唯一的例外是我们使用root->right->left而不是root->left->right来记录数组中的遍历顺序Result结果的倒序给出后序遍历函数walkPostOrder(root){if(root===null)return[]consttempStack=[root],result=[]while(tempStack.length){constlast=tempStack.弹出（）结果。push(last)if(last.left)tempStack。push(last.left)if(last.right)tempStack.push(last.right)}returnresult.reverse()}额外：JavaScript提示(tree)){console.log(node)}看起来非常好并且易??于阅读，不是吗？我们所要做的就是使用一个返回迭代器的遍历函数。以下是我们如何修改上面的walkPreOrder函数，使其表现得像上面共享的示例：.pop()yielditemif(item.right)stack.push(item.right)if(item.left)stack.push(item.left)}}推荐理由JavaScript语言中如何遍历结构，写法以通俗易懂的方式，讲解了广度优先、深度优先等各种方法的实现。翻译难免有出入，欢迎指正！原文：https://stackfull.dev/tree-da...以前不需要递归生成无穷多层次的树。基于乾坤微前端的实际部署
