23、线索二叉树：线索二叉树的概念、中序线索化、线索二叉树的遍历
各位同学，今天我们来聊一个挺有意思的话题——线索二叉树。
说实话，我第一次接触这个概念的时候，心里想的是：“二叉树不是好好的吗？干嘛要加什么线索？” 后来在项目中踩了坑，才明白这东西有多实用。
23.1 线索二叉树的概念
先说说普通二叉树的一个痛点。
你想想看，一棵二叉树有 n 个节点，那它就有 2n 个指针域（左右孩子指针）。但实际用到的只有 n-1 个（根节点没有父节点指向它，其他每个节点都有一个父节点指向它）。
也就是说，有 n+1 个指针域是空的。浪费啊！
核心思想：把这些空指针利用起来，指向遍历序列中的前驱或后继节点。这就是“线索化”。
我当年做嵌入式文件系统的时候，需要频繁遍历目录树。普通二叉树每次遍历都要递归，栈开销很大。线索化之后，遍历就像走链表一样顺畅——嗯，这个后面细说。
线索二叉树有几个关键定义：
- 前驱线索：左孩子指针为空时，指向遍历序列中的前驱节点
- 后继线索：右孩子指针为空时，指向遍历序列中的后继节点
- 标志位：每个节点需要两个标志位（ltag, rtag），区分指针是孩子还是线索
节点结构长这样：
typedef struct ThreadNode {
int data; // 数据域
struct ThreadNode *lchild; // 左孩子或前驱线索
struct ThreadNode *rchild; // 右孩子或后继线索
int ltag; // 0:左孩子, 1:前驱线索
int rtag; // 0:右孩子, 1:后继线索
} ThreadNode, *ThreadTree;ltag 和 rtag 就是“身份标识”。ltag=0 表示 lchild 指向左孩子，ltag=1 表示 lchild 指向前驱。rtag 同理。
我的习惯：定义结构体时，把标志位紧挨着指针放，这样内存布局更紧凑。嵌入式环境里，能省一点是一点。
23.2 中序线索化
线索化有很多种：前序线索化、中序线索化、后序线索化。我个人最常用的是中序线索化，因为中序遍历在二叉搜索树里太常见了。
中序线索化的过程，说白了就是：在中序遍历的过程中，把空指针改成线索。
具体怎么做？
- 定义一个全局指针
pre，指向当前节点的前驱 - 递归中序遍历二叉树
- 访问当前节点时，检查它的左指针：如果为空，就指向前驱（pre），ltag 置 1
- 检查 pre 的右指针：如果为空，就指向当前节点，rtag 置 1
- 更新 pre = 当前节点
看代码：
// 全局变量，指向当前节点的前驱
ThreadNode *pre = NULL;
// 中序线索化
void InThread(ThreadTree p) {
if (p == NULL) return;
// 1. 线索化左子树
InThread(p->lchild);
// 2. 处理当前节点
if (p->lchild == NULL) {
p->lchild = pre; // 左指针指向前驱
p->ltag = 1; // 标记为线索
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = p; // 前驱的右指针指向当前节点
pre->rtag = 1; // 标记为线索
}
pre = p; // 更新前驱
// 3. 线索化右子树
InThread(p->rchild);
}
// 创建线索二叉树（带头节点）
void CreateInThread(ThreadTree T) {
pre = NULL;
if (T != NULL) {
InThread(T);
// 处理最后一个节点
if (pre->rchild == NULL) {
pre->rtag = 1;
}
}
}注意：线索化完成后，最后一个节点的右指针可能还是空的。记得把它的 rtag 置 1，表示它是线索（指向 NULL）。
我曾经在调试一个内存泄漏问题时，发现遍历到最后一个节点就死循环了——就是因为没处理这个边界情况。
23.3 线索二叉树的遍历
线索化之后，遍历就变得非常优雅了。不需要递归，不需要栈，直接沿着线索走就行。
中序线索二叉树的遍历分两步：
- 找到中序遍历的第一个节点（最左下角的节点）
- 不断找后继节点，直到结束
找第一个节点：
// 找到以 p 为根的子树中，中序遍历的第一个节点
ThreadNode *FirstNode(ThreadNode *p) {
while (p->ltag == 0) { // 一直往左走，直到左指针是线索
p = p->lchild;
}
return p;
}找后继节点：
// 找到 p 在中序遍历中的后继节点
ThreadNode *NextNode(ThreadNode *p) {
if (p->rtag == 1) {
// 右指针是线索，直接返回后继
return p->rchild;
} else {
// 右指针是孩子，返回右子树中第一个节点
return FirstNode(p->rchild);
}
}完整遍历：
// 中序遍历线索二叉树（非递归）
void InOrder(ThreadTree T) {
ThreadNode *p = FirstNode(T);
while (p != NULL) {
printf("%d ", p->data);
p = NextNode(p);
}
}你看，代码多简洁！没有递归调用，没有栈溢出风险。在嵌入式环境里，这简直就是福音。
避坑指南：我曾经在 RTOS 的任务调度器里用线索二叉树管理定时器。一开始用递归遍历，结果任务栈一深就崩了。改成线索遍历后，稳定多了。记住：递归虽好，但不要贪杯。
23.4 知识体系图
下面这张图帮你理清线索二叉树的核心逻辑：
23.5 总结与对比
| 特性 | 普通二叉树 | 线索二叉树 |
|---|---|---|
| 空间利用率 | n+1 个空指针浪费 | 空指针全部利用 |
| 遍历方式 | 递归/栈，有栈溢出风险 | 非递归，无栈开销 |
| 插入/删除 | 简单，只需改孩子指针 | 需要同时维护线索，稍复杂 |
| 适用场景 | 频繁增删改 | 频繁遍历、查找前驱后继 |
嗯，总结一下：线索二叉树不是银弹，但在特定场景下非常好用。我个人建议：如果你的二叉树建好后很少改动，但需要频繁遍历或找前驱后继，那就用线索二叉树。反之，如果树结构经常变，普通二叉树更省心。
最后说一句：代码写多了你会发现，很多“高级”数据结构，其实都是在解决某个具体痛点。线索二叉树解决的就是“遍历效率”和“空间浪费”这两个痛点。理解了痛点，你就理解了它的精髓。