构造权值为 { 5, 13, 21, 7, 18, 30, 41 }的哈夫曼树。
时间: 2023-10-02 17:12:34 浏览: 54
首先,将权值从小到大排序:{ 5, 7, 13, 18, 21, 30, 41 }。
然后,我们可以按照以下步骤构造哈夫曼树:
1. 选取最小的两个权值:5 和 7。
2. 将它们合并成一个节点,节点权值为它们的和:12。
3. 新节点的左子树是原来的5,右子树是原来的7。
4. 新节点的权值12加入到权值序列中,此时序列为{ 12, 13, 18, 21, 30, 41 }。
5. 重复步骤1-4,直到只剩下一个节点为止。
按照上述步骤,我们可以得到以下哈夫曼树:
```
127
/ \
/ \
12 15
/ \ / \
5 7 13 18
/ \
21 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
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)