用权集{5,7,2,3,6,8,9}构建一颗哈夫曼树给出过程
时间: 2024-05-14 16:18:39 浏览: 16
1. 首先将权集中的元素按照从小到大的顺序排列,得到{2, 3, 5, 6, 7, 8, 9}。
2. 从中选取两个权值最小的元素,即2和3,构建一棵二叉树,将其权值设为2+3=5,得到:
```
5
/ \
2 3
```
3. 将这棵二叉树从权集中删除,将新的权集{5, 5, 6, 7, 8, 9}按照从小到大的顺序排列,得到{5, 5, 6, 7, 8, 9}。
4. 从中选取两个权值最小的元素,即5和5,构建一棵二叉树,将其权值设为5+5=10,得到:
```
10
/ \
5 5
```
5. 将这棵二叉树从权集中删除,将新的权集{6, 7, 8, 9, 10}按照从小到大的顺序排列,得到{6, 7, 8, 9, 10}。
6. 从中选取两个权值最小的元素,即6和7,构建一棵二叉树,将其权值设为6+7=13,得到:
```
13
/ \
6 7
```
7. 将这棵二叉树从权集中删除,将新的权集{8, 9, 10, 13}按照从小到大的顺序排列,得到{8, 9, 10, 13}。
8. 从中选取两个权值最小的元素,即8和9,构建一棵二叉树,将其权值设为8+9=17,得到:
```
17
/ \
8 9
```
9. 将这棵二叉树从权集中删除,将新的权集{10, 13, 17}按照从小到大的顺序排列,得到{10, 13, 17}。
10. 从中选取两个权值最小的元素,即10和13,构建一棵二叉树,将其权值设为10+13=23,得到:
```
23
/ \
10 13
```
11. 将这棵二叉树从权集中删除,得到最终的哈夫曼树:
```
48
/ \
/ \
23 25
/ \ / \
10 13 12 13
/ \
5 5
```
其中,每个叶子节点代表了原来权集中的一个元素,从左到右叶子节点代表的元素权值为{5, 7, 2, 3, 6, 8, 9}。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)