树遍历是计算机科学中的一个基本概念，涉及系统地访问树数据结构中的每个节点。通过树遍历，我们可以按预定顺序处理节点，方便搜索、排序和评估表达式等操作。 在本文中，我们将探索三种最广泛使用的树遍历方法：中序、前序和后序。 通过用 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 中中序、前序和后序遍历之间的区别。借助所提供的知识和示例，您现在可以有效地将这些技术应用到您自己的任务和项目中。
