用5个权值3 2 4 5 1构造的哈夫曼树的带权路径长度
时间: 2024-03-20 16:42:48 浏览: 27
首先,我们需要构造哈夫曼树。具体步骤如下:
1. 将权值从小到大排序,得到:1 2 3 4 5。
2. 取出权值最小的两个节点 1 和 2,构造一个新节点,权值为它们的和 3,将新节点插入到原来的节点中,得到:3 3 4 5。
3. 取出权值最小的两个节点 3 和 3,构造一个新节点,权值为它们的和 6,将新节点插入到原来的节点中,得到:4 5 6。
4. 取出权值最小的两个节点 4 和 5,构造一个新节点,权值为它们的和 9,将新节点插入到原来的节点中,得到:9 6。
5. 取出权值最小的两个节点 6 和 9,构造一个新节点,权值为它们的和 15,得到最终的哈夫曼树。
```
15
/ \
6 9
/ \
4 5
```
接下来,计算带权路径长度(WPL),即每个叶子节点的权值乘以它到根节点的路径长度之和,然后把所有叶子节点的 WPL 相加即可。
- 叶子节点 1 的 WPL:1 × 3 = 3
- 叶子节点 2 的 WPL:2 × 3 = 6
- 叶子节点 3 的 WPL:3 × 2 = 6
- 叶子节点 4 的 WPL:4 × 2 = 8
- 叶子节点 5 的 WPL:5 × 2 = 10
总的 WPL = 3 + 6 + 6 + 8 + 10 = 33。
所以,用5个权值3 2 4 5 1构造的哈夫曼树的带权路径长度为 33。
相关问题
用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是( )。
首先我们需要构建哈夫曼树。哈夫曼树的构建过程如下:
1. 将所有权值从小到大排序,得到{1, 2, 3, 4, 5}。
2. 取出权值最小的两个节点1和2,构建一个新节点,权值为1+2=3,作为1和2的父节点。
3. 将3插入到排序后的序列中,得到{3, 3, 4, 5}。
4. 取出权值最小的两个节点3和3,构建一个新节点,权值为3+3=6,作为3和3的父节点。
5. 将6插入到排序后的序列中,得到{4, 5, 6}。
6. 取出权值最小的两个节点4和5,构建一个新节点,权值为4+5=9,作为4和5的父节点。
7. 将9插入到排序后的序列中,得到{6, 9}。
8. 取出权值最小的两个节点6和9,构建一个新节点,权值为6+9=15,作为6和9的父节点。
9. 得到哈夫曼树,其带权路径长度为:1*3 + 2*3 + 3*4 + 4*5 + 5*1 = 49。
因此,用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是49。
试用权集合{12、4、5、6、1、2构造哈夫曼树,并计算哈夫曼树的带权路径长度}
首先按照权值从小到大排序,得到:{1, 2, 4, 5, 6, 12}。
接下来构造哈夫曼树:
1. 选取权值最小的两个节点1和2,合并成一个新节点3,权值为1+2=3。
2. 将新节点3插入到原节点中,得到{3, 4, 5, 6, 12}。
3. 选取权值最小的两个节点3和4,合并成一个新节点5,权值为3+4=7。
4. 将新节点5插入到原节点中,得到{5, 6, 7, 12}。
5. 选取权值最小的两个节点5和6,合并成一个新节点7,权值为5+6=11。
6. 将新节点7插入到原节点中,得到{7, 11, 12}。
7. 最后选取权值最小的两个节点7和11,合并成一个新节点18,权值为7+11=18。
8. 得到最终的哈夫曼树:
```
18
/ \
7 11
/ \
3 4
/ \
1 2
```
最后计算带权路径长度:(1\*2)+(2\*2)+(3\*2)+(4\*2)+(5\*1)+(6\*1)=42。