由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( )
时间: 2023-11-24 07:07:25 浏览: 850
霍夫曼树带权路径长度求值.cpp
首先需要构建哈夫曼树,构建过程如下:
1. 将权值从小到大排序:2,5,6,8,11
2. 取出最小的两个权值,合并为一个节点,权值为它们的和:2+5=7
3. 将新节点插入到排序后的位置:6,7,8,11
4. 重复步骤2-3,直到只剩下一个节点,即为根节点
构建出来的哈夫曼树如下所示:
```
32
/ \
14 18
/ \ / \
6 8 5 11
```
根据带权路径长度的公式,带权路径长度 = 所有叶子节点的权值 × 树高,因此带权路径长度为:
2 × 3 + 5 × 2 + 6 × 2 + 8 × 2 + 11 × 2 = 58
所以,带权路径长度为 58。
阅读全文