1.概念
- 结点的权：某种特定含义的数值
结点的带权路径长度=跟到结点路径长度 * 结点的权值树的带权路径长度(WPL)=树中所有叶子结点的带权路径之和- 哈夫曼树(最优二叉树)：在含有给定n个带权叶结点的二叉树中，WPL最小的二叉树。
2.哈夫曼树的构造
给定n个权值分别为 w1, w2, ... wn的结点，构造算法如下：
- 将这n个结点分别作为n课仅含结点的二叉树，构成森林F；
- 构造一个新结点，从F中选取两颗根结点权值最小的树作为新结点的左、右子树，并且将新节点的权值置为左、右子树上根结点的权值之和；
- 从F中删除刚才选出的两颗树，同时将新得到的树加入F中；
- 重复步骤2和3，直至F中只剩下一棵树为止。
哈夫曼树具有如下特点：
- 每个初始结点最终都称为叶结点，且权值越小的结点到根结点的路径长度越大；
- 构造过程中，共新建 n-1个结点，因此哈夫曼树的结点总数为 2n-1；
- 不存在度为1的结点；
- 哈夫曼树不唯一，但WPL必然都是最小值
3.哈夫曼编码
将字符频次作为字符结点的权值，构造哈夫曼树，即可得哈夫曼编码，可用于数据压缩；
前缀编码：没有一个编码是另一个编码的前缀；
固定长度编码：每个字符用相等长度的二进制位表示；
可变长度编码：允许不同字符用不等长的二进制位表示；
示例：
各字符编码为：
| 字符 | a | b | c | d | e | f |
| 编码 | 0 | 101 | 100 | 111 | 1101 | 1100 |