EA3-非递归遍历¶

二叉树的非递归遍历使用显式栈（数组模拟）来替代递归调用栈，避免深度过大导致栈溢出。以下是 C 语言实现的三种主要遍历方式：前序、中序、后序，以及层序遍历（BFS）。

一、数据结构定义¶

C
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

二、栈结构定义（用于非递归遍历）¶

C
#define MAX_STACK 100
#define MAX_QUEUE 100

// 栈结构（用于前、中、后序）
typedef struct {
    TreeNode* data[MAX_STACK];
    int top;
} Stack;

void initStack(Stack* s) {
    s->top = -1;
}

int isEmpty(Stack* s) {
    return s->top == -1;
}

void push(Stack* s, TreeNode* node) {
    if (s->top >= MAX_STACK - 1) {
        fprintf(stderr, "Stack overflow\n");
        return;
    }
    s->data[++s->top] = node;
}

TreeNode* pop(Stack* s) {
    if (isEmpty(s)) return NULL;
    return s->data[s->top--];
}

TreeNode* peek(Stack* s) {
    if (isEmpty(s)) return NULL;
    return s->data[s->top];
}

三、非递归遍历实现¶

1. 前序遍历（Preorder）：根 → 左 → 右¶

思路：访问根，压入右，再压入左（利用栈后进先出）

根入栈，循环内先pop栈顶，然后push先右后左。

前期先右后左

C
void preorderTraversal(TreeNode* root) {
    if (!root) return;

    Stack s;
    initStack(&s);
    push(&s, root);

    while (!isEmpty(&s)) {
        TreeNode* node = pop(&s);
        printf("%d ", node->data);

        if (node->right) push(&s, node->right);  // 先压右
        if (node->left)  push(&s, node->left);   // 后压左
    }
}

2. 中序遍历（Inorder）：左 → 根 → 右¶

思路：一路向左压栈，到空时弹出并访问，转向右子树

从跟一路压栈到最左，pop栈顶，然后转向右子树为跟重复🔁。

C
void inorderTraversal(TreeNode* root) {
    Stack s;
    initStack(&s);
    TreeNode* curr = root;

    while (curr || !isEmpty(&s)) {
        // 一直向左走到底，压入路径
        while (curr) {
            push(&s, curr);
            curr = curr->left;
        }

        // 弹出并访问
        curr = pop(&s);
        printf("%d ", curr->data);

        // 转向右子树
        curr = curr->right;
    }
}

3. 后序遍历（Postorder）：左 → 右 → 根¶

由于后序遍历需要在访问完左右子树后才能访问根节点，我们需要用栈来模拟递归过程，并用额外的标记来判断节点的访问状态。

方法一：双栈法（推荐）¶

✅ 核心思路：¶

利用两个栈来模拟后序遍历的逆序过程。

后序遍历顺序是：左 → 右 → 根
它的逆序是：根 → 右 → 左

这个逆序恰好类似于前序遍历的变种（根 → 右 → 左，而不是常规的根 → 左 → 右）。

🧠 思路拆解：¶

第一个栈（s1）：按“根 → 右 → 左”的顺序压入节点（即修改版前序遍历）
第二个栈（s2）：将 s1 弹出的节点依次压入 s2
最后从 s2 弹出：得到的是 s1 中节点的逆序，即 左 → 右 → 根，正是后序遍历！

🎯 关键点：¶

后序遍历 = 逆序的（根 → 右 → 左）

📌 优点：¶

逻辑清晰，易于理解
代码简洁，不易出错

🚫 缺点：¶

使用两个栈，空间略高（但仍是 O(n)）

