已知权值集合为{5,7,2,3,6,9},要求给出哈夫曼树,并计算带权路径长度WPL。
时间: 2023-08-19 17:17:06 浏览: 634
霍夫曼树带权路径长度求值.cpp
好的,根据哈夫曼树的构建规则,我们先将权值从小到大排序得到{2,3,5,6,7,9},然后构建哈夫曼树如下所示:
```
32
/ \
12 20
/ \ / \
5 7 6 9
/ \
2 3
```
其中,每个叶子结点代表一个权值,叶子结点的权值即为该权值出现的次数,每个非叶子结点代表两个权值的合并,其权值为左右子树权值之和。
带权路径长度WPL定义为所有叶子结点的权值乘上其到根结点的路径长度之和,因此,WPL的计算公式为:
```
WPL = 5*2 + 7*2 + 6*2 + 9*2 + 3*3 + 2*3 = 74
```
因此,给定的权值集合的哈夫曼树的带权路径长度为74。
阅读全文