用12, 3, 4, 56, 7, 9, 5, 13, 21, 28构造哈夫曼树
时间: 2024-05-01 18:22:17 浏览: 13
首先,根据哈夫曼树的构建原理,我们需要将给定的数字按照权重从小到大进行排序。排序结果如下:
```
3, 4, 5, 7, 9, 12, 13, 21, 28, 56
```
接下来,我们将相邻的两个数字合并成一个节点,权重为它们的和。每次合并后都要将新生成的节点按照权重插入到适当的位置,以保持权重的有序性。重复这个过程,直到只剩下一个节点,即为哈夫曼树的根节点。
下面是具体的构建过程:
1. 合并3和4,得到一个权重为7的节点。插入节点后,当前节点集合为:
```
5, 7, 9, 12, 13, 21, 28, 56, 7
```
2. 合并5和7,得到一个权重为12的节点。插入节点后,当前节点集合为:
```
9, 12, 13, 21, 28, 56, 12
```
3. 合并9和12,得到一个权重为21的节点。插入节点后,当前节点集合为:
```
13, 21, 28, 56, 21
```
4. 合并13和21,得到一个权重为34的节点。插入节点后,当前节点集合为:
```
28, 34, 56
```
5. 合并28和34,得到一个权重为62的节点。插入节点后,当前节点集合为:
```
56, 62
```
6. 最后,合并56和62,得到一个权重为118的节点,这个节点即为哈夫曼树的根节点。
哈夫曼树的结构如下所示:
```
118
/ \
56 62
/ \
28 34
/ \
13 21
/ \
9 12
/ \
3 4
```