C语言数据结构——哈夫曼树

迷南。 2022-12-24 11:59 137阅读 0赞

**哈夫曼树**  
又称最优二叉树它是树的带权路径长度 值最小的一棵二叉树，可用于构造最优编码，在信息传输、数据压缩等方面有着广泛的应用。  
哈夫曼树的相关概念  
**路径：**  
树中一个结点到另一个结点之间的分支序列  
**路径长度：**  
路径上分支的条数。  
**结点的权：**  
给结点赋予的数值。  
**带权路径长度：**  
结点的权值与该结点到树根间路径长度的乘积。  
树的带权路径长度：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70]  
例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 2]  
从上面这三棵树中可以看出，他们有着共同的5个叶子，权值也都相同，但其WPL却不同，原因就是三棵树的结构不同。所以：对于权值相同的n个叶子所构造的二叉树结构不同，WPL值也不同。这就引出了最优**二叉树的概念：**  
在叶子个数n以及各叶子权值Wi确定的条件下，树的带权路径长度WOL值最小的二叉树称为最优二叉树。  
从上面三个数观察可以看出：  
哈夫曼树最优二叉树的特点是：**权值越大，离根越近！WPL就越小**，因此最优二叉树又称**哈夫曼树**。

哈夫曼树的建立：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 3]  
例子：  
第一步：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 4]  
第二步：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 5]  
第三步：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 6]  
第四步：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 7]  
重复执行以上步骤：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 9]  
1.对于给定的N个叶子结点，构造哈夫曼树，其最终总的结点树一定是：2N-1。  
2.可选用静态链表作为存储结构。即用含2N-1个元素的数组来存储哈夫曼树，结点间的父子关系用下标来指示。  
3.在使用哈夫曼树进行编码和译码时，既要用结点的双亲信息，又要用结点的孩子信息，所以采用静态三叉链表存储哈夫曼树。  
静态链表存储：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 11]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70]: /images/20221120/cc55ac33de604961afb33e3ee2dc77e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020112810441978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201128104508804.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020112810523987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201128105402367.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201128105432292.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201128105459540.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201128105525532.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201128105619111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20201128105701372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20201128110440906.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20201128110451798.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70