七、线索二叉树：让空指针不再闲置
说到二叉树，你肯定遇到过这种情况——明明有那么多空指针，却白白浪费着。我刚开始学树结构时也觉得可惜，一个节点两个指针域，叶子节点全空着，这存储利用率也太低了。后来接触了线索二叉树，才明白前辈们早就想到了这个优化点。
7.1 线索化的概念
线索二叉树，说白了就是把那些空着的指针利用起来。左孩子为空时，让它指向前驱节点；右孩子为空时，让它指向后继节点。这样遍历的时候就不用递归或者栈了，直接顺着线索走就行。
但这里有个问题——我怎么知道一个指针是真正的孩子指针，还是线索？
嗯，解决办法很简单：每个节点加两个标志位。ltag 和 rtag，0 表示指向孩子，1 表示指向前驱/后继。
节点结构定义：
typedef struct ThreadNode {
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 0:孩子 1:线索
} ThreadNode, *ThreadTree;我个人习惯把 ltag 和 rtag 定义成 int 类型，虽然用 1 个 bit 就够了，但为了代码可读性，用 int 更直观。你在实际项目中如果追求极致内存，可以用位域，不过一般没必要。
7.2 中序线索二叉树的构建
构建线索二叉树的过程，本质上就是一次中序遍历，在遍历过程中把空指针改成线索。我当年第一次写这个代码时，犯了个低级错误——忘记处理最后一个节点的右指针。你想想看，最后一个节点没有后继，它的 rchild 应该指向 NULL，同时 rtag 置 1。
来看代码，我习惯用一个全局变量 pre 来记录上一个访问的节点：
ThreadNode *pre = NULL; // 全局变量，指向当前节点的前驱
void InThread(ThreadTree &p) {
if (p == NULL) return;
InThread(p->lchild); // 递归线索化左子树
// 处理当前节点
if (p->lchild == NULL) {
p->lchild = pre; // 左指针指向前驱
p->ltag = 1; // 标记为线索
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = p; // 前驱的右指针指向当前节点
pre->rtag = 1; // 标记为线索
}
pre = p; // 更新前驱
InThread(p->rchild); // 递归线索化右子树
}
void CreateInThread(ThreadTree T) {
pre = NULL;
if (T != NULL) {
InThread(T);
// 处理最后一个节点
if (pre->rchild == NULL) {
pre->rtag = 1;
}
}
}我曾经踩过的坑：递归线索化时，pre 指针的更新时机很重要。一定要在访问完当前节点、处理完线索后再更新 pre。如果顺序搞反了，线索会指向错误的前驱节点。调试这种 bug 特别痛苦，因为线索错误会导致遍历时死循环。
7.3 线索二叉树的遍历
线索化之后，遍历就变得很优雅了。不需要递归，不需要栈，顺着线索走就行。中序线索二叉树的遍历，核心就是找到第一个节点，然后不断找后继。
找第一个节点很简单——沿着左孩子一直走，直到 ltag 为 1 的那个节点：
ThreadNode *FirstNode(ThreadNode *p) {
while (p->ltag == 0) {
p = p->lchild;
}
return p;
}找后继节点呢？如果 rtag 为 1，说明右指针就是线索，直接返回 rchild。如果 rtag 为 0，说明有右子树，那么后继就是右子树中第一个被访问的节点：
ThreadNode *NextNode(ThreadNode *p) {
if (p->rtag == 1) {
return p->rchild; // 线索直接指向后继
} else {
return FirstNode(p->rchild); // 右子树的最左下节点
}
}有了这两个函数，中序遍历就简单了：
void InOrder(ThreadTree T) {
for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
printf("%d ", p->data);
}
}你看，这个 for 循环写得多清爽。没有递归调用，没有栈操作，时间复杂度 O(n)，空间复杂度 O(1)。
小技巧：如果你需要反向遍历（从最后一个节点往前），可以对称地写 LastNode 和 PreNode 函数。LastNode 沿着右孩子走到最右，PreNode 判断左线索或左子树的最右下节点。这在某些场景下很有用，比如需要双向遍历的时候。
7.4 知识体系总览
线索二叉树的核心逻辑，我画了张图帮你理清思路：
7.5 线索二叉树的优缺点
| 优点 | 缺点 |
|---|---|
| 遍历不需要递归或栈，空间效率高 | 插入和删除节点时需要维护线索，操作复杂 |
| 可以快速找到任意节点的前驱和后继 | 需要额外的两个标志位，存储开销略增 |
| 中序遍历时间复杂度 O(n)，空间 O(1) | 线索化过程本身需要递归，构建时仍有栈开销 |
说实话，线索二叉树在实际工程中用得不算特别多。但它的思想很巧妙——把浪费的资源利用起来。我在做嵌入式系统开发时，遇到过内存只有几十 KB 的场景，那时候用线索二叉树替代递归遍历，确实省下了不少栈空间。
如果你现在正在学习数据结构，我建议你把线索二叉树的代码亲手敲一遍。尤其是那个 pre 指针的传递逻辑，理解了它，你对递归和指针的理解会上一个台阶。
公众号：蓝海资料掘金营，微信 deep3321