后序遍历

2026 大纲 四（二）3 二叉树的遍历 · 后序部分，两种非递归解法（标记法、双栈法）在本篇讲透（前序见《前序遍历》、中序见《中序遍历》、层序见《层序遍历》）。

后序：先算完孩子，再算自己

左子树 → 右子树 → 根结点（LRN）。在遍历的固定游走路线上每个结点被经过三次，后序取第三次——左右子树都处理完、准备回到双亲的那一刻。

        A
       / \
      B   C
     / \   \
    D   E   F

后序序列是 D → E → B → F → C → A。

"先算完孩子，再算自己"这七个字就是后序全部用途的来源。 求树高 $H(T)=max(H(T_L),H(T_R))+1$——不知道两棵子树的高度就算不出自己的；求结点数、判断是否平衡同理；释放整棵树更是必须后序，因为先 free 掉根就丢掉了子树的指针。

反过来，"信息从根往下传"的任务（标层号、求根到叶的路径、按序列建树、复制）必须用前序。判据只有一句：算根的时候，需不需要子树的结果。

先看一眼

加载可视化中...

看完你应该确认：一个结点被访问的时刻，是它的两棵子树都已经走完的时候——所以根一定是最后一个。

递归实现，与两条序列性质

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void PostOrder(BiTree T) {
    if (T == NULL) return;   // 递归出口
    PostOrder(T->lchild);    // 先把左子树处理完
    PostOrder(T->rchild);    // 再把右子树处理完
    visit(T);                // 最后访问根 —— visit 在两次递归之后，这就是"后序"
}

两条性质要记住，后面反复用到。

第一，末元素必是根，与前序的"首元素必是根"对称。这两条合起来正是由遍历序列构造二叉树的入手点。

第二，后序 $=$ NRL 的逆序。 上例的 NRL（根→右→左）序列是 A C F B E D，反过来读正是后序 D E B F C A。

这一条极易记反：不是前序（NLR）的逆序。 前序 A B D E C F 逆过来是 F C E D B A，不是后序。记法是看结构：$\mathrm{NRL}(T)=N\cdot \mathrm{NRL}(T_R)\cdot \mathrm{NRL}(T_L)$，整体逆序后变成 $\mathrm{rev}(\mathrm{NRL}(T_L))\cdot \mathrm{rev}(\mathrm{NRL}(T_R))\cdot N$，递归代入即得 $L\cdot R\cdot N$。只有先右后左的次序，逆过来才是先左后右。 这条性质是下面双栈法的全部依据。

非递归难在哪：模板缺一个状态位

中序遍历那套统一模板对前序中序都够用，因为每个结点只需被处理一次。后序要求左右子树都完才能访问根，而结点被弹出时的状态是模糊的：

栈顶是结点 X，当前 p == NULL，说明"刚从某处回来了"。可是——
   情形 ①：刚从 X 的左子树回来，X 的右子树还没去   → 不能访问 X，要转向右子树
   情形 ②：刚从 X 的右子树回来，两边都完了         → 可以访问 X，弹栈

两种情形在栈上长得一模一样。 模板缺的正是"X 的右子树处理过没有"这一个状态位——所以"后序非递归最难"的准确原因不是代码长，而是信息不够。

补它有两条路：正面补上（标记法，记住上一个被访问的结点），或者绕开它（双栈法，先按 NRL 走一遍再整体倒出）。

解法一：标记法（r 指针）

用辅助指针 r 记录最近一次被访问的结点。栈顶结点 p 可以访问的条件是

$$p\to rchild=\text{NULL}\text{或}p\to rchild=r$$

前者表示它没有右子树，后者表示右子树刚访问完——因为后序里一棵子树最后被访问的正是它的根，r 等于右孩子就证明整棵右子树都完了。

