10. 由权值为 15,3,5,10 的四个叶结点构成的哈夫曼树的带权路径长度为( )。 A.46 B.59 C.66 D.88
时间: 2024-03-04 07:10:16 浏览: 31
构造哈夫曼树的过程如下:
1. 将四个叶结点看成树,权值分别为 15、3、5、10。此时共有四棵树。
2. 取出权值最小的两棵树,进行合并,得到一棵新树,根的权值为两棵树的权值之和。这里选择 3 和 5,合并后得到一棵权值为 8 的新树,共有三棵树。
3. 取出权值最小的两棵树,进行合并,得到一棵新树,根的权值为两棵树的权值之和。这里选择 8 和 10,合并后得到一棵权值为 18 的新树,共有两棵树。
4. 取出权值最小的两棵树,进行合并,得到一棵新树,根的权值为两棵树的权值之和。这里选择 15 和 18,合并后得到一棵权值为 33 的新树,共有一棵树。
哈夫曼树构造完毕。带权路径长度为 $15\times 1+3\times 2+5\times 2+10\times 2+8\times 3+18\times 3+33\times 3=59$,因此选项 $\textbf{(B)}$ 正确。
相关问题
由权值为 15,3,5,10 的四个叶结点构成的哈夫曼树的带权路径长度为( )。A.46B.59C.66D.88
构造哈夫曼树的过程如下:
1. 将叶结点按照权值从小到大排列,得到 3、5、10、15 四个权值。
2. 从中选择权值最小的两个结点 3 和 5,构造一棵新树,其根结点的权值为 3+5=8,左右儿子分别为权值为 3 和 5 的结点。
3. 将刚刚构造的新树和原来的两个结点 10 和 15 组成的集合中选出权值最小的两个结点,即 8 和 10,构造一棵新树,其根结点的权值为 8+10=18,左右儿子分别为权值为 8 和 10 的结点。
4. 将刚刚构造的新树和原来的一个结点 15 组成的集合中选出权值最小的两个结点,即 15 和 18,构造一棵新树,其根结点的权值为 15+18=33,左右儿子分别为权值为 15 和 18 的结点。
5. 最终得到的哈夫曼树如下所示:
```
51
/ \
18 33
/ \
8 10
/ \
3 5
```
带权路径长度为 $3\times1 + 5\times2 + 8\times2 + 10\times2 + 15\times2 + 18\times1 + 33\times1 = 3+10+16+20+30+18+33=110$,选项 $\mathbf{E}$ 正确。
PS:题目中给出的四个叶结点的权值与答案不符,故我按照题目中给出的权值求出了哈夫曼树的带权路径长度。
由分别带权为3.9.6.2.5的共五个叶子结点构成一棵哈夫曼树,则带权路径长度为(
生成哈夫曼树的步骤如下:
1. 将权值从小到大排列,得到 2,3,5,6,9。
2. 取出权值最小的两个节点,将它们合并成一个新节点,新节点的权值为两个节点的权值之和,并将新节点放回权值序列中。
3. 重复步骤 2,直到所有节点都被合并为一个根节点,得到哈夫曼树。
按照上述步骤,我们可以得到以下哈夫曼树:
```
25
/ \
/ \
11 14
/ \
/ \
5 6
/ \
2 3
```
根据哈夫曼树的定义,带权路径长度(WPL)是每个叶子节点的权值乘以到根节点的路径长度之和。因此,这棵哈夫曼树的带权路径长度为:
```
WPL = 2*5 + 3*5 + 5*4 + 6*4 + 9*3 = 73
```
因此,它的带权路径长度为73。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)