哈夫曼树

淡淡的烟草味﹌ 2021-12-16 08:23 247阅读 0赞

## 定义 ##

我们希望建立这样一株二叉树，其叶结点为一组给定的带权结点，称这个树的权重为每个叶子结点到根结点的距离与其权值的乘积的累和，即：

![20190705155648796.png][]

其中x.w表示叶结点的权重，而x.d为叶结点的深度。哈夫曼树是所有满足上面条件的二叉树中权重最小的。

**哈夫曼树的构造算法（心里默念：把每个叶节点按照权值的大小，先把最小的两个叶节点构成一个父节点是他们之和的小二叉树，在以父节点为新的“叶节点” 参与后续大小的比较；继续这样构成新的二叉树。）**

例如：频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3

*  第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在频率表中删除此次找到的两个数，并加入此次最小两个数的频率和。F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和 8给频率表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70][]

重复第一步：

频率表 A：60,    B:45,   C:13   D:69   E:14   FG:8

*  最小的是 FG：8与C：13，因此如图，并返回FGC的和：21给频率表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1][]

*  **频率表 A：60    B: 45   D: 69   E: 14   FGC: 21**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2][]

*  最后:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 3][]

*  **添加 0 和 1，规则左0 右1**

![70][]

频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3

每个 字符 的 二进制编码 为（从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码）

*  A：10
 *  B：01
 *  C：0011
 *  D：11
 *  E：000
 *  F：00101
 *  G：00100

**哈夫曼编码：那么当我想传送 ABC时，编码为 10 01 0011**

1、大家观察 出现得越多的字母，他的编码越短 ，出现频率越少的字母，他的编码越长。

在信息传输过程中，如果这个字母越多，那么我们希望他越瘦小（编码短）这样占用的编码越少，其实编码长的字母也是让频率比它多的字母把编码短的位子都占用后，他才去占用当前最短的编码。至此让总的编码长度最短。

2、要保证长编码的不与短编码的字母冲突：

比如 不能出现 读码 读到 01  还有长编码的 字母为011，如果短编码为一个长编码的左起子串，这就是冲突，意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母，但哈夫曼树（最优二叉树）在构造的时候就避免了这个问题。为什么能避免呢，因为哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况。

转载：[https://blog.csdn.net/qq\_29519041/article/details/81428934][https_blog.csdn.net_qq_29519041_article_details_81428934]

[20190705155648796.png]: /images/20211214/0941a8acaa234922a40a2b14d4420491.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70]: /images/20211214/4c55f6e16ed845cb9a5802ac42dcea69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1]: /images/20211214/dd2abba5f2064df0b7938ce93fe65ae1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2]: /images/20211214/a17ad70acfdc4431b51981af34c8cb35.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 3]: /images/20211214/e8eac265f43c403e8a08c87dacc2368d.png
[70]: /images/20211214/cc5dadb551cd43b48e0655e16499cdf3.png
[https_blog.csdn.net_qq_29519041_article_details_81428934]: https://blog.csdn.net/qq_29519041/article/details/81428934