哈夫曼树带权路径长度
一. 长什么样?
左边是普通树,右边是哈夫曼树
图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