表格
| 项目 | 成绩 | 百分比 |
|---|---|---|
| A | 不及格 | 10% |
| B | 及格 | 15% |
| C | 中 | 30% |
| D | 良 | 40% |
| E | 优 | 50% |
1
在这个树1或者树2里,百分比数值叫权值。
类似结点D,E等叫带权结点(Weight)。
类似树里的边(60->70->80->90->E)叫带权路径。
WPL:整棵树的带权路径长度。
树①:$10×1+ 15×2+30×3+40×4+5×4=310$。
树②:$10×3+15×3+30×2+40×2+5×2=225 $。
Haffman构造方法
- 将所有带权结点,按照从权值大小进行从小到大的排序
- 在排好序的序列中,拿出前两个最小的,由二者构成一个新结点
- 将构成的新结点,放到序列中,重新排序
- 重复步骤2 步骤3,直到把结点放完为止(剩一个结点)
ps:按照左小右大的规则放置结点,也可以左大右小,只要定下来,剩下结点放置必须遵守
2
设最终的树为③
树③的WPL:$10×4+15×3+30×2=40×1+5×4=205$
Haffman编码优化
若要发送一串形如ABCCCDFEE....的编码,用Haffman编码优化最优
根据上一知识点,构成树③每个分枝左0右1,如上图,
即得A:1101,B:111,C:10,D:0,E:1100,此时没有一个编码是其他编码的前缀,不会产生歧义。
