第十一章：二叉树的应用——线索二叉树、哈夫曼树与并查集
这一章咱们来聊三个非常实用的数据结构。说实话，这三个东西在教科书里经常被放在一起，但它们的应用场景其实完全不同。我当年学的时候也觉得有点跳跃，后来做项目多了才明白——它们分别解决了三个经典问题：遍历加速、数据压缩、集合管理。
好，咱们一个一个来。
11.1 线索二叉树：让遍历不再依赖递归
先问个问题：你写二叉树遍历的时候，是不是经常用递归？递归确实好写，但有个毛病——栈开销大，而且你没法快速找到某个节点的前驱和后继。比如中序遍历，你拿到一个节点，想知道它的“下一个”是谁，如果不从头递归一遍，根本不知道。
线索二叉树就是来解决这个问题的。说白了，它把那些空闲的左右指针利用起来，指向遍历序列中的前驱和后继。
11.1.1 线索化的核心思想
一个普通的二叉树节点，左右孩子指针不一定都用得上。叶子节点两个指针都是NULL，单孩子节点有一个是NULL。这些空指针，浪费了大概一半的空间。
线索化的做法是：
- 如果左指针为空，就指向前驱节点
- 如果右指针为空，就指向后继节点
- 加两个标志位
ltag和rtag，区分是指向孩子还是线索
节点结构定义：
typedef struct ThreadNode {
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 0表示孩子，1表示线索
} ThreadNode, *ThreadTree;嗯，这里要注意：ltag == 0 时，lchild 指向左孩子；ltag == 1 时，lchild 指向前驱。右指针同理。
11.1.2 中序线索化的构造过程
我个人习惯用中序线索化，因为中序遍历用得最多。构造过程其实就是在中序遍历的过程中，记录前驱节点，然后把当前节点的空指针指回去。
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); // 线索化右子树
}我在项目中遇到过一个问题：线索化之后，如果你修改了树的结构（比如插入删除节点），线索就全乱了。所以线索二叉树适合静态树，不适合频繁修改的场景。
小技巧：线索化之后，中序遍历可以不用递归，直接循环找后继就行。代码写起来像链表遍历，效率高很多。
11.2 哈夫曼树与哈夫曼编码：数据压缩的经典方案
说到数据压缩，你肯定听过ZIP、RAR这些。它们的底层原理之一就是哈夫曼编码。哈夫曼树，也叫最优二叉树，核心思想很简单：出现频率高的字符用短编码，频率低的用长编码。
11.2.1 哈夫曼树的构造
构造过程其实是个贪心算法：每次从森林中选两个权值最小的树合并。我刚开始学的时候觉得这有什么难的？后来自己手写才发现，选最小两个节点这一步，如果用数组每次扫描，效率很低。实际项目中我一般用最小堆来优化。
构造步骤：
- 把所有节点按权值放入最小堆
- 弹出两个最小的，合并成一个新节点，权值相加
- 新节点入堆
- 重复直到只剩一个节点
哈夫曼树节点定义：
typedef struct HuffmanNode {
int weight;
int parent, lchild, rchild; // 用数组下标表示
} HuffmanNode;
// 构造函数（核心逻辑）
void CreateHuffmanTree(HuffmanNode huffTree[], int n) {
// 初始化所有节点
for (int i = 0; i < 2*n - 1; i++) {
huffTree[i].parent = -1;
huffTree[i].lchild = -1;
huffTree[i].rchild = -1;
}
// 每次选两个最小的
for (int i = n; i < 2*n - 1; i++) {
int min1 = -1, min2 = -1;
// 找两个最小的无父节点
for (int j = 0; j < i; j++) {
if (huffTree[j].parent == -1) {
if (min1 == -1 || huffTree[j].weight < huffTree[min1].weight) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || huffTree[j].weight < huffTree[min2].weight) {
min2 = j;
}
}
}
huffTree[i].weight = huffTree[min1].weight + huffTree[min2].weight;
huffTree[i].lchild = min1;
huffTree[i].rchild = min2;
huffTree[min1].parent = i;
huffTree[min2].parent = i;
}
}我曾经在一个嵌入式项目里用哈夫曼编码压缩传感器数据。当时内存只有64KB，压缩率大概能到60%左右。不过要注意，哈夫曼编码需要保存编码表，如果数据量太小，编码表本身的开销可能抵消压缩收益。
11.2.2 哈夫曼编码的生成
从根节点到叶子节点的路径，左分支为0，右分支为1，就得到了每个字符的编码。注意：哈夫曼编码是前缀编码，任何一个编码都不是另一个编码的前缀，所以解码时不会产生歧义。
避坑指南：我曾经犯过一个错误——直接用递归生成编码，结果栈溢出。因为树可能很深（比如所有字符频率都差不多）。后来改成迭代方式，用数组模拟栈，稳得很。
11.3 并查集：高效管理不相交集合
并查集这个名字听起来有点学术，其实它的用途很直观：判断两个元素是否在同一个集合里，以及合并两个集合。比如社交网络里的“好友圈”、图论中的连通分量判断，都用得到。
11.3.1 基本操作
并查集的核心就三个操作：
- 初始化：每个元素自成一个集合
- 查找（Find）：找到元素所属集合的代表元
- 合并（Union）：把两个集合合并成一个
最简单的实现就是用数组，下标表示元素，值表示父节点。根节点的父节点指向自己。
#define MAXN 1000
int parent[MAXN];
void init(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i; // 每个元素都是自己的根
}
}
int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootY] = rootX; // 简单合并
}
}这个版本能工作，但效率不行。你想想看，如果树退化成一条链，find 操作就是O(n)的。我早期写代码就吃过这个亏，数据量一上来直接超时。
11.3.2 路径压缩与按秩合并
两个优化，让并查集几乎变成常数时间：
路径压缩：在 find 的时候，把路径上所有节点直接挂到根节点下面。
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 递归压缩
}
return parent[x];
}按秩合并：合并时，把高度低的树挂到高度高的树下面，避免树长高。
int rank[MAXN]; // 记录树的高度
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}个人经验：路径压缩和按秩合并一起用，时间复杂度接近O(α(n))，α(n)是阿克曼函数的反函数，增长极慢。说白了，对于任何实际数据规模，都可以认为是常数时间。
11.4 本章知识体系总览
下面这张图把三个知识点的核心逻辑串起来了，你可以对照着复习：
好了，这一章的内容就到这里。线索二叉树、哈夫曼树、并查集，每个都是很实用的工具。你写代码的时候，遇到遍历性能瓶颈，想想线索二叉树；遇到数据压缩需求，试试哈夫曼编码；遇到集合合并查询，直接用并查集加路径压缩。嗯，多练练，这些都会变成你的肌肉记忆。