若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是( )。
时间: 2024-05-01 15:23:55 浏览: 225
构造哈夫曼树的步骤是将权值从小到大排序,每次取出最小的两个权值构造一个新节点,将这两个节点作为新节点的左右子节点,新节点的权值为左右子节点的权值之和,然后将新节点的权值放回排序后的权值序列中。重复以上步骤,直到只剩下一个节点为止。
按照这个步骤,可以得到以下的构造过程:
1. 将{4,5,6,7,8}排序,得到{4,5,6,7,8}。
2. 取出最小的两个权值4和5,构造一个新节点,新节点的权值为4+5=9,将这两个节点作为新节点的左右子节点,得到以下树形结构:
```
9
/ \
4 5
```
3. 将{6,7,8,9}排序,得到{6,7,8,9}。
4. 取出最小的两个权值6和7,构造一个新节点,新节点的权值为6+7=13,将这两个节点作为新节点的左右子节点,得到以下树形结构:
```
13
/ \
6 7
/ \
4 5
```
5. 将{8,9,13}排序,得到{8,9,13}。
6. 取出最小的两个权值8和9,构造一个新节点,新节点的权值为8+9=17,将这两个节点作为新节点的左右子节点,得到以下树形结构:
```
13
/ \
6 7
/ \
4 5
/ \
8 9
```
7. 将{13,17}排序,得到{13,17}。
8. 取出最小的两个权值13和17,构造一个新节点,新节点的权值为13+17=30,将这两个节点作为新节点的左右子节点,得到以下树形结构:
```
30
/ \
13 17
/ \
6 7
/ \
4 5
/ \
8 9
```
最终得到的哈夫曼树的带权路径长度为:
```
4*2 + 5*2 + 6*2 + 7*2 + 8*2 = 60
```
因此,答案是60。
阅读全文