哈夫曼树，求解析，数据结构

Question

35.(填空题， 2.5 分)
有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9,试构造一棵哈夫曼树,则其加权路径长度WPL为多少，求解析

Answer 1

那么加权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80

（结点到树根之间的路径长度与该结点上权的乘积）

构造哈夫曼树的办法是：在W中选出两个权小结点，并同时计算出它们的和，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。