对给定的一组权值W=(1,2,3,7,20,3,2,4,8,10),试构造相应的哈夫曼树,并计算它的带权路径长度
时间: 2023-10-08 10:05:38 浏览: 69
好的,我会根据您的要求回答您的问题。
对于给定的权值W=(1,2,3,7,20,3,2,4,8,10),可以按照以下步骤构造相应的哈夫曼树:
1. 将权值从小到大进行排序,得到W'=(1,2,2,3,3,4,7,8,10,20)。
2. 取出W'中权值最小的两个节点1和2,构造出新节点(1,2),其权值为1+2=3。
3. 将(1,2)节点插入W'中,并删除原来的1和2节点,得到W''=(3,2,3,4,7,8,10,20)。
4. 重复步骤2和3,直到W''中只剩下一个节点,即哈夫曼树的根节点为止。
最后构造出的哈夫曼树如下所示:
58
/ \
/ \
/ \
/ \
/ \
/ \
33 25
/ \ / \
12 21 10 15
/\ /\
3 9 8 13
哈夫曼树的带权路径长度为58,即每个叶子节点权值与根节点的距离之积的总和。
带权路径长度的计算方法如下:
节点 权值 距离 权值*距离
3 1 3 3
9 2 2 4
8 2 2 4
13 3 1 3
10 7 1 7
15 20 1 20
25 3 2 6
33 4 2 8
58 10 1 10
总和 58
因此,哈夫曼树的带权路径长度为58。