5,267 讀數

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

经过 Anton Nikiforov7m2023/05/29

太長; 讀書

树遍历是计算机科学中的一个基本概念，涉及系统地访问树数据结构中的每个节点。通过树遍历，我们可以按预定顺序处理节点，方便搜索、排序和评估表达式等操作。在本文中，我们将探讨三种使用最广泛的树。遍历方法：中序、前序、后序。

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

树遍历是计算机科学中的一个基本概念，涉及系统地访问树数据结构中的每个节点。通过树遍历，我们可以按预定顺序处理节点，方便搜索、排序和评估表达式等操作。

在本文中，我们将探索三种最广泛使用的树遍历方法：中序、前序和后序。

通过用 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; }