某电文中由A、H、C、T、F字符构成,对应字符出现的频率为3、8、2、5、3, (1)请做出构建哈夫曼树的过程;(4分) (2)计算该哈夫曼树的WPL。(2分)
时间: 2023-08-28 21:03:43 浏览: 26
好的,我会先回答你的第一个问题。以下是构建哈夫曼树的过程:
1. 将所有字符按照出现频率从小到大排序,得到:C(2)、F(3)、A(3)、T(5)、H(8);
2. 取出最小的两个字符C(2)和F(3),合并成一个新节点CF(5);
3. 将新节点CF(5)插入到剩余节点中,得到:CF(5)、A(3)、T(5)、H(8);
4. 取出最小的两个节点CF(5)和A(3),合并成一个新节点CAF(8);
5. 将新节点CAF(8)插入到剩余节点中,得到:CAF(8)、T(5)、H(8);
6. 取出最小的两个节点T(5)和CAF(8),合并成一个新节点TCAF(13);
7. 将新节点TCAF(13)插入到剩余节点中,得到:H(8)、TCAF(13);
8. 取出最小的两个节点H(8)和TCAF(13),合并成一个新节点HTCAF(21);
9. 构建完成,得到哈夫曼树如下图所示:
```
HTCAF(21)
/ \
H(8) TCAF(13)
/ \
CAF(8) T(5)
/ \
C(2) F(3)
```
接下来是第二个问题,计算该哈夫曼树的WPL。
WPL为所有叶子节点的权值乘以其到根节点的路径长度之和,所以我们只需要计算出每个叶子节点的权值和路径长度,然后相乘求和即可。
C的权值为2,路径长度为3,所以C的贡献为2*3=6;
F的权值为3,路径长度为3,所以F的贡献为3*3=9;
A的权值为3,路径长度为2,所以A的贡献为3*2=6;
T的权值为5,路径长度为2,所以T的贡献为5*2=10;
H的权值为8,路径长度为1,所以H的贡献为8*1=8。
将所有叶子节点的贡献相加,得到WPL=6+9+6+10+8=39。
所以,该哈夫曼树的WPL为39。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)