二叉树之_哈夫曼树_哈弗曼编码

柔光的暖阳◎ 2022-12-13 14:13 197阅读 0赞

### 哈夫曼树又称最优二叉树 ###

给定N个权值作为N个[叶子结点][Link 1]，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

### 名词解释 ###

**路径**：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。  
**路径长度**：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。  
**结点的权：**给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。  
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 \* 5 = 10 。  
  
**树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” **。例如图 1 中所示的这颗树的带权路径长度为：

> WPL = 7 \* 1 + 5 \* 2 + 2 \* 3 + 4 \* 3

![ce5390ad453917667263bb069ce25db5.png][]

### 哈夫曼树解析: ###

![20160825101010931][]

三棵二叉树的带权路径长度为：

（a）WPL=9x2+4x2+5x2+2x2=18+8+10+4=40

（b）WPL=9x1+5x2+4x3+2x3=9+10+12+6=37

（c）WPL=4x1+2x2+5x3+9x3=4+4+15+27=50

**其中（b）所示的二叉树的WPL最小，此树是哈夫曼树**。由上图可知：由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树 不一定是最优二叉树。**权值越大的结点离根结点越近**的二叉树才是最优二叉树。

## 怎么构建哈夫曼树? ##

对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：

1.  在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
2.  在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
3.  重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

![fe5aabed79ffdca6989e0cb94c5cac18.png][]

### 哈夫曼编码 ###

简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：

![7ed95609341a70e8c05a62fcf008bdf4.png][]

虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成\{5,4,3,3\}，再根据第二步，取最小的两个权值构成新树，如图：  
![77a5fa7da451a9f6daa90085d8790ae3.png][]

再依次建立哈夫曼树，如下图：

![7a2c925729246c5ee5bcdf4e82f160db.png][]

其中各个权值替换对应的字符即为下图：

![4339d50bc15cfb1bcc59eb15859abec8.png][]

所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010  
霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。

如果考虑到进一步节省存储空间，就应该将出现概率大（占比多）的字符用尽量少的0-1进行编码，也就是更靠近根（节点少），这也就是最优二叉树-哈夫曼树。  
为什么？-----> **权值大的在上层，权值小的在下层。满足出现频率高的码长短。**

**哈夫曼编码的带权路径权值：叶子节点的值 \* 叶子节点的高度（根节点为0）**

**上图的带权路径长度为：（3+4+5）\*2+（1+2）\*3=33**

哈夫曼编码相关转载自 :[https://blog.csdn.net/qq\_36653505/article/details/81701181][https_blog.csdn.net_qq_36653505_article_details_81701181]

[Link 1]: https://baike.baidu.com/item/%E5%8F%B6%E5%AD%90%E7%BB%93%E7%82%B9/3620239
[ce5390ad453917667263bb069ce25db5.png]: /images/20221123/4a487c705f17493899a72a0846b856aa.png
[20160825101010931]: /images/20221123/d50e3432d8f54e46bd33ab0f297b91e1.png
[fe5aabed79ffdca6989e0cb94c5cac18.png]: /images/20221123/4ac958b572be463d934bdb9755efd12e.png
[7ed95609341a70e8c05a62fcf008bdf4.png]: /images/20221123/f04ddf44d8f24182987c33bd6a577d90.png
[77a5fa7da451a9f6daa90085d8790ae3.png]: /images/20221123/34b08ed02cc944c6b70ae27cfb923f76.png
[7a2c925729246c5ee5bcdf4e82f160db.png]: /images/20221123/c4d723be4ae84f24b621b333be9e7ad6.png
[4339d50bc15cfb1bcc59eb15859abec8.png]: /images/20221123/886dd8efe05a42e7b62b34d10e522fed.png
[https_blog.csdn.net_qq_36653505_article_details_81701181]: https://blog.csdn.net/qq_36653505/article/details/81701181