有数据WG={3,2,4,5,1}, (1)画出所构建的Huffman 树; (2)所建Huffman 树的树高是多少? (3)求所建Huffman 树的带权路径长度WPL。
时间: 2023-06-09 17:07:44 浏览: 136
好的,我明白了。让我来回答你的问题。
(1) 我根据数据WG={3, 2, 4, 5, 1} 帮你画出所构建的Huffman树如下:
```
+-----+
| 15 |
+-----+
/ \
/ \
+---+ +---+
| 7| | 8|
+---+ +---+
/ \ / \
+--+ | | | |
| 3| | | | |
+--+ | | | |
| 4| | |
+--+ +--+
/ \ / \
/ \ / \
2 1 5 4
```
(2) 所建Huffman树的树高为4。
(3) 求所建Huffman树的带权路径长度WPL:
带权路径长度WPL是指所有叶子结点的权值乘上其到根节点的距离之和。因此我们可以通过遍历Huffman树,计算每个叶子结点的路径长度并累加起来,最终得到WPL。
根据构建的Huffman树,可以得到每个叶子结点的权值和路径长度如下:
```
叶子结点 权值 路径长度
3 3 3
2 2 3
4 4 2
5 5 2
1 1 3
```
因此,WPL为:
WPL = 3*3 + 2*3 + 4*2 + 5*2 + 1*3 = 27
所以,所建Huffman树的带权路径长度WPL为27。
希望我的回答对你有所帮助!
阅读全文