一 真题2010-3
2010-03. 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
二 题目要素解析
核心概念：后序线索二叉树
- 对二叉树进行后序遍历后，将空的左指针（lchild）改为指向该节点的后序前驱，空的右指针（rchild）改为指向该节点的后序后继。
- 非空的指针仍保留原来的孩子指针含义。
遍历顺序：后序遍历顺序为 左子树 → 右子树 → 根节点。
线索特征：
- 叶子节点的 lchild 和 rchild 都为空，会被全部改为线索。
- 非叶子节点如果某一方向没有孩子，也会被加上线索。
三 哔哔详解
四个选项的二叉树图是一样的，都是下图
a
/ \\
b c
/
d
后序遍历序列：d → b → c → a
选项 D
- 节点 d 左指针为 Null（正确），右指针指向 b（d 的后继是 b，正确）。
- 节点 b 的左指针指向 d（b 的前驱是 d，正确），右指针指向 c（b 的后继是 c，正确）。
- 节点 c 的左指针指向 b（c 的前驱是 b，正确），右指针指向 a（c 的后继是 a，正确）。
- 节点 a 的左指针指向 c（a 的前驱是 c，正确），右指针为 Null（正确）。
- 所有空指针都正确指向了后序前驱或后继，完全符合定义。
既然D 符合，故排除其与选项。
四 参考答案
参考答案 D
五 考点精析
5.1 线索二叉树概念
线索二叉树 是对普通二叉树的一种存储优化结构：
- 将二叉树中空的左/右指针域，改为指向该节点在某种遍历序列中的前驱或后继；
- 这些新添加的指针称为 线索（Thread），原指向孩子的指针称为 指针（Link）。
📌 目的：
- 利用空指针空间，避免递归或栈实现遍历；
- 实现非递归、O(1) 空间的遍历（需配合标志位）。
5.2 线索二叉树基本性质与特征
5.2.1 节点结构
每个节点增加两个布尔标志位（通常为 ltag 和 rtag）：
| lchild | 左孩子指针 或 前驱线索 |
| rchild | 右孩子指针 或 后继线索 |
| ltag | 0：lchild 指向左孩子；1：lchild 指向前驱 |
| rtag | 0：rchild 指向右孩子；1：rchild 指向后继 |
💡 若题目图示中未标标志位，则通过实线/虚线区分：
- 实线 = 指针（孩子）；
- 虚线 = 线索（前驱/后继）。
5.2.2 线索化规则（通用）
| 前序线索化 | 前驱 | 后继 |
| 中序线索化 | 前驱 | 后继 |
| 后序线索化 | 前驱 | 后继 |
✅ 统一规律：
- 左空指针 → 前驱；
- 右空指针 → 后继；
- 区别仅在于**“前驱/后继”是哪种遍历下的顺序**。
5.2.3 空指针数量
- n 个节点的二叉树有 n+1 个空指针；
- 线索化后，这些空指针全部被利用，形成双向链表式结构（按遍历顺序）。
5.3 三种线索化对比
| 前序线索树 | 根 → 左 → 右 | – 根的前驱为空 – 最右叶节点的后继为空 | ★★ |
| 中序线索树 | 左 → 根 → 右 | – 最常用 – 形成有序双向链表（若为二叉排序树） | ★★★★ |
| 后序线索树 | 左 → 右 → 根 | – 根的后继为空 – 遍历起点为最左叶或最右叶 | ★★★ |
⚠️ 难点：后序线索树中，无法从根直接找到遍历起点，且后继查找较复杂。
5.4 经典应用场景
1. 高效遍历
- 中序线索树可实现无需栈/递归的 O(n) 时间、O(1) 空间遍历；
- 适用于嵌入式系统或内存受限场景。
2. 二叉排序树优化
- 中序线索化的 BST，可快速找到前驱/后继，用于范围查询、第 k 小等操作。
3. 表达式树求值
- 前序/后序线索化便于表达式遍历。
5.5 中序线索化二叉树代码
✅ 节点定义
// 线索二叉树节点结构
typedef struct ThreadNode {
char data; // 数据域（可根据需要改为 int 等）
struct ThreadNode *lchild, *rchild; // 左、右指针
int ltag, rtag; // 标志位：0 表示指针，1 表示线索
} ThreadNode, *ThreadTree;
📌 标志位含义：
- ltag == 0 → lchild 指向左孩子；
- ltag == 1 → lchild 指向前驱；
- rtag == 0 → rchild 指向右孩子；
- rtag == 1 → rchild 指向后继。
✅ 中序线索化主函数
// 全局变量 pre，用于记录刚刚访问过的节点（即当前节点的前驱）
ThreadNode *pre = NULL;
// 对以 p 为根的二叉树进行中序线索化
void InOrderThreading(ThreadTree &p) {
if (p != NULL) {
InThread(p); // 执行线索化
pre = NULL; // 线索化完成后重置 pre（可选，避免影响后续操作）
}
}
✅ 核心递归线索化函数（带详细注释）
// 递归进行中序线索化
void InThread(ThreadTree p) {
if (p == NULL) return;
// 1. 递归线索化左子树
InThread(p->lchild);
// 2. 处理当前节点 p
if (p->lchild == NULL) {
// 若左孩子为空，则将 lchild 改为指向前驱（即 pre）
p->ltag = 1;
p->lchild = pre; // 前驱是上一个访问的节点
}
if (pre != NULL && pre->rchild == NULL) {
// 若前驱节点 pre 的右孩子为空，则将其 rchild 改为指向当前节点 p（即后继）
pre->rtag = 1;
pre->rchild = p;
}
// 3. 更新 pre 为当前节点（为下一次递归做准备）
pre = p;
// 4. 递归线索化右子树
InThread(p->rchild);
}
✅ 使用示例
int main() {
ThreadTree root = /* 构建二叉树 */;
// 初始化 pre 为 NULL（也可在 InOrderThreading 内部处理）
pre = NULL;
// 执行中序线索化
InOrderThreading(root);
// 此时 root 指向的树已变为中序线索二叉树
return 0;
}
🔍 关键逻辑解析
| InThread(p->lchild) | 先处理左子树（中序：左 → 根 → 右） |
| p->lchild = pre | 当前节点左空 → 指向前驱（pre 是上一个被访问的节点） |
| pre->rchild = p | 前驱节点右空 → 指向当前节点（即其后继） |
| pre = p | 更新 pre，为下一个节点提供前驱信息 |
💡 为什么能建立双向线索？
- 当访问节点 A 时，pre 是 A 的前驱 B；
- 若 B 的右指针为空，则将其设为指向 A（B 的后继）；
- 同时，若 A 的左指针为空，则设为指向 B（A 的前驱）；
- 如此形成 双向链表式线索。
⚠️ 注意事项（408 考点）
✅ 中序线索树遍历（补充，常考）
// 中序遍历线索二叉树（非递归，O(1) 空间）
void InOrderTraverse_Thr(ThreadTree T) {
ThreadTree p = T;
if (!p) return;
// 找到中序遍历的第一个节点（最左节点）
while (p->ltag == 0) {
p = p->lchild;
}
// 遍历所有节点
while (p) {
visit(p); // 访问当前节点
if (p->rtag == 1) {
// 有后继线索，直接跳转
p = p->rchild;
} else {
// 无后继线索，进入右子树，并找其最左节点
p = p->rchild;
while (p && p->ltag == 0) {
p = p->lchild;
}
}
}
}
5. 易错点警示
| “线索可以指向任意节点” | ❌ 必须严格按遍历顺序指向前驱/后继 |
| “所有线索树都能 O(1) 找到遍历起点” | ❌ 后序线索树不能（需从根开始找最左/最右叶） |
| “线索化改变树的逻辑结构” | ❌ 仅改变存储结构，逻辑不变 |
| “虚线一定是指向后继” | ❌ 左虚线 = 前驱，右虚线 = 后继 |
六 考点跟踪
| 2010 | 第3题 | 线索二叉树，后序遍历 | ||
| 2013 | 第5题 | 线索二叉树，后序遍历 | ||
| 2014 | 第4题 | 线索二叉树，中序遍历 |
说明：本文内容基于公开资料整理，参考了包括但不限于《数据结构》（严蔚敏）、《计算机操作系统》（汤小丹）、《计算机网络》（谢希仁）、《计算机组成原理》（唐朔飞）等国内高校经典教材，以及其他国际权威著作。同时，借鉴了王道、天勤、启航等机构出版的计算机专业考研辅导系列丛书中的知识体系框架与典型题型分析思路。文中所有观点、例题解析及文字表述均为作者结合自身理解进行的归纳与重述，未直接复制任何出版物原文。内容仅用于学习交流，若有引用不当或疏漏之处，敬请指正。
