给定5个数分别为5,10,10,18,20,求计算哈夫曼值详细过程
时间: 2023-12-15 18:03:29 浏览: 26
首先,哈夫曼编码是用于数据压缩的一种编码方式,通过将频率较高的字符用较短的编码表示,来减小数据的存储空间。在计算哈夫曼值时,需要按照以下步骤进行:
1. 将给定的数按照从小到大的顺序排序,得到:5,10,10,18,20。
2. 选出两个权值最小的数,将它们合并为一个节点,并将它们的权值相加。这里选出的是5和10,它们合并后的权值为15。将这个新的节点插入到列表中,得到:15,10,18,20。
3. 重复上一步骤,选出两个权值最小的数,将它们合并为一个节点,并将它们的权值相加。这里选出的是10和15,它们合并后的权值为25。将这个新的节点插入到列表中,得到:18,20,25。
4. 重复上一步骤,选出两个权值最小的数,将它们合并为一个节点,并将它们的权值相加。这里选出的是18和20,它们合并后的权值为38。将这个新的节点插入到列表中,得到:25,38。
5. 最后,将列表中剩下的两个节点合并为一个节点,并将它们的权值相加。这里选出的是25和38,它们合并后的权值为63。
6. 计算哈夫曼值,即将树上每个节点的权值乘以它的深度,然后将所有结果相加。对于这个例子,树的结构如下:
63
/ \
25 38
/ \
15 10
/ \
5 10
从根节点开始,深度为0,其权值为63,因此贡献值为 0*63=0。接下来,深度为1的节点有两个,分别是25和38,它们的权值分别为25和38,因此贡献值为 1*25 + 1*38 = 63。深度为2的节点有三个,分别是15、10和10,它们的权值分别为15、10和10,因此贡献值为 2*15 + 2*10 + 2*10 = 70。最终的哈夫曼值为0+63+70=133。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)