二叉树遍历非递归实现：前序、中序、后序（栈）

树形结构的遍历，说白了就是“怎么把一棵树里所有节点都走一遍”。递归写法很优雅，但实际项目中——尤其是嵌入式环境——递归的栈开销往往让人头疼。我记得有一次在某个资源受限的MCU上做文件系统目录遍历，递归直接撑爆了任务栈，从那以后，我对非递归遍历就格外上心。

这一章我们聚焦二叉树遍历的非递归实现。核心工具就是栈。前序和中序用一个栈就能搞定，后序稍微绕一点，我习惯用双栈法，思路清晰，不容易写错。

1. 前序非递归遍历（单栈）

前序遍历的顺序是：根 → 左 → 右。非递归实现时，我们手动模拟递归栈的行为。

思路很简单：

• 从根节点出发，一路向左，边压栈边访问节点。
• 走到左边尽头后，弹出栈顶节点，转向右子树。
• 重复这个过程，直到栈空且当前节点为NULL。

我个人习惯把“访问节点”放在压栈之前，这样逻辑上更贴近递归的前序顺序。

void preorder_nonrecursive(TreeNode* root) {
    if (root == NULL) return;

    Stack* stack = createStack(100);
    TreeNode* cur = root;

    while (cur != NULL || !isEmpty(stack)) {
        // 一路向左，边压栈边访问
        while (cur != NULL) {
            printf("%d ", cur->data);   // 访问根节点
            push(stack, cur);
            cur = cur->left;
        }
        // 弹出栈顶，转向右子树
        cur = pop(stack);
        cur = cur->right;
    }

    destroyStack(stack);
}

2. 中序非递归遍历（单栈）

中序遍历的顺序是：左 → 根 → 右。和前序的区别只有一个：访问节点的时机不同。

中序非递归的套路：

• 同样一路向左压栈，但不访问节点。
• 走到左边尽头后，弹出栈顶节点，此时才访问。
• 然后转向右子树，重复。

你想想看，为什么中序要等到弹出时才访问？因为中序要求左子树先处理完，根节点才能出场。栈正好帮我们把左子树路径暂存起来，等左子树走到底，再回头处理根。

void inorder_nonrecursive(TreeNode* root) {
    if (root == NULL) return;

    Stack* stack = createStack(100);
    TreeNode* cur = root;

    while (cur != NULL || !isEmpty(stack)) {
        // 一路向左压栈，不访问
        while (cur != NULL) {
            push(stack, cur);
            cur = cur->left;
        }
        // 弹出栈顶，此时访问
        cur = pop(stack);
        printf("%d ", cur->data);   // 访问根节点
        cur = cur->right;
    }

    destroyStack(stack);
}

3. 后序非递归遍历（双栈法）

后序遍历的顺序是：左 → 右 → 根。这是三种遍历里最麻烦的非递归实现。为什么？因为当你处理完左子树和右子树后，还得回到根节点，但栈里只保存了路径，你没法区分“左子树刚处理完”还是“右子树刚处理完”。

双栈法是我个人最推荐的方式。思路很巧妙：

• 第一个栈用来做“逆向”的前序遍历：根 → 右 → 左。
• 把访问结果压入第二个栈。
• 最后把第二个栈全部弹出，得到的就是左 → 右 → 根的后序顺序。

说白了，后序就是“前序的镜像”再反转。你想想看，前序是根左右，后序是左右根，如果把前序改成根右左，再反转，不就是左右根了吗？

void postorder_nonrecursive(TreeNode* root) {
    if (root == NULL) return;

    Stack* stack1 = createStack(100);
    Stack* stack2 = createStack(100);
    TreeNode* cur;

    push(stack1, root);

    while (!isEmpty(stack1)) {
        cur = pop(stack1);
        push(stack2, cur);   // 先压入第二个栈

        // 注意：先压左，再压右，这样弹出顺序是根右左
        if (cur->left != NULL)
            push(stack1, cur->left);
        if (cur->right != NULL)
            push(stack1, cur->right);
    }

    // 弹出第二个栈，得到后序顺序
    while (!isEmpty(stack2)) {
        cur = pop(stack2);
        printf("%d ", cur->data);
    }

    destroyStack(stack1);
    destroyStack(stack2);
}

4. 三种遍历的对比总结

5. 知识体系流程图

下面这张图帮你理清三种非递归遍历的核心逻辑和区别：

6. 避坑指南与个人经验

我曾经在调试一个树形菜单的遍历时，把中序和前序的访问时机搞反了，结果菜单顺序完全乱掉。后来我养成了一个习惯：写非递归遍历时，先把递归版本写在注释里，然后对照着翻译成栈操作，这样不容易出错。

另外，双栈法虽然多用一个栈，但它的好处是不需要额外标志位，逻辑一目了然。如果你面试时被问到后序非递归，我建议你直接说双栈法，面试官通常会觉得你思路清晰。

公众号:蓝海资料掘金营，微信deep3321