【数据结构】哈夫曼树

女爷i 2023-09-23 20:43 99阅读 0赞

#### 【数据结构】哈夫曼树 ####

*  一、基本概念
 *  二、 哈夫曼树的构造
 *  三、 哈夫曼树的性质
 *  四、 哈夫曼编码

## 一、基本概念 ##

![在这里插入图片描述][196e8247f72e4b4996e2577317b05596.png_pic_center]

*  **路径**：从一个结点到另一个结点之间的分支序列
 *  **路径长度**：从一个结点到另一个结点所经过的分支数量
 *  **结点的权**：有某种现实含义的数值（如：表示结点的重要性等）
 *  **结点的带权路径长度**：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
    
     *  例如叶子结点中权为3的带权路径长度就是 3\*3 = 9  
          
        
 *  **树的带权路径长度**：树中所有叶子结点的带权路径长度之和（WPL）  
    ![在这里插入图片描述][d398914974164bdb954dccc2d23a3c33.png_pic_center]
    
     *  例如  
        ![在这里插入图片描述][21311dc01dec403aa0fd16c5e8b2bd9d.png_pic_center]  
        这颗树的带权路径长度为：  
        **2*1 + 2*3 + 2*4 +2*5 = 26**

![在这里插入图片描述][3a97b186ac4542cd9c15e003e108e7fc.png_pic_center]  
这颗树的带权路径长度为：  
**1*3 + 3*3 + 2*4 + 5*1 = 25**

![在这里插入图片描述][73c9b4c8bccf4f7a9ad3817badd40e1b.png_pic_center]  
这颗树的带权路径长度为：  
**1*5 + 3*3 + 3*1 + 2*4 = 25**

![在这里插入图片描述][9282a9cdee0749d9b813005c8662fe59.png_pic_center]  
这颗树的带权路径长度为：  
**1*1 + 2*3 + 3 *5 + 3*4 = 34**

*  在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树  
    ![在这里插入图片描述][bf8b5d98a8e34295808edaaf0a56d88f.png_pic_center]

## 二、 哈夫曼树的构造 ##

![在这里插入图片描述][93246909734d4a11a69b376a3081a16d.png_pic_center]  
另一种构造方法：  
![在这里插入图片描述][93622c53be4240199f2d270c01acf442.png_pic_center]

## 三、 哈夫曼树的性质 ##

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

## 四、 哈夫曼编码 ##

*  规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符编码。这样的编码称为哈夫曼编码。
 *  哈夫曼编码的特点：权值越大的字符编码越短，反之越长  
    ![在这里插入图片描述][d32ff2a2c205484588299a6b10981f40.png_pic_center]  
    ![在这里插入图片描述][f794a2ea1ea349a2a9f5482dbd1d5256.png_pic_center]

[196e8247f72e4b4996e2577317b05596.png_pic_center]: https://img-blog.csdnimg.cn/196e8247f72e4b4996e2577317b05596.png#pic_center
[d398914974164bdb954dccc2d23a3c33.png_pic_center]: https://img-blog.csdnimg.cn/d398914974164bdb954dccc2d23a3c33.png#pic_center
[21311dc01dec403aa0fd16c5e8b2bd9d.png_pic_center]: https://img-blog.csdnimg.cn/21311dc01dec403aa0fd16c5e8b2bd9d.png#pic_center
[3a97b186ac4542cd9c15e003e108e7fc.png_pic_center]: https://img-blog.csdnimg.cn/3a97b186ac4542cd9c15e003e108e7fc.png#pic_center
[73c9b4c8bccf4f7a9ad3817badd40e1b.png_pic_center]: https://img-blog.csdnimg.cn/73c9b4c8bccf4f7a9ad3817badd40e1b.png#pic_center
[9282a9cdee0749d9b813005c8662fe59.png_pic_center]: https://img-blog.csdnimg.cn/9282a9cdee0749d9b813005c8662fe59.png#pic_center
[bf8b5d98a8e34295808edaaf0a56d88f.png_pic_center]: https://img-blog.csdnimg.cn/bf8b5d98a8e34295808edaaf0a56d88f.png#pic_center
[93246909734d4a11a69b376a3081a16d.png_pic_center]: https://img-blog.csdnimg.cn/93246909734d4a11a69b376a3081a16d.png#pic_center
[93622c53be4240199f2d270c01acf442.png_pic_center]: https://img-blog.csdnimg.cn/93622c53be4240199f2d270c01acf442.png#pic_center
[d32ff2a2c205484588299a6b10981f40.png_pic_center]: https://img-blog.csdnimg.cn/d32ff2a2c205484588299a6b10981f40.png#pic_center
[f794a2ea1ea349a2a9f5482dbd1d5256.png_pic_center]: https://img-blog.csdnimg.cn/f794a2ea1ea349a2a9f5482dbd1d5256.png#pic_center