哈夫曼树带权路径长度

一. 长什么样？

左边是普通树，右边是哈夫曼树

图a： WPL=5*2+7*2+2*2+13*2=54

图b： WPL=5*3+2*3+7*2+13*1=48

可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

二. 怎么生成和计算？

1. 总结

①先对权值从小到大排序。

②选两个最小的加起来成为一个新结点，而这两个最小的值是新结点的左右子结点。

③两个老的结点去掉，新的结点放入再次排序然后重复过程②。

④直到完全生成一棵树。

⑤计算的时候，只计算那些初始权值里面有的值，把它乘以深度（和传统说的深度不一样，是传统说的深度减一）加起来就是路径长度。

2. 例子

例：对于给定的一组权值w={1,4,9,16,25,36,49,64,81,100},构造具有最小带权外部路径长度的扩充二叉树，并求出他的的带权外部路径长度。

解答过程（红色表示原来的权值结点，蓝色是加出来的结点）：

带权外部路径长度计算：

WPL=2*100 + 3*64 + 2*81 + 4*25 + 3*49 + 3*36 + 5*16 + 6*9 + 7*1 + 7*4 =1078