若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是
时间: 2023-06-12 16:04:49 浏览: 781
霍夫曼树带权路径长度求值.cpp
哈夫曼树的带权路径长度(WPL)是指所有叶子节点的权值乘以其到根节点的路径长度之和。构造哈夫曼树的过程是将权值从小到大排序,每次取出权值最小的两个节点合并成一个新的节点,并将其权值设为两个节点权值之和。重复此过程直至只剩下一个节点,即为哈夫曼树的根节点。
对于给定的权值{4, 5, 6, 7, 8},构造哈夫曼树的过程如下:
1. 取出权值最小的两个节点4和5,将它们合并成一个新的节点,权值为9,得到如下子树:
```
9
/ \
4 5
```
2. 取出权值最小的两个节点6和7,将它们合并成一个新的节点,权值为13,得到如下子树:
```
13
/ \
6 7
```
3. 将上面两个子树合并成一个新的节点,权值为22,得到如下哈夫曼树:
```
22
/ \
13 9
/ \
6 7
```
计算带权路径长度(WPL):
```
WPL = 4*3 + 5*3 + 6*2 + 7*2 + 8*2 = 12 + 15 + 12 + 14 + 16 = 69
```
因此,给定的权值{4, 5, 6, 7, 8}构造的哈夫曼树的带权路径长度为69。
阅读全文