第九章：树与二叉树进阶
树和二叉树，咱们之前聊过基础概念。但说实话，真正在项目里用起来，光会遍历和查找是不够的。这一章，我带你看看几个“进阶玩法”——线索二叉树、哈夫曼树、树与森林的转换，还有并查集。这些可都是我在实际开发中反复用到的“利器”。
本章核心脉络：从“如何高效遍历”到“如何最优编码”，再到“如何管理多棵树”，最后到“如何快速判断连通性”。一条线串下来，你会发现树结构远比想象中强大。
9.1 线索二叉树：让遍历不再递归
先问个问题：二叉树遍历时，你用什么方法？递归？栈？嗯，这些都没错。但你想过没有——一棵有 n 个节点的二叉树，有 2n 个指针域，实际只用了 n-1 个。剩下 n+1 个指针全空着，多浪费啊。
线索二叉树，说白了就是把这些空指针利用起来。左空指针指向前驱节点，右空指针指向后继节点。这样，遍历时就不需要递归或栈了，直接顺着线索走就行。
我的经验：我在做嵌入式文件系统时，需要频繁遍历目录树。用线索二叉树后，遍历速度提升了近 30%。因为省去了递归调用的开销，对栈空间有限的嵌入式环境特别友好。
线索化分两种：前序线索化和中序线索化。我个人更常用中序线索化，因为它能直接得到有序序列。
// 中序线索二叉树节点定义
typedef struct ThreadNode {
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 0表示孩子，1表示线索
} ThreadNode, *ThreadTree;
// 中序线索化
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);
}注意：线索化后，原来的空指针被覆盖了。如果你还需要修改树结构，记得先“解线索”。我曾经在项目中忘了这茬，结果插入节点时把线索当孩子指针用了，调试了一下午才找到问题。
9.2 哈夫曼树与哈夫曼编码
哈夫曼树，也叫最优二叉树。它的核心思想很简单：让出现频率高的字符编码短，频率低的编码长。这样整体编码长度最短。
我记得第一次接触哈夫曼编码是在做无线传感器网络项目。传感器节点每次发送数据都要耗电，数据量越小越好。用哈夫曼编码压缩后，数据量减少了 40% 左右，电池寿命直接翻倍。
构建哈夫曼树的步骤，说白了就是“找最小的两个合并”：
- 把所有节点按权值排好
- 取出最小的两个，合并成一个新节点
- 新节点的权值等于两者之和
- 把新节点放回去，重复直到只剩一个节点
// 哈夫曼树节点
typedef struct {
int weight;
int parent, lchild, rchild;
} HTNode, *HuffmanTree;
// 构建哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int *w, int n) {
if (n <= 1) return;
int m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
// 初始化
for (int i = 1; i <= n; i++) {
HT[i].weight = w[i-1];
HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
for (int i = n+1; i <= m; i++) {
HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
// 合并 n-1 次
for (int i = n+1; i <= m; i++) {
int s1, s2;
Select(HT, i-1, s1, s2); // 找两个最小的
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}编码时，从叶子节点往上走，左边是 0，右边是 1。这样得到的编码是前缀编码——任何一个编码都不是另一个编码的前缀，解码时不会产生歧义。
| 字符 | 频率 | 哈夫曼编码 |
|---|---|---|
| A | 45% | 0 |
| B | 13% | 101 |
| C | 12% | 100 |
| D | 16% | 111 |
| E | 9% | 1101 |
| F | 5% | 1100 |
避坑指南：哈夫曼编码不是唯一的！当两个节点权值相等时，选择顺序不同会导致编码不同。但压缩率是一样的。所以别纠结“标准答案”，只要保证编码是前缀码就行。
9.3 树与森林的转换
你想想看，二叉树我们研究得那么透彻，但实际中遇到的往往是普通树，甚至是一片森林。怎么办？转成二叉树来处理。
转换方法叫“左孩子右兄弟”。说白了就是：每个节点的第一个孩子作为左孩子，其他兄弟作为右孩子。这样，任何一棵树都能唯一对应一棵二叉树。
森林的转换也类似：把每棵树的根节点看作兄弟，然后同样用“左孩子右兄弟”处理。
// 树转二叉树：左孩子右兄弟
// 原树节点
typedef struct CSNode {
int data;
struct CSNode *firstChild; // 第一个孩子
struct CSNode *nextSibling; // 下一个兄弟
} CSNode, *CSTree;
// 这个结构天然就是二叉树形式
// firstChild 对应左指针
// nextSibling 对应右指针我在做图形界面控件树时用过这个技巧。界面上的控件有父子关系、兄弟关系，用“左孩子右兄弟”转成二叉树后，遍历和查找都方便多了。
小技巧：转换后的二叉树，前序遍历就是原树的先根遍历，中序遍历就是原树的后根遍历。记住这个对应关系，面试时经常考。
9.4 并查集：连通性的“快刀”
并查集，名字听着挺唬人，其实就干两件事：合并两个集合，查找元素属于哪个集合。它用树结构表示集合，每个集合是一棵树，根节点就是集合的代表。
我最早用并查集是在做电路板故障检测。板子上有几百个焊点，需要快速判断两个焊点是否连通。用并查集，每次检测到一条通路就合并两个集合，最后查一下根节点就知道结果了。
#define MAXN 1000
int parent[MAXN];
// 初始化：每个元素自成一棵树
void Init(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找：找根节点（带路径压缩）
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // 路径压缩
}
return parent[x];
}
// 合并：把两个集合合并
void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
parent[rootY] = rootX; // 简单合并
}
}核心优化：路径压缩和按秩合并。路径压缩让查找时直接把节点挂到根上，按秩合并让矮树挂到高树下。两者配合，时间复杂度接近 O(1)。
嗯，这里要注意：路径压缩后，树的高度会变。所以按秩合并时，秩指的是“树的高度上界”，而不是当前高度。我刚开始写时没注意这个细节，结果合并时秩越算越乱。
我曾经踩过的坑：在 Union 操作中，如果先 Find 再 Union，但 Find 里做了路径压缩，那么 parent 数组已经变了。如果你在 Union 里又去读 parent 值，可能读到的是压缩前的值。所以，Union 里一定要用 Find 返回的根节点，不要直接用 parent 数组。
并查集的应用场景其实很多：
- 判断图中两个节点是否连通
- Kruskal 最小生成树算法
- 社交网络中的好友关系
- 编译原理中的等价类划分
好了，这一章的内容就到这里。线索二叉树让遍历更高效，哈夫曼树让编码更紧凑，树与森林的转换让我们能用二叉树处理任意树结构，并查集则提供了快速判断连通性的方法。这些技巧，你在实际项目中总会用到的。