哈夫曼树原理及构造方法

﹏ヽ暗。殇╰゛Y 2022-12-03 09:14 28阅读 0赞

原文链接：[https://blog.csdn.net/qq\_29519041/article/details/81428934][https_blog.csdn.net_qq_29519041_article_details_81428934]

**哈夫曼树的建立**  
（1）初始化：根据给定的n个权值，构造n棵二叉树的森林集合F=\{T1,T2,…,Tn\}，其中每棵二叉树只有一个权值为Wi的根节点，左右子树均为空。  
（2）找最小的树并构造新的树：在森林集合F中选取两颗根的权值最小的树作为左右子树构造一棵新的二叉树，新二叉树的根结点为新增加的结点，其权值为左右子树根的权值之和。  
（3）删除与插入：在森林集合中删除已选取的两棵根的权值最小的树，同时将新构造的二叉树加入到森林集合F中。  
（4）重复（2）和（3）步骤：直到森林集合只含有一棵树为止，这棵树即为哈夫曼树。

# **哈夫曼树（最优二叉树）** #

**百度百科：**[https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin][https_baike.baidu.com_item_E5_93_88_E5_A4_AB_E6_9B_BC_E6_A0_91_2305769_fr_aladdin]

## **一. 目的：** ##

**找出存放一串字符所需的最少的二进制编码**

### **二. 构造方法：** ###

**首先统计出每种字符出现的频率！（也可以是概率）//权值**

**------------------------------------------------------------------------------------------------**

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

第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在**频率表**中删除**此次找到的两个数，并加入此次最小两个数的频率和。**

**F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和 8给频率表**

![70][]

** 重复第一步：**

**-------------------------------------------------------------------------------------------------**

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

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

![70 1][]

**---------------------------------------------------------------------------------------------------**

重复第一步：

**---------------------------------------------------------------------------------------------------**

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

**如图**

![70 2][]

**-----------------------------------------------------------------------------------------------------**

重复第一步

**-----------------------------------------------------------------------------------------------------**

**频率表 A：60    B: 45   D: 69  FGCE: 35**

![70 3][]

**-----------------------------------------------------------------------------------------------------**

重复第一步

**-----------------------------------------------------------------------------------------------------**

**频率表 A：60   D: 69  FGCEB: 80**

![70 4][]

**-----------------------------------------------------------------------------------------------------**

重复第一步

**-----------------------------------------------------------------------------------------------------**

**频率表 AD：129  FGCEB: 80**

![70 5][]

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

![70 6][]

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

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

那么当我想传送 ABC时，编码为 10 01 0011

**思考：**

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

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

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

比如 不能出现 读码 读到 01  还有长编码的 字母为011，如果短编码为一个长编码的左起子串，这就是冲突，意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母，

但哈夫曼树（最优二叉树）在构造的时候就避免了这个问题。为什么能避免呢，因为哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况。

**提问：**

### **1.为什么要保证长编码不与短编码冲突？** ###

**冲突情况**：如果我们已经确定D，E，F，G 用 01 ，010 ，10，001的2进制编码来传输了。那么想传送FED时，我需要传送     1001001，接收方可以把它解析为FDG（10 01 001），当然也能解析为FED（10 010 01），他两编码一样的，这就是编码冲突，（**这里编码冲突的原因，也是因为编码时，D的编码是E的编码的左起子串了**）显然这是不行的，就像我说压脉带，你如果是日本人会理解为 （你懂得），这就是发出同一种语，得出不同的意的情况。所以不能让一个字母的二进制代表数，为另一个字母的二进制代表数的子串。但为什么**实际情况只要求编码时，一个编码不是另一编码的****左起子串**呢而不是**绝对意义上的非子串**呢，因为计算机从数字串的左边开始读，如果从右边读，那么可以要求是**非右起**（无奈）。你又可以问了为什么编码要求是**非左起**或**非右起**不直接规定不能是子串呢（也行，不过=>），比如说原文中B就是C，F，G的子串，那这不就不符合规则了么。这里是为了哈夫曼的根本目的，优化编码位占用问题，如果完全不能有任何子串那么编码将会非常庞大。但这里计算机是一位一位的·读取编码的，**只需要保证计算机在读取中不会误判就行**。并且编码占用最少。

**code：0110101001110**

左起子串：011

右起子串：110

绝对非子串：**1110111  此串在code中完全找不到**

### 2.那么哈夫曼树怎么避免左起子串问题呢？ ###

因为哈夫曼是**从叶子节点开始构造，构造到根节点**的，而且构造时，都是**计算两个权值的节点的和**再**与其他叶子节点**再生成一个**父节点**来组成一个**新的树**。并且**不允许任何带有权值的节点作为他们的父节点**。这也保证了**所有带有权值的节点都被构造为了叶子节点**。然后最后编码的时候是**从根节点开始走到叶子节点而得出的编码**。在有权值的节点又不会出现在任何一条路的路途中的情况，只会出现在终点的情况下，因此不会出现01代表一个字母011又代表一个字母。

又如原文ABC编码为10010011的情况，当计算机读到10时，由于有左起子串不冲突的原则。那么计算机完全可以保证当前的10就是A字母，然后再往下读010011的部分，然后当读到01时，也完全能确定B，C同理，而不用说因为会出现冲突的编码而接着继续读取之后的编码来确定前面的编码。这样对信息的判断和效率是相当的不利的，也不是说不可以。即使你ABCD,分别用01,011,0111,01111来代替也行，传输后也能精确识别，但是数据量极大呢，想代替整个中文编码呢，那0后面得多少个1才能代表完。因此哈夫曼就是为了获得最少编码量代替最多字符串，并且不冲突，系统不会误判而产生的。

### 3.这里要提一下同权不同构 ###

已经有朋友问起这个问题了。这里要说一下**哈夫曼树的构造并不是唯一的**。

考虑如下情况：

有权值分别为 5,29,7,8,14,23,3,11的情况，可以如下图一样构造。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70][]

