用权集{5,7,2,3,6,8,9}构建一颗哈夫曼树给出过程
时间: 2023-03-05 15:33:35 浏览: 80
根据节点权值构建霍夫曼树
构建哈夫曼树的过程如下:
1. 将权值从小到大排序,得到集合{2, 3, 5, 6, 7, 8, 9}。
2. 选取权值最小的两个节点2和3,将它们合并为一个新节点,其权值为2+3=5。这个新节点代表的子树有2和3两个节点。
3. 将得到的新节点5插入集合中,集合变为{5, 5, 6, 7, 8, 9}。
4. 选取权值最小的两个节点5和5,将它们合并为一个新节点,其权值为5+5=10。这个新节点代表的子树有两个节点5。
5. 将得到的新节点10插入集合中,集合变为{6, 7, 8, 9, 10}。
6. 选取权值最小的两个节点6和7,将它们合并为一个新节点,其权值为6+7=13。这个新节点代表的子树有6和7两个节点。
7. 将得到的新节点13插入集合中,集合变为{8, 9, 10, 13}。
8. 选取权值最小的两个节点8和9,将它们合并为一个新节点,其权值为8+9=17。这个新节点代表的子树有8和9两个节点。
9. 将得到的新节点17插入集合中,集合变为{10, 13, 17}。
10. 选取权值最小的两个节点10和13,将它们合并为一个新节点,其权值为10+13=23。这个新节点代表的子树有10和13两个节点。
11. 将得到的新节点23插入集合中,集合变为{17, 23}。
12. 最后,选取权值最小的两个节点17和23,将它们合并为一个新节点,其权值为17+23=40。这个新节点代表的子树有整棵哈夫曼树。
构建完毕,下面是这颗哈夫曼树的形状:
```
40
/ \
/ \
17 23
/ \
8 9
/ \ \
5 3 6
\
2
```
在这个哈夫曼树中,每个叶子节点代表一个权值。哈夫曼编码可以通过从根节点出发,遍历到每个叶子节点,记录下经过的路径方向(0表示向左,1表示向右),得到每个叶子节点的编码。编码的长度为从根节点到叶子节点路径上经过的边数,也就是叶子节点对应权值的码长。
阅读全文