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 |