C++
void postOrderTraversal(TreeNode* root) {
    if (!root) return;

    stack<TreeNode*> s1, s2;
    s1.push(root);

    // 第一个栈用于遍历，第二个栈用于存储结果
    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node);

        // 先压入左子树，再压入右子树
        if (node->left) s1.push(node->left);
        if (node->right) s1.push(node->right);
    }

    // 从第二个栈中弹出就是后序遍历结果
    while (!s2.empty()) {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

方法二：单栈法（带访问标记）¶

✅ 核心思路：¶

使用一个栈，每个节点存储 <节点指针, 是否已访问子树> 的状态。

我们希望：只有当一个节点的左右子树都访问完毕后，才访问该节点本身。

🧠 思路拆解：¶

沿着左子树一路入栈（模拟递归中的“深入左子树”）
到达叶子后，查看栈顶节点：
如果它的子树还没访问过（标记为 false），就转向其右子树
如果它的子树已经访问过（标记为 true），说明左右子树都处理完了，可以访问该节点
访问后弹出，继续处理下一个栈顶

🎯 关键点：¶

用布尔标记记录“是否已处理过当前节点的子树”，避免重复进入

📌 优点：¶

逻辑清晰，体现“状态控制”思想
适合理解递归展开的本质

🚫 缺点：¶

需要额外的 pair 或结构体存储状态

C++
void postOrderTraversal(TreeNode* root) {
    if (!root) return;

    stack<pair<TreeNode*, bool>> s; // bool标记是否已访问过子树
    TreeNode* cur = root;

    do {
        while (cur) { // 沿左子树一直向下
            s.push({cur, false});
            cur = cur->left;
        }

        auto& pair = s.top();
        cur = pair.first;

        if (pair.second) { // 子树已访问过，可以访问当前节点
            cout << cur->val << " ";
            s.pop();
            cur = nullptr; // 防止再次进入左子树循环
        } else { // 标记子树已访问，转向右子树
            pair.second = true;
            cur = cur->right;
        }
    } while (!s.empty() || cur);
}

方法三：单栈法（带前驱节点标记）¶

✅ 核心思路：¶

使用一个栈 + 一个指针 pre 记录上一次访问的节点，通过判断 pre 是否等于当前节点的右子节点，来决定是否可以访问当前节点。

🧠 思路拆解：¶

一路向左入栈（同方法二）
到达底部后，查看栈顶节点 temp：
如果 temp 有右子树且右子树还没访问（即 temp->right != pre）：
- 转向右子树继续遍历
否则（右子树为空或已访问）：
- 可以访问 temp，输出其值
- 更新 pre = temp，表示刚刚访问了它
- 弹出栈顶

🎯 关键点：¶

利用 pre 指针判断“右子树是否已访问”，从而决定是否能访问根节点

📌 优点：¶

只用一个栈 + 一个指针，空间效率高
不需要额外标记字段

🚫 缺点：¶

逻辑稍复杂，pre 的作用需要仔细理解

C++
void postOrderTraversal(TreeNode* root) {
    if (!root) return;

    stack<TreeNode*> s;
    TreeNode* pre = nullptr; // 记录最近访问的节点
    TreeNode* cur = root;

    while (cur || !s.empty()) {
        if (cur) {
            s.push(cur);
            cur = cur->left;
        } else {
            TreeNode* temp = s.top();
            // 如果右子树存在且未被访问过
            if (temp->right && temp->right != pre) {
                cur = temp->right;
            } else {
                cout << temp->val << " ";
                pre = temp;
                s.pop();
            }
        }
    }
}

✅ 三种方法对比总结¶

方法	核心思想	数据结构	关键技巧	适用场景
双栈法	后序 = 逆序的（根→右→左）	两个栈	利用逆序关系	教学、易理解
标记法	状态控制：是否访问过子树	栈 + bool 标记	状态机思维	理解递归展开
前驱法	通过前一个访问节点判断	栈 + pre 指针	利用访问历史	空间敏感场景

4. 层序遍历（Level-order / BFS）¶

使用队列实现广度优先搜索（BFS）

C
void levelOrderTraversal(TreeNode* root) {
    if (!root) return;

    Queue q;
    initQueue(&q);
    enqueue(&q, root);

    while (!isQueueEmpty(&q)) {
        TreeNode* node = dequeue(&q);
        printf("%d ", node->data);

        if (node->left)  enqueue(&q, node->left);
        if (node->right) enqueue(&q, node->right);
    }
}

四、四种遍历对比¶

遍历方式	数据结构	时间复杂度	空间复杂度	特点
前序	栈	O(n)	O(h)	最简单，DFS 基础
中序	栈	O(n)	O(h)	BST 中序 = 有序
后序	栈 + prev	O(n)	O(h)	最复杂，需判断访问状态
层序	队列	O(n)	O(w)	w = 最大宽度，适合按层处理

h = 树高，w = 最大宽度（如完全二叉树最宽层）

五、关键点总结¶

非递归本质：用显式数据结构模拟系统调用栈。
前/中/后序 → 用 栈（Stack）
层序 → 用 队列（Queue）
后序难点在于避免重复访问右子树，prev 指针是关键。

如需实现线索二叉树遍历或Morris遍历（O(1)空间复杂度），也可继续提问。