Question

霍夫曼算法

2010年9月三级数据库13题
（13）对于给出的一组权w＝{10, 12, 16, 21, 30},通过霍夫曼算法求出的扩充二叉树的带权外部路径长度

Answer 1

霍夫曼算法使用贪心法，先对数据按权值排序：
10 12 16 21 30 选取权值最小的两个得 10+12=22
16 21 22 30 同上，得 16+21=37
22 30 37 同上，得 22+30=52
37 52 同上，得 37+52=89
画出该二叉树知，其带权路径长为：10×3 + 12×3 + 16×2 + 21×2 +30×2 = 200

Answer 2

===================== 第1步 =====================
10
12
16
21
30

====================== 第2步 =====================
16
21
(10[0], 12[1])22
30

====================== 第3步 =====================
(10[0], 12[1])22
30
(16[0], 21[1])37

====================== 第4步 =====================
(16[0], 21[1])37
((10[00], 12[01]), 30[1])52

====================== 第5步 =====================
((16[00], 21[01]),((10[100], 12[101]), 30[11]))89

可以看到节点合并的次序和编码(方括号内的01串)路径的生成过程。