给定权值集合w={3,5,7,8,11,12} ,请构造关于w的一棵huffman树,并求其加权路径长度WPL 。
时间: 2023-08-01 15:06:52 浏览: 67
首先,我们需要将权值从小到大排序,得到w={3,5,7,8,11,12}。
然后,我们依次取出权值最小的两个节点,将它们合并成一个新的节点,新节点的权值为这两个节点的权值之和。重复这个过程,直到所有节点都被合并成一个根节点。
具体来说,我们可以按照以下步骤构造Huffman树:
1. 将所有节点看作是一棵只有根节点的树。
2. 从w中取出权值最小的两个节点,将它们合并成一个新的节点,并将新节点插入到树中。
3. 将w中已经取出的两个节点从w中删除。
4. 重复步骤2和3,直到w中只剩下一个节点,即根节点。
构造出来的Huffman树如下所示:
```
46
/ \
/ \
18 28
/ \ / \
8 10 11 17
/ \ / \
3 5 7 8
```
最后,我们计算出Huffman树的加权路径长度WPL。WPL是指每个叶子节点的权值乘以从根节点到该叶子节点的路径长度之和的总和。
根据Huffman树,每个叶子节点的WPL分别为:
```
3 * 4 = 12
5 * 4 = 20
7 * 3 = 21
8 * 3 = 24
11 * 2 = 22
12 * 2 = 24
```
因此,Huffman树的WPL为12+20+21+24+22+24=123。
相关问题
数据结构设给定权值集合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。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)