利用2 3 5 7 8 11构造哈夫曼树 并算出WPL
时间: 2024-01-07 14:04:32 浏览: 61
构造哈夫曼树,并生成编码
首先计算每个节点的权值,即将相邻两个数相加,如下所示:
2+3=5
5+5=10
7+8=15
10+10=20
15+11=26
接下来,将这些权值构造成哈夫曼树。我们可以从最小的两个权值开始,构造出一棵新的子树,并将其权值设置为这两个权值之和。我们不断重复这个过程,直到最后只剩下一棵树为止。构造的过程如下:
```
5 7 11 20 26
/ \ / \ / \ |
2 3 5 7 8 11 20
\ / \ / \
5 8 10 15 26
| |
2 3
```
最后,我们来计算WPL(带权路径长度)。WPL是指每个叶子节点的权值乘以该节点到根节点的路径长度之和。将每个叶子节点的权值和路径长度相乘,再求和即可:
WPL = 2*3 + 3*3 + 5*2 + 7*2 + 8*2 + 11*2 = 66
因此,利用2 3 5 7 8 11构造的哈夫曼树的WPL为66。
阅读全文