二叉树的遍历-省流版

递归本质上做的事

递归遍历其实就做了三件事：

访问当前节点（打印或处理数据）；
递归左子树；
递归右子树。

递归函数靠系统调用栈来记住“走到哪一步、该返回哪里”。而非递归遍历，就是自己用栈（Stack）来模拟系统调用栈。

非递归（模拟栈）的基本逻辑

一个栈记录“接下来要访问的节点”。

入栈（push）：表示“以后还要回来访问这个节点”；
出栈（pop）：表示“当前节点访问完成”；
栈顶代表当前递归层正在处理的节点。

三种遍历的思维区别

遍历顺序	操作顺序（递归形式）	非递归实现的核心思路
前序遍历	根 → 左 → 右	出栈时访问 → 先压右再压左
中序遍历	左 → 根 → 右	一直向左入栈 → 遇空回退并访问，再右转
后序遍历	左 → 右 → 根	两次入栈 or 记录上次访问的节点

非递归遍历的具体思路

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

思路：

根节点先访问；
用栈保存节点；
先压右子树，再压左子树，这样出栈顺序正好是“左→右”。

步骤：

根节点入栈；
当栈不空：
- 弹出栈顶并访问；
- 若有右子树 → 压入；
- 若有左子树 → 压入。

1
2
3
4
5
6
7
8


栈操作顺序：

push(A)
pop A → print(A)
push(C)
push(B)
pop B → print(B)
...

C++实现（简洁版）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void preorder(Tree root) {
    if (!root) return;
    stack<Tree> s;
    s.push(root);
    while (!s.empty()) {
        Tree node = s.top(); s.pop();
        cout << node->data << ' ';
        if (node->RChild) s.push(node->RChild);
        if (node->LChild) s.push(node->LChild);
    }
}

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

思路：

一直往左下走，把沿途节点入栈；
遇到空时，弹出一个节点访问；
再转向它的右子树，继续。

步骤：

初始化指针 p = root；
当 p 不空时入栈并左移；
若 p 空：
- 弹出栈顶并访问；
- 再右移；
重复直到栈空且 p 为空。

C++实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void inorder(Tree root) {
    stack<Tree> s;
    Tree p = root;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            p = p->LChild;
        } else {
            p = s.top(); s.pop();
            cout << p->data << ' ';
            p = p->RChild;
        }
    }
}

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

思路：

后序遍历最麻烦，因为根在最后访问。可以用两种常见思路：

方法 1：两个栈（简单好记）

栈1 用来正向遍历；
栈2 存储访问顺序；
最后输出栈2。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void postorder(Tree root) {
    if (!root) return;
    stack<Tree> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        Tree node = s1.top(); s1.pop();
        s2.push(node);
        if (node->LChild) s1.push(node->LChild);
        if (node->RChild) s1.push(node->RChild);
    }
    while (!s2.empty()) {
        cout << s2.top()->data << ' ';
        s2.pop();
    }
}

方法 2：一个栈 + 标记上次访问节点

稍复杂，但节省空间：

用 lastVisited 记录上次访问的节点；
如果右子树访问过或不存在，就访问当前节点。

记忆口诀总结

遍历类型	思路口诀
前序遍历	“根先打印，右先压”
中序遍历	“一路左压，遇空弹栈，右转继续”
后序遍历	“根最后，双栈或标记法”

对比总结

假设二叉树：

遍历方式	输出结果	特点
前序	A B D E C	根先访问
中序	D B E A C	根在中间
后序	D E B C A	根最后访问