W=(3,12,7,4,2,8,11),构造一颗哈夫曼树,并计算树的带权路径长度
时间: 2023-09-15 14:19:43 浏览: 182
好的,根据您提供的权值 W=(3,12,7,4,2,8,11),我们可以构造哈夫曼树如下:
```
42
/ \
/ \
19 23
/ \ / \
8 11 11 12
/ \ / \
3 5 7 4
```
树的带权路径长度为 3*2 + 5*2 + 4*2 + 7*2 + 4*3 + 11*2 + 12*2 = 104。
相关问题
给定叶节点权值:(2,3,5,7,8,11),构造哈夫曼树,并计算其带权路径长度WPL。
首先,我们需要将叶节点按照权值从小到大排序:(2,3,5,7,8,11)
然后,我们需要将权值最小的两个节点合并为一个新节点,其权值等于这两个节点的权值之和。这里我们可以选择先合并2和3,得到一个新节点5,然后将5和5合并,得到一个新节点10,再将7和8合并,得到一个新节点15,最后将10和15合并,得到一个根节点25。
构造出的哈夫曼树如下所示:
```
25
/ \
10 15
/ \ / \
5 5 7 8
| |
2 3
```
根据定义,带权路径长度WPL等于每个叶节点的权值乘以它到根节点的路径长度之和,最后再把所有叶节点的WPL相加。因此,我们可以计算出每个叶节点的WPL如下所示:
```
WPL(2) = 2*3 = 6
WPL(3) = 3*3 = 9
WPL(5) = 5*2 = 10
WPL(7) = 7*2 = 14
WPL(8) = 8*2 = 16
WPL(11) = 11*2 = 22
```
然后,我们可以将每个叶节点的WPL相加,得到总的WPL:
```
WPL = 6 + 9 + 10 + 14 + 16 + 22 = 77
```
因此,构造出的哈夫曼树的带权路径长度为77。
2、给定一组权值:3,3,7,7,11,13,17,试构造一棵哈夫曼树,并计算出带权路径长度。
首先将权值从小到大排列,得到3,3,7,7,11,13,17。
然后将相邻的两个权值合并成一个节点,权值为它们的和,得到6,14,18,11,13,17。此时,又将相邻的两个节点合并,得到20,29,11,13,17。最后,将20和29合并,得到49,构成了一棵哈夫曼树。
根据哈夫曼树的定义,带权路径长度是每个叶子节点的权值乘以它到根节点的路径长度之和,再将所有叶子节点的结果相加。因此,可以计算出带权路径长度为:
3*3 + 3*3 + 7*2 + 7*2 + 11*2 + 13*2 + 17*2 = 109
因此,构造的哈夫曼树的带权路径长度为109。