第十一章：线索二叉树——让空指针不再闲置
各位同学，今天我们来聊一个很有意思的话题——线索二叉树。
说实话，我第一次接触线索二叉树的时候，心里想的是：“这玩意儿有必要吗？” 但后来在项目中吃了不少苦头，才明白它的价值。嗯，咱们慢慢聊。
11.1 线索化的概念
先问大家一个问题：一棵普通的二叉树，有多少个空指针？
你想想看，一棵有 n 个结点的二叉树，总共有 2n 个指针域。但实际用到的只有 n-1 个（根结点没有父指针）。也就是说，有 n+1 个指针是空的。浪费啊！
我当年做嵌入式文件系统时，需要频繁遍历目录树。每次递归遍历，栈开销大得吓人。后来我就在想：“这些空指针能不能利用起来？”
线索化，说白了就是：把空指针改成指向遍历序列中的前驱或后继结点。
- 左空指针 → 指向前驱结点
- 右空指针 → 指向后继结点
这样，你就不需要递归或栈，直接沿着线索走一遍就行。
核心要点：线索化后的二叉树，遍历时间复杂度仍然是 O(n)，但空间复杂度从 O(n)（递归栈）降到了 O(1)。
11.2 中序线索二叉树的构造
我个人习惯用中序线索化，因为中序遍历在二叉搜索树里太常用了。构造过程其实不复杂，核心就是一次中序遍历，边遍历边改指针。
先看结点结构：
typedef struct ThreadNode {
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 0表示孩子，1表示线索
} ThreadNode, *ThreadTree;这里多了两个标志位：ltag 和 rtag。它们告诉程序：这个指针到底指向孩子还是线索。
构造过程我画了一张图，大家看看：
构造代码我贴一下，大家注意看 pre 这个指针的用法：
void InThread(ThreadTree p, ThreadTree &pre) {
if (p == NULL) return;
// 1. 线索化左子树
InThread(p->lchild, pre);
// 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, pre);
}小技巧：我习惯在递归前先判断 p == NULL，而不是在调用处判断。这样代码更干净，不容易漏判。
11.3 线索二叉树的遍历
线索化之后，遍历就变得非常优雅了。不需要递归，不需要栈，一个循环搞定。
中序线索遍历的思路：
- 找到最左边的结点（第一个要访问的结点）
- 访问它
- 如果它有右线索，直接沿线索走
- 如果它有右孩子，去右子树找最左边
- 重复直到 NULL
void InOrderTraverse(ThreadTree T) {
ThreadTree p = T;
while (p != NULL) {
// 找到最左边的结点
while (p->ltag == 0)
p = p->lchild;
// 访问结点
printf("%d ", p->data);
// 沿线索走
while (p->rtag == 1) {
p = p->rchild;
if (p == NULL) break;
printf("%d ", p->data);
}
// 去右子树
p = p->rchild;
}
}这段代码我当年调试了整整一个下午。为什么？因为 rtag == 1 时，我忘了判断 p == NULL，结果一直死循环。嗯，边界条件永远是魔鬼。
11.4 前序与后序线索化简介
中序线索化最常用，但前序和后序也有用武之地。
| 类型 | 线索指向 | 遍历特点 | 我遇到的场景 |
|---|---|---|---|
| 前序线索化 | 前驱、后继 | 先访问根，再沿线索走 | 表达式树求值 |
| 中序线索化 | 前驱、后继 | 左-根-右，最自然 | 二叉搜索树遍历 |
| 后序线索化 | 前驱、后继 | 需要栈辅助（较复杂） | 目录树删除 |
前序线索化代码和中序很像，只是把「处理当前结点」挪到了递归左右子树之前：
void PreThread(ThreadTree p, ThreadTree &pre) {
if (p == NULL) return;
// 处理当前结点（前序：先处理根）
if (p->lchild == NULL) {
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
// 注意：这里要判断 ltag，避免走进线索
if (p->ltag == 0)
PreThread(p->lchild, pre);
if (p->rtag == 0)
PreThread(p->rchild, pre);
}我曾经踩过的坑：前序线索化时，如果不判断 ltag == 0 就直接递归左子树，会沿着线索回到父结点，造成无限递归。这个 bug 我查了整整两天才找到。
后序线索化更复杂一些。因为后序遍历是「左-右-根」，线索化后遍历时，你没法简单地沿线索走完——需要栈来辅助。我个人在实际项目中很少用后序线索化，除非内存极度受限且必须做后序遍历。
11.5 总结一下
线索二叉树的核心思想就一句话：让空指针干活，别闲着。
- 中序线索化最实用，构造和遍历都简单
- 前序线索化注意递归时别走进线索
- 后序线索化复杂，非必要不用
我记得有一次做嵌入式文件系统，内存只有 64KB，递归遍历目录树直接栈溢出。改成线索二叉树后，不仅省了栈空间，遍历速度还快了 30%。有时候，好的数据结构比好的算法更管用。