void PostOrderFlag(BiTree T) {
    Stack S;
    InitStack(S);
    BiTNode *p = T, *r = NULL;      // r 指向最近访问过的结点
    while (p || !IsEmpty(S)) {
        if (p) {                    // 沿左链一路入栈（与统一模板相同）
            Push(S, p);
            p = p->lchild;
        } else {
            GetTop(S, p);           // 只取栈顶，不弹出 —— 因为还可能要转向它的右子树
            if (p->rchild && p->rchild != r) {
                p = p->rchild;      // 情形①：右子树还没处理，转过去
            } else {
                Pop(S, p);
                visit(p);           // 情形②：左右都完了，访问根
                r = p;              // 记录"刚访问的是它"
                p = NULL;           // 关键：置空，让下一轮继续走 else 分支去看新的栈顶
            }
        }
    }
}

三处细节缺一不可，默写前先把它们的道理过一遍：

细节	为什么必须这样	写错会怎样
用 GetTop 取栈顶而不是 Pop	取出来后可能要转向它的右子树，转完还得回到它把它访问掉；提前弹出就再也找不回来	结点的右子树处理完后，该结点永远不会被访问
访问后置 p = NULL	若不置空，p 仍指向刚访问过的结点，下一轮会走进 if (p) 分支，把它重新入栈并再次沿它的左链下潜	死循环 / 结点被重复访问
r 只在访问后更新，不在入栈时更新	r 的语义是"最近一个被访问过的结点"，只有它才能证明某棵右子树已经完成	提前更新会让还没处理的右子树被误判为已完成，整棵右子树被跳过

标记法还有一个不可替代的性质：每当栈顶是结点 $X$ 时，栈中自底向上恰好是从根到 $X$ 的那条路径。 由此得到两个推论：

• 求某结点的所有祖先：遍历到目标结点时，把栈从底到顶打印出来即可；
• 求两个结点的最近公共祖先：先遍历到第一个结点、把栈内容整条复制下来；继续遍历到第二个结点时，拿当前栈与副本从底部逐个比对，最后一个相同的结点就是最近公共祖先。

双栈法没有这个性质——它的 S1 里装的是待展开的兄弟分支，不是路径。凡是题目要"路径 / 祖先 / 最近公共祖先"，只能用标记法。

标记法的逐步执行表（想手动模拟一遍就展开）

步	当前 p	动作	栈（底→顶）	r	输出
1	A	入栈，向左	A	NULL	—
2	B	入栈，向左	A B	NULL	—
3	D	入栈，向左	A B D	NULL	—
4	NULL	栈顶 D，无右子树 → 弹出访问	A B	D	D
5	NULL	栈顶 B，右孩子 E $\ne$ r=D → 转向 E	A B	D	—
6	E	入栈，向左	A B E	D	—
7	NULL	栈顶 E，无右子树 → 弹出访问	A B	E	E
8	NULL	栈顶 B，右孩子 E $=$ r → 弹出访问	A	B	B
9	NULL	栈顶 A，右孩子 C $\ne$ r=B → 转向 C	A	B	—
10	C	入栈，向左（左为空）	A C	B	—
11	NULL	栈顶 C，右孩子 F $\ne$ r=B → 转向 F	A C	B	—
12	F	入栈，向左	A C F	B	—
13	NULL	栈顶 F，无右子树 → 弹出访问	A C	F	F
14	NULL	栈顶 C，右孩子 F $=$ r → 弹出访问	A	C	C
15	NULL	栈顶 A，右孩子 C $=$ r → 弹出访问	（空）	A	A

输出 D E B F C A ✓。注意每一行的栈内容都是一条自根而下的路径。

解法二：双栈法（NRL 再逆序）

依据就是上面那条"后序 $=$ NRL 的逆序"。NRL（根→右→左）与前序是同一类遍历——每个结点只处理一次，可以用最简单的"弹栈 + 压孩子"写法完成。把 NRL 的结果压进第二个栈，再全部弹出，就得到逆序。

