树、森林及其应用

本节导读

上一节讲的是二叉树，这一节把视线放回一般的树和森林：怎么存、怎么和二叉树互相转换、怎么遍历；再讲大纲列的三个应用——哈夫曼树和哈夫曼编码、并查集、堆。其中「堆及其应用」是常见资料称 2025 年版新增的条目。

学完你应该能把一片森林画成二叉树并写出遍历序列，能构造哈夫曼树、算出带权路径长度，能写出并查集的查找与合并，能用筛选法建堆并完成插入和删除。

树的存储结构

表示法	存法	长处	短处
双亲表示法	数组，每个结点记录双亲的下标，根记 −1	找双亲 $O(1)$O(1)，找根只需沿双亲向上	找孩子要扫描整个数组
孩子表示法	每个结点挂一条孩子链表	找孩子方便	找双亲要遍历各条链表
孩子兄弟表示法	二叉链表：左指针指第一个孩子，右指针指下一个兄弟	能直接套用二叉树的算法	找双亲不方便

孩子兄弟表示法就是树与二叉树转换的依据：树中一个结点没有孩子，在二叉链表里就是它的左指针为空，所以树（森林）的叶结点个数等于对应二叉树中左指针为空的结点个数。

树、森林与二叉树的转换

• 树变二叉树：每个结点的第一个孩子作左孩子，它右边的兄弟作右孩子（「左孩子右兄弟」）。根没有兄弟，所以得到的二叉树根没有右子树。
• 森林变二叉树：每棵树先各自变成二叉树，再把第二棵的根作为第一棵根的右孩子，第三棵的根作为第二棵根的右孩子，依此类推。
• 二叉树变森林：反过来，根及其右链上的结点分别是各棵树的根。

遍历的对应关系：

树	森林	对应二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历（有的教材叫后序遍历）	中序遍历

树还有层次遍历，按层从上到下、每层从左到右访问。

哈夫曼树和哈夫曼编码

结点的带权路径长度是根到它的路径长度（边数）乘它的权，树的带权路径长度 $\mathrm{WPL} = \sum w_i l_i$WPL=∑wi​li​ 是所有叶结点之和。n 个权值构造的 WPL 最小的二叉树叫哈夫曼树（最优二叉树）。

构造方法：把 n 个权值看成 n 棵只有根的树；每次选两棵根权值最小的树合并成一棵新树，新根的权值为两者之和；重复 n − 1 次。由此可知：

• 哈夫曼树共有 2n − 1 个结点，其中分支结点 n − 1 个，没有度为 1 的结点；
• 权值越小的叶结点离根越远；
• WPL 也等于所有分支结点的权值之和（每次合并时，两棵子树里的叶子都加深一层）。

哈夫曼编码：在哈夫曼树中左分支记 0、右分支记 1，根到叶的 0、1 串就是该字符的编码。它是前缀编码——任何一个编码都不是另一个编码的前缀，所以译码不会有歧义。同权值时合并的选法不同，编码可能不唯一，但 WPL 相同。

并查集

并查集用双亲表示法的森林表示若干个不相交的集合，每棵树是一个集合、根是代表元。两个基本操作：Find(x) 沿双亲找到根；Union(a, b) 把一个根挂到另一个根下面。

int parent[MAXN];                     /* 根的 parent 存「负的元素个数」 */
int Find(int x) {                     /* 找根，并做路径压缩 */
    int root = x;
    while (parent[root] >= 0) root = parent[root];
    while (x != root) {               /* 路径上的结点直接挂到根下 */
        int up = parent[x];
        parent[x] = root;
        x = up;
    }
    return root;
}
void Union(int a, int b) {            /* a、b 是不同集合的根，小树并到大树 */
    if (parent[a] <= parent[b]) {     /* a 的元素不比 b 少 */
        parent[a] += parent[b];
        parent[b] = a;
    } else {
        parent[b] += parent[a];
        parent[a] = b;
    }
}

不做任何优化时，树可能退化成一条链，Find 最坏 $O(n)$O(n)。小树并到大树（按大小合并）之后，n 个元素的树高（只有根时为 1）不超过 $\lfloor \log_2 n \rfloor + 1$⌊log2​n⌋+1；再加上路径压缩，每次操作的均摊代价几乎是常数。并查集的典型应用：判断图的连通分量、判断加一条边会不会形成回路（第 7 节的 Kruskal 算法就要用）。

堆

定义与调整

n 个关键字的序列，按完全二叉树编号（1 至 n）存放，若每个结点都不小于它的孩子，即 $k_i \ge k_{2i}$ki​≥k2i​ 且 $k_i \ge k_{2i+1}$ki​≥k2i+1​，叫大根堆；都不大于孩子叫小根堆。堆顶是最大（或最小）元素。

操作	做法	时间
建堆（筛选法）	从最后一个分支结点 $\lfloor n/2 \rfloor$⌊n/2⌋ 起到根，逐个向下调整	$O(n)$O(n)
插入	放到末尾，与双亲比较，不合要求就交换，逐层上浮	$O(\log_2 n)$O(log2​n)
删除堆顶	用最后一个元素替换堆顶，再从根向下调整	$O(\log_2 n)$O(log2​n)

向下调整（以大根堆为例）：把当前结点与较大的孩子比较，孩子更大就交换，一直下沉到不能再沉。

void sift_down(int H[], int i, int n) {   /* 大根堆 H[1..n]，调整以 i 为根的子树 */
    int x = H[i];
    for (int j = 2 * i; j <= n; j = j * 2) {
        if (j < n && H[j + 1] > H[j]) j++;   /* 选较大的孩子 */
        if (x >= H[j]) break;
        H[i] = H[j];                         /* 孩子上移一层 */
        i = j;
    }
    H[i] = x;
}

堆的应用

堆排序（第 10 节）、优先队列（每次取出优先级最高的元素，操作系统的优先级调度、图算法里取当前最小距离的顶点都能用它）、在大量数据中选出最大或最小的若干个。

易错提醒

• ❌ 树的后根遍历对应二叉树的后序遍历。✅ 树的后根遍历对应二叉树的中序遍历。因为在孩子兄弟表示里，一个结点的全部孩子在它的左子树里，右子树是它的兄弟。

• ❌ 哈夫曼树中可以有度为 1 的结点。✅ 哈夫曼树每次都是两棵合并，没有度为 1 的结点。因为每个分支结点都由一次合并产生，恰有两个孩子。

• ❌ WPL 是所有结点（含叶结点）权值之和。✅ WPL 是叶结点权值乘路径长度之和，等于分支结点权值之和。因为叶结点自己的权值不随合并累加。

• ❌ 筛选法建堆从第 1 个结点开始向下调整。✅ 从最后一个分支结点 $\lfloor n/2 \rfloor$⌊n/2⌋ 开始，倒着调整到根。因为向下调整要求左右子树已经是堆。

• ❌ 并查集合并时，把两个元素本身直接相连。✅ 先各自 Find 到根，再把一个根挂到另一个根下。因为集合由根代表，元素之间直接相连会破坏树的结构。

例题精讲

例题 1（计算）

给定权值 2、3、5、7、11、13，构造哈夫曼树并求 WPL。

答题要点示范：合并过程为 2 + 3 = 5；5 + 5 = 10；7 + 10 = 17；11 + 13 = 24；17 + 24 = 41。WPL = 分支结点之和 = 5 + 10 + 17 + 24 + 41 = 97。逐个核对：7、11、13 的路径长度为 2，权值 5 的叶子为 3，2 和 3 为 4，$7 \times 2 + 11 \times 2 + 13 \times 2 + 5 \times 3 + 2 \times 4 + 3 \times 4 = 97$7×2+11×2+13×2+5×3+2×4+3×4=97。

点评：第二步有两个 5（一个是叶子、一个是新结点），先选哪个都行，树形可能不同，WPL 一样。

例题 2（建堆）

用筛选法把序列 15、9、27、4、33、18、6 建成大根堆，写出结果。

答题要点示范：n = 7，从第 3 个结点开始：27 的孩子是 18、6，不动；第 2 个结点 9 的孩子是 4、33，与 33 交换，得 15、33、27、4、9、18、6；第 1 个结点 15 的孩子是 33、27，与 33 交换，15 下沉到第 2 个位置，孩子是 4、9，不再交换。结果为 33、15、27、4、9、18、6。

例题 3（森林与二叉树）

森林由三棵树组成：A 的孩子依次是 B、C、D；E 的孩子是 F；G 的孩子依次是 H、I。把它转换成二叉树，写出二叉树的先序和中序序列。

答题要点示范：A 的左孩子 B，B 的右孩子 C，C 的右孩子 D；A 的右孩子 E，E 的左孩子 F；E 的右孩子 G，G 的左孩子 H，H 的右孩子 I。先序：A B C D E F G H I，就是森林的先序遍历；中序：B C D A F E H I G，就是森林的中序遍历。

本节小结

• 树的三种存储：双亲表示、孩子表示、孩子兄弟表示（二叉链表）；树的叶结点对应二叉树左指针为空的结点。
• 「左孩子右兄弟」转二叉树；森林各棵依次挂在右链上；树的先根、后根对应二叉树的先序、中序。
• 哈夫曼树：每次合并两个最小的，2n − 1 个结点、无度为 1 的结点，WPL 等于分支结点权值之和；哈夫曼编码是前缀编码。
• 并查集：Find 找根、Union 挂根；小树并大树加路径压缩。
• 堆：筛选法建堆 $O(n)$O(n)，插入上浮、删除下沉各 $O(\log_2 n)$O(log2​n)。