构造权值为 { 5, 13, 21, 7, 18, 30, 41 }的哈夫曼树。
时间: 2023-10-05 22:07:44 浏览: 116
首先将权值从小到大排序,得到 { 5, 7, 13, 18, 21, 30, 41 },然后按照哈夫曼树的构造规则,不断合并权值最小的两个节点,直到只剩下一个根节点为止。
首先将 5 和 7 合并,得到一个权值为 12 的新节点。然后将 12 和 13 合并,得到一个权值为 25 的新节点。然后将 18 和 21 合并,得到一个权值为 39 的新节点。然后将 25 和 30 合并,得到一个权值为 55 的新节点。最后将 39 和 41 合并,得到一个权值为 80 的新节点。最终得到的哈夫曼树如下所示:
```
80
/ \
39 41
/ \
25 30
/ \
12 13
/ \
5 7
```
因此,权值为 { 5, 13, 21, 7, 18, 30, 41 } 的哈夫曼树为上面的树形结构。
相关问题
构造权值为 { 5, 13, 21, 7, 18, 30, 41 }的哈夫曼树,并画出来
首先,我们需要按照权值从小到大的顺序对节点进行排序:
{ 5, 7, 13, 18, 21, 30, 41 }
接下来,我们将权值最小的两个节点合并,得到一个新节点,新节点的权值为两个节点的权值之和。将新节点加入到排序后的节点序列中,并重新排序。重复这个过程,直到所有节点都被合并成为一个根节点为止。
下面是按照此方法构造出来的哈夫曼树:
```
135
/ \
/ \
23 41
/ \ / \
10 13 18 23
/ \ | | / \
5 5 5 7 10 13
```
其中,每个节点的数字表示该节点的权值。可以看到,根节点的权值为所有节点权值之和,即5+7+13+18+21+30+41=135。
权值为123456789构造哈夫曼树
根据提供的引用内容,构造哈夫曼树的步骤如下:
1. 根据给定的权值,构造n棵只有根结点的二叉树,这n棵二叉树构成一个森林F。
2. 在森林中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且新置的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
3. 在森林F中删除这两棵树,同时将新得到的二叉树加入F中。
4. 重复步骤2和3,直到F中只含一棵树为止。这棵树就是哈夫曼树。
根据给定的权值123456789,我们可以按照上述步骤构造哈夫曼树。首先,我们将每个权值作为一个独立的树,构成森林F。然后,我们选择权值最小的两棵树(1和2)作为左右子树构造一棵新的二叉树,根结点的权值为左右子树根结点的权值之和(1+2=3)。接下来,我们删除这两棵树,并将新得到的二叉树加入F中。重复这个过程,直到F中只含一棵树为止。
构造哈夫曼树的过程如下:
1. 构造森林F:根据给定的权值,构造9棵只有根结点的二叉树,分别为1, 2, 3, 4, 5, 6, 7, 8, 9。
2. 选择权值最小的两棵树:选择1和2作为左右子树构造一棵新的二叉树,根结点的权值为1+2=3。
3. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有8棵树:3, 3, 4, 5, 6, 7, 8, 9。
4. 选择权值最小的两棵树:选择3和3作为左右子树构造一棵新的二叉树,根结点的权值为3+3=6。
5. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有7棵树:4, 5, 6, 6, 7, 8, 9。
6. 选择权值最小的两棵树:选择4和5作为左右子树构造一棵新的二叉树,根结点的权值为4+5=9。
7. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有6棵树:6, 6, 7, 8, 9,9。
8. 选择权值最小的两棵树:选择6和6作为左右子树构造一棵新的二叉树,根结点的权值为6+6=12。
9. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有5棵树:7, 8, 9, 9, 12。
10. 选择权值最小的两棵树:选择7和8作为左右子树构造一棵新的二叉树,根结点的权值为7+8=15。
11. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有4棵树:9, 9, 12, 15。
12. 选择权值最小的两棵树:选择9和9作为左右子树构造一棵新的二叉树,根结点的权值为9+9=18。
13. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有3棵树:12, 15, 18。
14. 选择权值最小的两棵树:选择12和15作为左右子树构造一棵新的二叉树,根结点的权值为12+15=27。
15. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有2棵树:18, 27。
16. 选择权值最小的两棵树:选择18和27作为左右子树构造一棵新的二叉树,根结点的权值为18+27=45。
17. 删除选择的两棵树,并将新得到的二叉树加入F中,此时F中含有1棵树:45。
最终得到的哈夫曼树如下:
```
45
/ \
18 27
/ \
12 15
/ \
9 9
```
相关推荐
![](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)