void PostOrderDoubleStack(BiTree T) {
    if (T == NULL) return;
    Stack S1, S2;
    InitStack(S1); InitStack(S2);
    Push(S1, T);
    while (!IsEmpty(S1)) {
        BiTNode *p;
        Pop(S1, p);
        Push(S2, p);                          // S1 的弹出序列就是 NRL，全部转存到 S2
        if (p->lchild) Push(S1, p->lchild);   // 左先入栈 → 后弹出
        if (p->rchild) Push(S1, p->rchild);   // 右后入栈 → 先弹出，保证"根→右→左"
    }
    while (!IsEmpty(S2)) {
        BiTNode *p;
        Pop(S2, p);
        visit(p);                             // S2 后进先出，弹出顺序即 NRL 的逆序 = 后序
    }
}

入栈次序的判据：想让谁先被展开，就让谁后入栈。 这里要右子树先展开，所以右孩子后入栈——与[前序的"弹栈压右左"写法恰好相反（前序要左先出，所以左后入）。这一处最容易照着前序抄错。

双栈法的逐步执行表（想验证 NRL 那一步就展开）

同一棵树：

步	从 S1 弹出	压入 S1	S1（底→顶）	S2（底→顶）
0	—	A	A	—
1	A	B，C	B C	A
2	C	F（C 无左孩子）	B F	A C
3	F	—	B	A C F
4	B	D，E	D E	A C F B
5	E	—	D	A C F B E
6	D	—	（空）	A C F B E D

S1 的弹出序列 A C F B E D 正是 NRL；S2 自顶向下弹出得到 D E B F C A，即后序 ✓

两种解法怎么选：

对比项	标记法（r 指针）	双栈法
思路	补上"右子树是否已处理"的状态位	绕开：做 NRL 再整体逆序
空间	$O(h)$——栈中是当前路径	$O(n)$——S2 最终装下全部 $n$ 个结点
访问时机	边遍历边访问，在线	必须先走完整棵树才开始访问，离线
能否求祖先、最近公共祖先	能	不能
代码难度	较高（三处细节易错）	较低

判据：题目只要"写出后序序列"，双栈法更好写；题目涉及路径、祖先、边访问边判断、空间受限，只能用标记法。

顺带说清复杂度：两种写法时间都恒为 $O(n)$（标记法里每个结点最多入栈一次、被 GetTop 查看两次、出栈一次；双栈法里每个结点在两个栈上各进出一次）。双栈法的 $O(n)$ 空间不可优化——它必须把整个遍历序列缓存下来才能逆序输出，这是"离线"算法的固有代价。

后序驱动的任务

1. 求二叉树的高度。

int Depth(BiTree T) {
    if (T == NULL) return 0;         // 空树高度为 0
    int m = Depth(T->lchild);        // 先拿到左子树高度
    int n = Depth(T->rchild);        // 再拿到右子树高度
    return (m > n ? m : n) + 1;      // 最后才能算自己 —— 后序的访问时机
}

2. 统计结点数 / 叶子数 / 各度结点数。

int NodeCount(BiTree T) {
    if (T == NULL) return 0;
    return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

int LeafCount(BiTree T) {
    if (T == NULL) return 0;
    if (T->lchild == NULL && T->rchild == NULL) return 1;   // 度为 0
    return LeafCount(T->lchild) + LeafCount(T->rchild);
}

把判定条件换成 (lchild == NULL) != (rchild == NULL) 就是统计度为 1 的结点，换成 lchild && rchild 就是度为 2 的结点。三者算完可以用 $n_0=n_2+1$ 自检。

3. 释放整棵二叉树——这一个必须是后序。

void DestroyBiTree(BiTree T) {
    if (T == NULL) return;
    DestroyBiTree(T->lchild);   // 先释放子树
    DestroyBiTree(T->rchild);
    free(T);                    // 最后释放自己
}

先 free(T) 会让 T->lchild、T->rchild 变成对已释放内存的访问，两棵子树将永远无法回收。

4. 后缀表达式求值。 对表达式树做后序遍历得到后缀表达式（逆波兰式），它不需要括号也无歧义：

表达式	表达式树的后序序列
$a+b\times c$	a b c * +
$(a+b)\times c$	a b + c *

同一批符号、两棵不同的树给出两个不同的后缀式；而它们的中序序列都是 a + b * c——这正是中序输出会丢括号、而后序不会的原因。求值时用一个栈：遇操作数入栈，遇运算符弹两个操作数、算完把结果压回，最终栈里剩的就是答案。

5. 判断二叉树是否平衡。 要判断某结点是否平衡，必须先知道它两棵子树的高度——又是自底向上，只能后序。见 平衡二叉树（AVL）。

考点速记

三条会被反复调用的结论：

1. 后序 $=$ "先算完孩子再算自己"：求高度、结点数、判平衡、释放内存、后缀式只能用它。
2. 后序序列末元素必是根，且后序 $=$ NRL 的逆序（不是前序的逆序）——前者是构造二叉树的入手点，后者是双栈法的依据。
3. 非递归的困难是模板缺一个状态位；标记法的栈恰是根到当前结点的路径，这是它相对双栈法不可替代的价值。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 给树形 + 后序序列，问别的信息。 树形已经画在题面上，后序序列只是把字母对应到结点上。做法固定：先按后序在图上编号、把字母填进去，再读目标——问"与某结点同层的是谁"就数层，问"先序序列是什么"就重读一遍。这类题失分几乎都在填字母时错位，慢一点把整棵树标完最稳。
• 前序 + 后序的联合推理。 后序末与前序首都是根，两者一起用能定出根的孩子数：去根后前序首 $=$ 后序末 $⟺$ 根只有一个孩子；若去根后两个序列完全逆序，则整棵树是一条单链。
• 由中序 + 层序重建后求后序。 层序的第一个是根，用它在中序里切分左右；再从层序剩余部分里挑出最先出现的、属于该子树的结点作为该子树的根，递归下去。重建完再读一遍后序。
• 森林的后根遍历对应二叉树的哪种遍历。 答案是中序，不是后序。这一条方向最容易记反，见 森林与二叉树的转换。
• 后序线索树的判定。 见 线索二叉树——后序线索树找后继需要双亲信息，这是它与中序线索树最大的区别。

易错：把"后序 $=$ NRL 的逆序"记成"后序 $=$ 前序的逆序"。 只有先右后左的次序，逆过来才是先左后右。

易错：双栈法照抄前序的入栈次序。 前序是先压右后压左，双栈法是先压左后压右。

易错：标记法里用 Pop 取栈顶、或访问后忘记 p = NULL。 前者让结点再也访问不到，后者直接死循环。

易错：认为森林的后根遍历对应二叉树的后序。 它对应的是中序。

教材出处

• 三种遍历的操作定义与"限定先左后右后只剩前三种方案"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p122（5.5.1 节）
• "三种遍历算法不同处仅在于访问根结点和遍历左右子树的先后关系；抹去输出语句后三个算法完全相同"，以及用三角形/圆形/方形分别标出前序/中序/后序访问时机的递归执行过程图：印刷 p123
• 遍历的复杂度分析（时间 $O(n)$，辅助空间为栈的最大容量即树的深度，最坏 $O(n)$）：印刷 p125
• "计算二叉树的深度是在后序遍历二叉树的基础上进行的运算"、深度算法（左右子树深度取大者加 1）与统计结点个数的算法，以及"读者可以模仿此算法写出统计度为 0、度为 1、度为 2 的结点个数"：印刷 p127–p128

相关知识

前序遍历（首元素是根，与后序对称）｜中序遍历｜层序遍历｜由遍历序列构造二叉树｜线索二叉树｜树与二叉树基本概念｜平衡二叉树（AVL）

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（7题）

2026Q32分2023Q52分2020Q42分2017Q52分2012Q32分2011Q52分2010Q32分