带权路径长度：

(5+3+7+8)\*4+

(11+14)\*3+

(23+29)\*2

=271

也可以如下图构造：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70 1][]

带权路径长度：

（3+5)\*5+

7\*4+

(8+11+14)\*3+

(23+29)\*2

=271

这两种不同的方式构造出来的哈夫曼树，得出的带权路径长度相等，那么选哪颗树都可以，这就叫**同权不同构**。

此问题由博主 [https://me.csdn.net/weixin\_43690959 ][https_me.csdn.net_weixin_43690959]昵称：叫我Tim就好了～ 提出，在这里对他表示感谢。

**看懂的朋友留个赞，没看懂的留言我给你单独讲 \_(:з」∠)\_**

[https_blog.csdn.net_qq_29519041_article_details_81428934]: https://blog.csdn.net/qq_29519041/article/details/81428934
[https_baike.baidu.com_item_E5_93_88_E5_A4_AB_E6_9B_BC_E6_A0_91_2305769_fr_aladdin]: https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin
[70]: /images/20221123/32a7d570e80447ec9fa4a2ebf51ec1b3.png
[70 1]: /images/20221123/c1bdc39f3dde4f61a1ee33b062723f38.png
[70 2]: /images/20221123/d32939f028a041bda682b19c6e694c7e.png
[70 3]: /images/20221123/37bc656dd6aa4024b2c70f18445cacb6.png
[70 4]: /images/20221123/a721e921145748c38be4772ad928e0d9.png
[70 5]: /images/20221123/7e0e4c24aa074e37bdf9ddb2ba31e1c3.png
[70 6]: /images/20221123/40cf4d1a28d343b2a6278a77a9c4dcd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70]: /images/20221123/551537d782f943aab1a435d28f057006.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NTE5MDQx_size_16_color_FFFFFF_t_70 1]: /images/20221123/aff0e830782f4fce83c71f20dfc3f9ea.png
[https_me.csdn.net_weixin_43690959]: https://me.csdn.net/weixin_43690959