数据结构考研笔记（十六） ——哈夫曼树、编码应用

快来打我* 2022-12-16 06:15 85阅读 0赞

### 这里写目录标题 ###

*  带权路径长度
 *  哈夫曼
 *   *  构造
     *  性质
     *  应用
     *  哈夫曼树构造前缀编码

# 带权路径长度 #

路径长度 ： 路径上所经历边的个数。  
结点的权 ： 结点被赋予的数值。  
![在这里插入图片描述][20201019093317861.png_pic_center]  
![在这里插入图片描述][20201019093405422.png_pic_center]  
![在这里插入图片描述][20201019093433206.png_pic_center]

# 哈夫曼 #

**哈实曼树**也称最优二叉树，含有n个带权叶子结点带权路径长度最小的二叉树

## 构造 ##

哈夫曼树的构造算法
      1)将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F;
      2)生成一个新结点，并从F中找出根结点权值最小的两棵树作为它的左右子树，且新结点的权值为两棵子树根结点的权值之和;
      3)从F中删除这两个树，并将新生成的树加入到F中;
      4)重复2,3步骤，直到F中只有一棵树为止。

如下图，生成一个新的结点，然后在F中找到最小的两个权值的树，作为新结点的左右子树。然后新结点的权值就为左右子树之和  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]

## 性质 ##

哈夫曼树的性质
       1）每个初始结点都会成为叶节点，双支结点都为新生成的结点
       2）权值越大离根结点越近，反之权值越小离根结点越远
       3）哈夫曼树中没有结点的度为1
       4）n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1。

## 应用 ##

编码问题  
**编码**对于一个字符串序列，用二进制来表示字符。  
固定长度编码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]  
**前缀编码**没有一个编码是另一个编码的前缀  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]

## 哈夫曼树构造前缀编码 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 4]  
哈夫曼树并不唯一，所以每个字符对应的哈夫曼编码也不唯一,但带权路径长度相同且最优

[20201019093317861.png_pic_center]: /images/20221123/99e854a7ee594c258ad4e706951cfec4.png
[20201019093405422.png_pic_center]: /images/20221123/3dbb28f0420249a38f19ae8cd79f7179.png
[20201019093433206.png_pic_center]: /images/20221123/1904ba5a0c6b417983fddfdafeb5ad9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/51dca3179c48498fa7a815c024d60547.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/c19dfe99031b4ccdbe664d50e7267043.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/52da75431fff492d9eecf9ef5d547e78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/12672cd047754f2c91cca310950d14ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/48f962f243bc46a6a02702ad461fca7d.png