JS实现二叉树前中后序遍历方法

想知道如何在JavaScript中高效实现二叉树遍历吗？本文深入讲解了二叉树的前序、中序和后序遍历算法，并提供清晰易懂的JS代码示例。无论你是算法新手还是想巩固基础，都能轻松掌握递归与迭代两种实现方式。通过学习，你将理解前序（根左右）、中序（左根右）和后序（左右根）遍历的区别，并能运用栈结构模拟递归过程，为解决更复杂的树形结构问题打下坚实基础。掌握这些关键算法，助力你的JS编程能力更上一层楼！

在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实现二叉树前中后序遍历方法》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！