设给定权集w={2,3,4,7,8,9},构造关于w的一棵Huffman树,则:(1)树的带权路径长度WPL=填空1 (2)以根结点作为第1层,权值为4的结点的层次数为:空2
时间: 2024-03-16 11:48:01 浏览: 38
根据Huffman树的构造方法,我们可以先将权集中的数字按照从小到大的顺序排列,即w={2,3,4,7,8,9}。然后,我们可以依次将权值最小的两个数字合并成一个节点,直到最终合并成一棵树为止。
具体过程如下:
1. 将2和3合并成一个节点,权值为5
2. 将4和5合并成一个节点,权值为9
3. 将7和8合并成一个节点,权值为15
4. 将9和15合并成一个节点,权值为24
最终得到的Huffman树如下所示:
```
24
/ \
/ \
9 15
/ \ / \
4 5 7 8
/ \
2 3
```
根据Huffman树的性质,树的带权路径长度WPL等于所有叶子节点的权值乘以它们到根节点的路径长度之和。因此,我们可以计算出WPL=2*3 + 3*3 + 4*2 + 7*2 + 8*2 + 9*1 = 67。
根据题目要求,权值为4的节点的层次数为3,因此空2的答案为3。
相关问题
数据结构设给定权值集合w={3,5,7,8,11,12} ,请构造关于w的一棵huffman树。
好的,这是一个关于数据结构的问题,我可以回答。以下是构造出来的Huffman树(其中叶节点上的数字表示对应权值,非叶节点上的数字表示对应节点的权重):
```
46
/ \
23 23
/ \ / \
12 11 8 15
/ \ / | / \
5 7 3 5 7 8
```
希望能对您有所帮助。
设给定权值集合w={3,5,7,8,11,12} ,请构造关于w 的一棵huffman树,并求其加权路径长度WPL 。
好的,根据给定的权值集合w,我们可以构造如下的Huffman树:
```
46
/ \
21 25
/ \ / \
8 13 11 14
/ \
5 6
```
构造Huffman树的过程如下:
- 首先将w中的所有元素看作一棵森林,每个元素对应一棵只有一个节点的树;
- 从森林中选取权值最小的两棵树合并,构造成一棵新树,其根节点的权值为两棵树根节点权值之和;
- 将新树加入森林中,并从森林中删除被合并的两棵树;
- 重复执行上述步骤,直到森林中只剩下一棵树为止。
根据上述过程,我们可以得到上面的Huffman树。接下来,我们计算其加权路径长度WPL:
```
WPL = 3*4 + 5*3 + 7*3 + 8*3 + 11*2 + 12*2 = 94
```
因此,构造出的Huffman树的加权路径长度WPL为94。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)