画出Huffman树,写出各字符的Huffman编码,并计算WPL值。 字符集 {A,B,C,D,E,F,G,H} 权值集 {23,5,17,4,9,31,29,18}
时间: 2023-10-01 11:05:56 浏览: 77
首先,我们需要根据权值集构建出Huffman树。具体过程如下:
1. 将权值集中所有元素作为叶节点,构建出一个森林。
2. 在森林中选择两个权值最小的树作为左右子树,将它们合并成一棵新的树,并将它们的权值之和作为新的节点权值。
3. 将新的树插入森林中,并删除原来的两棵树。
4. 重复2和3的步骤,直到森林中只剩下一棵树,即为Huffman树。
下面是根据给定的权值集构建出的Huffman树:
```
136
/ \
56 80
/ \ / \
23 33 29 51
/ \
18 11
```
接下来,我们可以根据Huffman树给出每个字符的Huffman编码。从根节点开始,如果向左子树走,则编码为0,如果向右子树走,则编码为1。最终得到的编码如下:
```
A: 100
B: 11011
C: 101
D: 11010
E: 1110
F: 0
G: 01
H: 1111
```
最后,我们可以根据每个字符的权值和它对应的Huffman编码,计算出WPL值。WPL值是每个字符的权值乘以它的Huffman编码长度之和的总和,即:
```
WPL = 23*3 + 5*5 + 17*3 + 4*5 + 9*4 + 31*1 + 29*2 + 18*4 = 317
```
因此,给定字符集的Huffman编码为:
```
A: 100
B: 11011
C: 101
D: 11010
E: 1110
F: 0
G: 01
H: 1111
WPL = 317
```
相关推荐
![cpp](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)