数据结构设给定权值集合w={3,5,7,8,11,12} ,请构造关于w的一棵huffman树。
时间: 2023-06-02 22:06:06 浏览: 376
好的,这是一个关于数据结构的问题,我可以回答。以下是构造出来的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。
设给定权值集合w={3,5,7,8,11,12} ,请构造关于w的一棵huffman树,并求其加权路径长度WPL 。
首先,我们需要按照权值从小到大的顺序将节点排序,得到w'={3,5,7,8,11,12}。然后,我们需要依次取出两个权值最小的节点,并将它们合并为一个新节点,其权值为它们的权值之和。这样,我们就可以构造出一棵huffman树。
具体步骤如下:
1. 取出权值最小的节点3和5,将它们合并为一个新节点,其权值为8,得到w''={7,8,8,11,12}。
2. 取出权值最小的节点7和8,将它们合并为一个新节点,其权值为15,得到w'''={11,12,15,8}。
3. 取出权值最小的节点11和12,将它们合并为一个新节点,其权值为23,得到w''''={15,23,8}。
4. 取出权值最小的节点15和8,将它们合并为一个新节点,其权值为23,得到w'''''={23,23}。
此时,我们得到了一棵huffman树,其根节点的权值为46。树的形状如下:
```
46
/ \
23 23
/ \
15 8
/ \
3 5
```
最后,我们需要计算出huffman树的加权路径长度WPL。计算方法是:将每个叶子节点的深度乘以其权值,再将所有叶子节点的乘积相加。对于上面的huffman树,其WPL为:
WPL = 3×5 + 3×8 + 2×11 + 2×12 + 2×15 + 2×23 = 235
因此,这棵huffman树的加权路径长度为235。