给出以数据序列{10,2,7,13,9,12,18}为节点权植所构造的哈弗曼树并计算该树的加权路径和长度WPL.

题目

给出以数据序列{10,2,7,13,9,12,18}为节点权植所构造的哈弗曼树并计算该树的加权路径和长度WPL.

答案

1:那么首先取出最小的两个,即2,7.构成以下图案.
9
| |
2 7
集合便成为了 {7,9,10,12,13,18}
2：从中选出两个最小的.即 7 ,9.
即变成 16
| |
9 7
| |
2 7
集合即变成了{10,12,13,16,18}
3:从中选取两个最小的.即 10,12；
即构成：
22
| |
10 12
集合即变成了{13,16,18,22}
4：从中选取两个最小的.即13,16.
即变成 29
| |
16 13
| |
9 7
| |
2 7
集合变成了{18,22,29}；
5：同样,取出18,22；
即构成：
40
| |
22 18
| |
10 12
集合即变成{29,40}；
6：将29,40,联合起来.
69
| |
29 40
| | | |
16 13 22 18
| | | |
9 7 10 12
| |
2 7
即变成了{69}；
那么就已经完成了.
可以看到最初的集合里的数都变成了叶子.
WPL就是用 叶子节点乘以它的层数,然后 累加起来就是啦.
即（13+18）*2+（7+10+12）*3+（2+7）*4 =205.
注意：是用 【叶子节点】 乘以 层数.根为第0层.
参考下我回答过的 参考资料,