有七个带权结点,其权值分别为3,13,8,2,6,10,14,试以它们为叶子结点构造一棵哈夫 曼树(要求满足左孩子权值不超过右孩子权值的原则)。请画出该哈夫曼树,并计算 其带权路径长度 WPL,
时间: 2024-11-30 10:18:11 浏览: 13
大学数据结构期末考试试题(有答案)-aa72220b76c66137ee061980.doc
为了构建一棵满足哈夫曼树规则的树,我们需要按照以下步骤操作:
1. 首先,将给定的7个节点按照权值从小到大排序:2, 3, 6, 8, 10, 13, 14。
2. 将两个最小的节点合并为一个新的节点,这个新节点的权值是两个小节点权值之和:2 + 3 = 5。
3. 接下来,将这个新节点和下一个最小节点(在这里是6)进行合并:5 + 6 = 11。
4. 以此类推,每次合并两个已排序的最小节点,直到只剩下一个节点,即为哈夫曼树的根节点。
下面是哈夫曼树的构造过程:
```
14 (1)
/ \
11 13 (13)
/ \ \
5 8 2 (2)
\
6 (6)
```
现在我们已经得到了哈夫曼树。为了计算带权路径长度(WPL),我们需要从根节点开始,向下遍历每个边,权重之和就是WPL。
从根到叶子的路径:
- 2 = 3
- 从11到8: 11 - 8 = 3
- 从8到6: 8 - 6 = 2
WPL = 3 + 6 + 3 + 3 + 2 = 17
所以,这棵哈夫曼树的带权路径长度WPL是17。
阅读全文