§06 树状结构
哈夫曼树
带权叶子构成森林，每轮取权值最小的两棵树合并（根权为两权之和），n 个叶子合并 n-1 次后 只剩一棵树——哈夫曼树。它让带权路径长度 WPL 最小：权大的叶子离根近、权小的离根远， 是哈夫曼编码（前缀编码）的基础。
哈夫曼树
伪代码
1
procedure HuffmanTree(w, n)
2
for i = 1 to n do 创建叶子 F[i]，权 w[i]
3
for k = 1 to n - 1 do
4
从 F 中选权最小的两棵树 i, j
5
合并为新树 t，权 = w[i] + w[j]
6
t 的左孩子 = i，右孩子 = j
7
删去 i, j，t 加入 F
8
end for
9
return F 中唯一的树 // 哈夫曼树
10
WPL = Σ 叶子权 × 路径长度