哈夫曼树和哈夫曼编码

带权路径长度

结点的权：具有现实意义的数值（比如，频率、次数、重要性等等）
结点的带权路径长度：从树的根到该节点的路径长度（经过的边）与该节点上的权值所做的乘积。
树的带权路径长度：树中所有叶子节点的带权路径长度的积。记为WPL，Weighted Path Length。

哈夫曼树的定义

哈夫曼树：WPL最小的二叉树称为哈夫曼树，也称为最优二叉树。

哈夫曼树的构造

给定 n n n个权值为 w 1 , w 2 , w 3 , . . . , w n w_1, w_2, w_3, ... , w_n w1​,w2​,w3​,...,wn​的结点，构造哈夫曼树的算法如下：

1. 排序：所有结点按权值升序排序
2. 组合：取权值最小两个的结点组合成一个新二叉树
3. 新点：新的二叉树的根的权值为两个左右子树的权值之和，新权值取代两个子树的权值
4. 重复1、2、3，直至结束

a	c	e	b	d
1	2	2	3	7

e	ac	b	d
2	3	3	7

b	eac	d
3	5	7

如此重复，直至构造哈夫曼树：

另外一种构造结果

哈夫曼树的性质

1. 每个初始结点最终都成为叶子结点
2. 权值越小的结点到根节点的带权路径长度越大
3. 哈夫曼树的结点总数为 2 n − 1 2n-1 2n−1
4. 哈夫曼树不唯一，但WPL必然相同且为最优

哈夫曼编码

固定长度编码：每个字符用相等长度的二进制位表示

可变长度编码 variable-length code：允许对不同字符用不等长的二进制位表示。
前缀编码 prefix code：在可变长度编码中，若没有一个编码是另一个编码的前缀，则称这样的可变长度编码为前缀编码。

可能“无前缀码”是一个更好的名字，但在相关文献中，“前缀码”是一致认可的标准术语。——来自《算法导论》

哈夫曼编码：字符集中的每个字符作为一个叶子结点，字符的出现频率作为权值，由此构造出的哈夫曼树所得到编码。

参考

王道考研-数据结构与算法5.5_3哈夫曼树