哈夫曼树构造

哈夫曼树构造：每次合并两棵最小树

权值越小的叶子通常越深；目标是让总带权路径长度最小。

1. 初始森林

例：叶子权值为 7, 3, 2, 1, 2。初始时，每个权值都是一棵只有根的二叉树。

73212

哈夫曼构造只看当前每棵树的根权值。每一轮从森林中拿出根权值最小的两棵树。

2. 第 1 轮：合并 1 和 2

73212

取出 1 和一个 2，生成新树，根权值为 1 + 2 = 3。

7323

左右孩子顺序任意。换左右只会改变编码中的 0/1，不改变 WPL。

3. 第 2 轮：合并 2 和 3

7323

当前最小的是 2 和 3，合并为新根 5。

735

这个 3 可能是上一轮形成的新树，也可能是原始叶子 3。若权值相同，选取不同会得到不同形态，但最小 WPL 不变。

4. 第 3、4 轮：继续合并

第 3 轮：合并 3 和 5 -> 8 森林变为：7, 8 第 4 轮：合并 7 和 8 -> 15 森林只剩一棵树，构造完成。

原始叶子有 5 个，因此合并 4 次，新增 4 个内部结点，总结点数为 2n - 1 = 9。

5. WPL 怎么算

按叶子深度计算。上图一种构造对应的深度可以是：

权值 7：深度 1 权值 3：深度 2 权值 2：深度 3 权值 1：深度 4 权值 2：深度 4 WPL = 7*1 + 3*2 + 2*3 + 1*4 + 2*4 = 31

小权值被放得更深，对总 WPL 的惩罚较小；大权值应尽量靠近根。

6. 对应 C 代码骨架

typedef struct { int weight; int parent; int lchild; int rchild; } HuffNode; // 每轮在 parent == -1 的根结点中选两个最小权值。 // 生成新结点后，把两个根的 parent 指向新结点。 for (int i = n; i < 2 * n - 1; ++i) { int a = -1, b = -1; SelectTwoMin(tree, i, &a, &b); tree[i].weight = tree[a].weight + tree[b].weight; tree[i].lchild = a; tree[i].rchild = b; tree[i].parent = -1; tree[a].parent = i; tree[b].parent = i; }