树遍历是计算机科学中的一个基本概念，涉及系统地访问树数据结构中的每个节点。通过树遍历，我们可以按预定顺序处理节点，方便搜索、排序和评估表达式等操作。 在本文中，我们将探索三种最广泛使用的树遍历方法：中序、前序和后序。 通过用 JavaScript 实现的清晰简洁的示例，您将对这些遍历技术有深入的了解。 树结构定义 在深入研究树遍历算法之前，让我们定义将用于二叉树的结构。树将由节点组成，其中每个节点包含一个值和对其左右子节点的引用。   function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } 现在我们已经定义了树结构，我们可以继续探索三种树遍历方法。 中序遍历 中序遍历遵循二叉树中访问节点的下一个模式——算法首先遍历左子树，然后访问当前节点，最后遍历右子树。如果树表示排序的数据结构，这可确保按升序访问节点。  A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G 递归中序遍历 检查当前节点是否为空。如果是这样，返回。 递归调用左子树上的函数。 访问当前节点。 递归调用右子树上的函数。   function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; } 非递归中序遍历 初始化一个空栈，并将当前节点设置为树的根。 在堆栈不为空或当前节点不为空时进行迭代。 将所有左节点压入堆栈，直到到达一个空左子节点。 从栈中弹出一个节点，访问它，并将当前节点设置为它的右孩子。 重复步骤2，直到栈为空，当前节点为null。   function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; } 前序遍历 在前序遍历中，算法首先访问当前节点，然后遍历左子树，最后遍历右子树。这种排序确保以“自上而下”的方式访问节点，从根开始向叶子移动。  A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G 递归前序遍历 检查当前节点是否为空。如果是这样，返回。 访问当前节点。 递归调用左子树上的函数。 递归调用右子树上的函数。   function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; } 非递归前序遍历 从空栈开始，将根节点压入栈中。 初始化一个空数组来存放前序遍历结果。 输入一个 while 循环，直到堆栈为空。 从堆栈中弹出一个节点，并通过将其值添加到结果数组来访问它。 如果该节点有右孩子，则将右孩子压入堆栈。 如果节点有左孩子，则将左孩子压入堆栈。 重复步骤 3-6 直到堆栈为空。   function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; } 后序遍历 在本次遍历中，算法先遍历左子树，再遍历右子树，最后访问当前节点。这种排序确保以“自下而上”的方式访问节点，从叶子开始向根移动。  A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A 递归后序遍历 检查当前节点是否为空。如果是这样，返回。 递归调用左子树上的函数。 递归调用右子树上的函数。 访问当前节点。   function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; } 非递归后序遍历 从空栈开始，将根节点压入栈中。 初始化一个空数组来存放后序遍历结果。 输入一个 while 循环，直到堆栈为空。 从堆栈中获取顶部节点（不删除它）。 如果该节点有左孩子，则将左孩子压入栈中，并将当前节点的左孩子置为null。 如果该节点有右孩子，则将右孩子压入栈中，并将当前节点的右孩子设置为null。 如果节点既没有左孩子也没有右孩子，则它是叶节点。从堆栈中弹出节点，并将其值添加到结果数组。 重复步骤 4-7 直到堆栈为空。   function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; } 结论 我希望您现在已经清楚地了解 JavaScript 中中序、前序和后序遍历之间的区别。借助所提供的知识和示例，您现在可以有效地将这些技术应用到您自己的任务和项目中。

Read My Stories

該音頻是用故事的原始語言製作的！

探索 JavaScript 中的树遍历：带示例的中序、先序和后序

About Author

註釋

標籤

这篇文章刊登在

Related Stories

如何将您的工作流程提高 10 倍：17 个必备应用程序

比特币 UTXO 模型，为独特的生态系统提供动力

Claude Sonnet 3.5 系统提示泄漏：法医分析

扬帆起航：利用数据湖开发生产级 RAG 应用程序

如何将您的工作流程提高 10 倍：17 个必备应用程序

比特币 UTXO 模型，为独特的生态系统提供动力

Claude Sonnet 3.5 系统提示泄漏：法医分析

扬帆起航：利用数据湖开发生产级 RAG 应用程序

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps