二叉树前序遍历的迭代式实现：从基础到进阶的完全指南

你好！作为一名开发者，我们经常需要在处理树形数据结构时遍历节点。你可能已经熟悉了递归方式的优雅，但在实际生产环境中，尤其是面对深度极大的树时，递归可能会带来栈溢出的风险。因此，掌握迭代式遍历不仅是为了通过面试，更是为了编写更健壮的代码。

在这篇文章中，我们将深入探讨二叉树的前序遍历。我们将一起从最基础的思路出发，逐步构建高效的迭代算法，并剖析其中的每一个细节。无论你是在准备算法面试，还是正在优化项目中的数据处理逻辑，这篇文章都将为你提供实用的见解和高质量的代码参考。

什么是前序遍历？

简单来说，前序遍历遵循“根-左-右”的顺序。当我们访问一个节点时，先处理节点本身的数据，然后递归地处理左子树，最后处理右子树。

• 根节点：首先访问当前节点。
• 左子树：然后访问当前节点的左子节点。
• 右子树：最后访问当前节点的右子节点。

#### 示例演示

为了确保我们在同一个频道上，让我们看一个直观的例子：

> 输入：

>

>       1
>      / \
>     2   3
>    / \
>   4   5
> 

> 前序遍历流程：

> 1. 访问根节点：1

> 2. 走向左子树（根节点为2）：访问 2

> 3. 继续走向2的左子树（根节点为4）：访问 4

> 4. 4没有子节点，回退到2，走向2的右子树（根节点为5）：访问 5

> 5. 2的子树处理完毕，回退到1，走向1的右子树（根节点为3）：访问 3

>

> 输出： 1 2 4 5 3

为什么选择迭代？

虽然递归代码简洁，但它依赖于系统的调用栈。在处理如 int main() { Node* root = ...; } 这种极深的链状树（类似链表）时，递归深度可能达到数万甚至数百万层，直接导致 栈溢出 错误。迭代法通过显式地使用堆栈数据结构，能让我们更精确地控制内存使用，这是高级程序员必须掌握的技能。

—

方法一：使用栈的经典迭代法

这是最直观的迭代解法。在递归中，操作系统帮助我们管理调用栈；而在迭代中，我们需要自己构建这个栈。

#### 算法核心思路

• 初始化：创建一个空栈 S，并将根节点压入栈中。
• 循环条件：只要栈 S 不为空，就说明还有节点未处理。
• 弹出与访问：从栈顶弹出一个节点，并将其值加入结果列表（这对应于递归中的“处理根节点”）。
• 压入子节点：

* 这里有个关键技巧：栈是“后进先出” (LIFO) 的数据结构。

* 我们希望先处理左子节点，再处理右子节点。

* 因此，我们必须先将右子节点压入栈，再将左子节点压入栈。这样，左子节点会位于栈顶，下一次循环时就会先被弹出。

• 结束：当栈为空时，遍历完成。

#### 复杂度分析

• 时间复杂度：O(n)。每个节点只被访问和弹出一次。
• 空间复杂度：O(h)，其中 h 是树的高度。最坏情况下（树退化为链表），栈的大小为 n；平均情况下为 O(log n)。

#### 代码实现

我们可以通过以下几种主流编程语言来实现这个逻辑。注意代码中的注释，它们解释了每一步的作用。

C++ 实现

#include 
#include 
#include 

using namespace std;

// 定义树节点结构
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = right = nullptr; 
    }
};

// 迭代式前序遍历函数
vector preOrder(Node* root) {
    vector res;
    // 边界检查：如果根节点为空，直接返回空结果
    if (root == nullptr)
        return res;

    // 使用 STL 的 stack 容器
    stack s;
    // 步骤1：将根节点压入栈中
    s.push(root);

    // 步骤2：循环直到栈为空
    while (!s.empty()) {
        // 弹出栈顶元素并访问
        Node* curr = s.top();
        s.pop();
        res.push_back(curr->data);

        // 关键步骤：先压右孩子，再压左孩子
        // 因为栈是后进先出，这样能保证左孩子先被处理
        if (curr->right != nullptr)
            s.push(curr->right);
        if (curr->left != nullptr)
            s.push(curr->left);
    }

    return res;
}

int main() {
    // 构建测试用例
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    vector preorder = preOrder(root);

    cout << "前序遍历结果: ";
    for (int val : preorder) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Java 实现

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class Solution {
    public static List preOrder(Node root) {
        List res = new ArrayList();
        if (root == null) return res;

        Stack s = new Stack();
        s.push(root);

        while (!s.isEmpty()) {
            Node curr = s.pop();
            res.add(curr.data);

            // 先右后左，确保栈顶是左节点
            if (curr.right != null) s.push(curr.right);
            if (curr.left != null) s.push(curr.left);
        }

        return res;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        List result = preOrder(root);
        System.out.println("前序遍历结果: " + result);
    }
}

Python 实现

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def preOrder(root):
    res = []
    if root is None:
        return res
    
    # Python 列表可以完美充当栈使用
    stack = [root]
    
    while stack:
        curr = stack.pop()
        res.append(curr.data)
        
        # 注意顺序：先压右，再压左
        if curr.right:
            stack.append(curr.right)
        if curr.left:
            stack.append(curr.left)
            
    return res

if __name__ == ‘__main__‘:
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    
    print(‘前序遍历结果:‘, preOrder(root))

JavaScript 实现

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function preOrder(root) {
    const res = [];
    if (root === null) return res;

    const stack = [root];

    while (stack.length > 0) {
        const curr = stack.pop();
        res.push(curr.data);

        // JavaScript 中数组也是很好的栈结构
        if (curr.right !== null) stack.push(curr.right);
        if (curr.left !== null) stack.push(curr.left);
    }

    return res;
}

// 测试代码
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

console.log(‘前序遍历结果:‘, preOrder(root).join(‘ ‘));

C# 实现

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class BinaryTreeTraversal {
    public static List PreOrder(Node root) {
        List res = new List();
        if (root == null) return res;

        Stack s = new Stack();
        s.Push(root);

        while (s.Count > 0) {
            Node curr = s.Pop();
            res.Add(curr.data);

            if (curr.right != null) s.Push(curr.right);
            if (curr.left != null) s.Push(curr.left);
        }

        return res;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        List result = PreOrder(root);
        Console.WriteLine("前序遍历结果: " + string.Join(" ", result));
    }
}

—

常见误区与最佳实践

在我们编写这类代码时，有几个容易“踩坑”的地方，你需要注意：

• 压栈顺序：最常见的错误就是先压左孩子，再压右孩子。这会导致右子树先于左子树被遍历，输出的顺序就变成了前序遍历的“镜像”版本。请时刻记住：想要左边先出，就得右边先入。

• 空指针检查：在向栈中压入子节点之前，务必检查 INLINECODE67927e99（或 INLINECODE536c2528）。如果试图将 INLINECODE75a2ca67 压入栈，后续弹出时进行 INLINECODE424014a3 操作会直接导致程序崩溃。

• 空间换时间：虽然上述方法空间复杂度是 O(n)，但在实际应用中，栈的开销通常是可以接受的。相比于递归可能导致的隐式栈溢出，显式栈提供了更好的可控性。

总结

通过这篇文章，我们一起攻克了二叉树迭代式前序遍历这一经典算法。我们从递归的原理出发，理解了为什么要引入栈，并亲手实现了 C++、Java、Python、JavaScript 和 C# 五种语言的版本。

关键点回顾：

• 根 -> 左 -> 右 是前序遍历的核心顺序。
• 使用栈来模拟递归调用栈是迭代法的精髓。
• 先压右，再压左 是保证遍历顺序正确的关键技巧。

希望这些代码示例和解释能帮助你更好地理解这一算法。在接下来的学习中，你可以尝试探索更高级的遍历方法，例如“Morris 遍历”，它能在不使用栈的情况下以 O(1) 空间复杂度完成遍历，但这属于较为进阶的话题了。现在，不妨试着在你的本地 IDE 中运行这些代码，感受一下迭代算法的魅力吧！