若以{4,5,6,7,8}作为权值构造哈夫曼树,则该树的带权路径长度为( )
时间: 2023-08-06 17:05:46 浏览: 297
霍夫曼树带权路径长度求值.cpp
哈夫曼树的构造过程中,每次选择权值最小的两个节点进行合并,直到最终合并成一棵树。因此,构造出来的哈夫曼树是一棵带权路径长度最小的树。
对于给定的权值{4,5,6,7,8},构造出来的哈夫曼树如下图所示:
```
30
/ \
13 17
/ \ / \
4 5 6 11
/ \
7 8
```
其中,叶节点的权值分别为4、5、6、7、8,非叶节点的权值为其左右子树的权值之和。根据定义,带权路径长度等于每个叶节点的权值乘以其到根节点的路径长度之和,再将所有叶节点的带权路径长度相加。
因此,该哈夫曼树的带权路径长度为:
```
4*3 + 5*3 + 6*2 + 7*2 + 8*2 = 12 + 15 + 12 + 14 + 16 = 69
```
因此,答案为69。
阅读全文