在javascript中实现二叉树的前中后序遍历，主要通过递归或迭代方法完成，核心区别在于访问根、左子树和右子树的顺序：前序为根左右，中序为左根右，后序为左右根；递归实现简洁直观，而迭代实现分别利用栈结构模拟调用过程，其中前序使用单一栈并先入右子节点再入左子节点，中序通过持续入栈左子节点并在回溯时访问，后序则可通过双栈法将前序的根右左逆序变为左右根，最终实现三种遍历方式的正确输出，完整掌握这些方法是处理树形结构的基础，也是算法进阶的关键步骤。
在JavaScript中实现二叉树的前中后序遍历，主要依赖递归或借助栈的迭代方法。这三种遍历方式的核心区别在于访问根节点、左子树和右子树的相对顺序。理解并掌握它们，是处理树形数据结构的基础，也是许多复杂算法的起点。
解决方案
我们先定义一个简单的二叉树节点结构，这样后续的代码会更清晰：
class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}
接下来，我们看看前中后序的实现。
前序遍历 (Pre-order Traversal): 根 -> 左 -> 右
前序遍历的逻辑是先访问当前节点，然后递归地访问左子树，最后访问右子树。
递归实现：这是最直观的方式，代码非常简洁。
function preorderTraversalRecursive(root, result = []) { if (!root) { return result; } result.push(root.val); // 访问根节点 preorderTraversalRecursive(root.left, result); // 遍历左子树 preorderTraversalRecursive(root.right, result); // 遍历右子树 return result;}
迭代实现：使用一个栈来模拟递归的过程。我的思路是，先将根节点入栈。然后在一个循环里，每次弹出栈顶元素，访问它，接着先将右子节点入栈（如果存在），再将左子节点入栈（如果存在）。这样做的原因是，栈是后进先出（LIFO），为了先处理左子树，我们必须先让左子树的根在栈顶。
function preorderTraversalIterative(root) { const result = []; if (!root) { return result; } const stack = [root]; while (stack.length > 0) { const node = stack.pop(); result.push(node.val); // 先推右孩子，再推左孩子，确保左孩子先被处理 if (node.right) { stack.push(node.right); } if (node.left) { stack.push(node.left); } } return result;}
中序遍历 (In-order Traversal): 左 -> 根 -> 右
中序遍历是先访问左子树，然后访问当前节点，最后访问右子树。对于二叉搜索树（BST）来说，中序遍历的结果是一个有序序列，这特性蛮有意思的。
递归实现：
function inorderTraversalRecursive(root, result = []) { if (!root) { return result; } inorderTraversalRecursive(root.left, result); // 遍历左子树 result.push(root.val); // 访问根节点 inorderTraversalRecursive(root.right, result); // 遍历右子树 return result;}
迭代实现：这个实现稍微需要一点技巧。我们需要一直向左走，将遇到的节点压入栈中。当无法再向左走时，弹出栈顶节点并访问它，然后转向其右子树。
function inorderTraversalIterative(root) { const result = []; const stack = []; let current = root; while (current || stack.length > 0) { // 一直向左，并将节点入栈 while (current) { stack.push(current); current = current.left; } // 弹出栈顶节点，它是当前子树中最左的未访问节点 current = stack.pop(); result.push(current.val); // 转向右子树 current = current.right; } return result;}
后序遍历 (Post-order Traversal): 左 -> 右 -> 根
后序遍历是先访问左子树，然后访问右子树，最后访问当前节点。这个遍历方式在释放资源或构建表达式树时比较常用。
递归实现：
function postorderTraversalRecursive(root, result = []) { if (!root) { return result; } postorderTraversalRecursive(root.left, result); // 遍历左子树 postorderTraversalRecursive(root.right, result); // 遍历右子树 result.push(root.val); // 访问根节点 return result;}
迭代实现：后序遍历的迭代实现通常被认为是最复杂的。一种比较直观的方法是使用两个栈。第一个栈用于模拟前序遍历的逆过程（根右左），第二个栈则收集第一个栈弹出的元素，最终第二个栈的元素顺序就是后序遍历的结果。
function postorderTraversalIterative(root) { const result = []; if (!root) { return result; } const stack1 = [root]; const stack2 = []; // 用于存储最终结果的逆序 while (stack1.length > 0) { const node = stack1.pop(); stack2.push(node.val); // 将节点值推入第二个栈 // 先推左孩子，再推右孩子，确保右孩子先被处理 if (node.left) { stack1.push(node.left); } if (node.right) { stack1.push(node.right); } } // stack2 此时存储的是 "根右左" 的逆序，即 "左右根" return stack2.reverse();}
这个双栈方法虽然多用了一个栈，但在理解上比单栈的复杂判断要容易些，我个人觉得在初学时更友好。
以上就是JS如何实现二叉树遍历？前中后序遍历的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1516452.html
微信扫一扫 
支付宝扫一扫 
