哈夫曼树

基本概念

1.结点的权

每个结点带有的具有某种现实意义的数值(比如代表重要性等)

2.结点的带权路径长度

从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

3.树的带权路径长度

树中所有叶结点的带权路径长度之和（WPL, Weighted Path Length）

$WPL=\sum_{i=1}^{n}w_il_i$

✨4.哈夫曼树

在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

构造哈夫曼树

给定n个权值分别为 $w_1,w_2,…,w_n$ 的结点，其构造过程描述如下：

① 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F

② 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。

③ 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。

④ 重复步骤②和③，直至F中只剩下一棵树为止。

假设给定结点在经过步骤①之后如下

则其②③④步骤为：

$WPL_{min}=1*7+2*3+3*2+4*1+4*2=31$

或者

$WPL_{min}=1*7+3*(1+2+2+3)=31$

👇👇👇👇👇👇

哈夫曼树特点：

① 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。 ② 哈夫曼树的结点总数为2n-1。 ③ 哈夫曼树中不存在度为1的结点。 ④ 哈夫曼树并不唯一，但WPL必然相同且为最优。

哈夫曼编码

固定长度编码

如ASCII码

可变长度编码

前缀编码

没有一个编码是另一个编码的前缀

哈夫曼编码

由哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树。

✨ 应用

可用于数据压缩

如图，为英文字母使用频率表，若不进行压缩，第 i 个字母频率用$l_i表示$，路径长至少为5($2^4<26<2^5$)，则

$WPL=5×\sum_{i=1}^{n}l_i$=500

若通过构造哈夫曼树进行哈夫曼编码

则$WPL_{min}=$

$v=\frac{WPL_{min}}{WPL}$