第九章 二叉树进阶与线索二叉树
各位同学，今天我们来聊聊二叉树里那些“进阶”的东西。说实话，二叉树本身并不复杂，但一旦涉及到线索化、哈夫曼编码这些概念，很多初学者就开始头疼了。我当年学的时候也一样，总觉得“线索”这词儿太抽象，直到自己动手写了一遍代码才恍然大悟——哦，原来就是利用空指针嘛。
一、线索二叉树的概念
先问大家一个问题：一个普通的二叉树，有多少个空指针？
答案是：n+1 个。其中 n 是节点数。你想想看，每个节点有两个指针域，总共 2n 个指针，但只有 n-1 条边（因为根节点没有父节点），所以空指针就是 2n - (n-1) = n+1 个。这些空指针，说白了就是浪费了。
线索二叉树的核心思想，就是把这些空指针利用起来，指向遍历序列中的前驱和后继节点。这样做的目的有两个：
- 提高空间利用率（空指针不再闲置）
- 加快遍历速度（不需要递归或栈，直接沿着线索走）
我个人习惯把线索二叉树理解成“给二叉树装上了导航”。普通二叉树遍历时，你走到一个叶子节点就不知道下一步该去哪了；而线索二叉树里，每个节点都告诉你“下一个是谁”。
关键概念：线索二叉树分为前序线索、中序线索和后序线索三种。最常用的是中序线索二叉树，因为中序遍历的结果是有序的（对于二叉搜索树而言）。
二、线索二叉树的构造
构造线索二叉树的过程，本质上就是在遍历的过程中，把空指针改成线索。我以中序线索化为例，给大家讲清楚。
首先，我们需要在节点结构体中增加两个标志位：
typedef struct ThreadNode {
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 0表示指向孩子，1表示指向前驱/后继
} ThreadNode, *ThreadTree;这里 ltag 和 rtag 就是“开关”。当 ltag=0 时，lchild 指向左孩子；当 ltag=1 时，lchild 指向前驱节点。rchild 同理。
中序线索化的核心代码是这样的：
void InThread(ThreadTree &p, ThreadTree &pre) {
if (p == NULL) return;
InThread(p->lchild, pre); // 线索化左子树
// 处理当前节点
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, pre); // 线索化右子树
}嗯，这里要注意一个细节：pre 指针始终指向“刚刚访问过的节点”。当遍历到当前节点 p 时，pre 就是 p 的前驱。如果 p 的左孩子为空，就把左指针指向前驱 pre；如果 pre 的右孩子为空，就把 pre 的右指针指向当前节点 p。
避坑指南：我曾经在写线索化代码时，忘记在递归调用前保存 pre 的值，结果线索全乱了。记住：pre 是引用传递，递归返回时 pre 已经更新了。
三、线索二叉树的遍历
线索二叉树的遍历，不需要递归，也不需要栈。你只需要找到第一个节点，然后沿着线索一直走就行了。
以中序线索二叉树为例：
// 找到以 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) {
for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
printf("%d ", p->data);
}
}你看，代码非常简洁。没有递归调用，没有栈溢出风险。我在嵌入式项目中特别喜欢用这种方式，因为嵌入式系统的栈空间通常很有限，递归深度稍微大一点就可能出问题。
性能对比：普通二叉树中序遍历的时间复杂度是 O(n)，空间复杂度是 O(h)（h 为树高）。线索二叉树中序遍历的时间复杂度同样是 O(n)，但空间复杂度降到了 O(1)。
四、哈夫曼树与哈夫曼编码
哈夫曼树，也叫最优二叉树。它的应用场景很明确：数据压缩。
我举个例子。假设你要传输一段文本，里面只有 A、B、C、D 四个字符，出现频率分别是 5、4、3、2。如果用固定长度的编码（比如 2 位二进制），每个字符需要 2 位，总共需要 (5+4+3+2)*2 = 28 位。
但哈夫曼编码可以根据频率分配不同长度的编码：频率高的用短编码，频率低的用长编码。这样总长度会更短。
构造哈夫曼树的步骤很简单：
- 把所有节点按权值放入最小堆（或优先队列）
- 每次取出两个权值最小的节点，合并成一个新节点，权值为两者之和
- 把新节点放回堆中
- 重复步骤 2-3，直到只剩一个节点（即根节点）
下面我用 SVG 画一张哈夫曼树的构造过程图，帮助大家理解：
构造完成后，从根节点到每个叶子节点的路径，就是该字符的哈夫曼编码。通常规定左分支为 0，右分支为 1。比如上图中，权值为 2 的叶子节点，路径是：根(14)→左(5)→左(2)，编码就是 00。
最终编码结果：
| 字符 | 频率 | 哈夫曼编码 |
|---|---|---|
| A | 5 | 01 |
| B | 4 | 10 |
| C | 3 | 11 |
| D | 2 | 00 |
总长度 = 5*2 + 4*2 + 3*2 + 2*2 = 28 位。咦？和固定长度编码一样？这是因为这个例子太特殊了，频率分布比较均匀。在实际应用中，比如英文文本中 'e' 的出现频率远高于 'z'，哈夫曼编码的优势就会非常明显。
注意事项：哈夫曼编码是前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀。这是解码时不产生歧义的关键。我曾经在项目中遇到过编码表传输错误导致解码失败的问题，后来加了 CRC 校验才解决。
五、总结
这一章我们讲了三个核心内容：
- 线索二叉树：利用空指针加速遍历，空间换时间？不，是空间和时间都优化了。
- 哈夫曼树：最优二叉树，用于数据压缩。
- 哈夫曼编码：变长编码，频率越高编码越短。
说实话，线索二叉树在实际工程中用得不算特别多，但它的思想——利用闲置资源——在嵌入式开发中非常常见。比如我做过的一个传感器数据采集系统，内存只有 64KB，每个字节都得精打细算，线索二叉树这种“废物利用”的思路就很有启发。
哈夫曼编码就不一样了，它是数据压缩领域的基石。从 JPEG 图片到 ZIP 压缩包，到处都有它的身影。你想想看，你每天发的微信图片，很可能就经过了哈夫曼编码的压缩。
好了，这一章就到这里。代码要多写，光看是学不会的。建议你自己动手实现一遍中序线索二叉树的构造和遍历，再写一个哈夫曼编码器。遇到问题很正常，调试的过程才是真正进步的过程。