最优二叉树哈夫曼树.doc

第四讲最优二叉树——哈夫曼树
目录
第四讲最优二叉树——哈夫曼树 154
第七章最优二叉树——哈夫曼树 155
156
7. 2 哈夫曼树的构造算法 158
160
文件的编码和解码 162
162
习题 163
第七章最优二叉树——哈夫曼树
【重点与难点】
带权二叉树与哈夫曼树基本概念;
构造哈夫曼树;
哈夫曼编码及其算法实现。
【引入】
在实际应用中,常常要考虑一个问题:如何设计一棵二叉树,使得执行路径最短,即算法的效率最高。

假设邮政局的包裹自动测试系统能够测出包裹的重量,如何设计一棵二叉树将包裹根据重量及运距进行分类从而确定邮资。
国内快递包裹资费单位:元
(2004年1月1日起执行)
运距(公里)
首重1000克
5000克以内续重每500克
5001克以上续重每500克
<=500



<=1000 >500



<=1500 >1000



<=2000 >1500



<=2500 >2000



<=3000 >2500



<=4000 >3000



<=5000 >4000



<=6000 >5000



>6000



国家邮政局制定的快递包裹参考标准
,但不同的二叉树判定的次数可能不一样,执行的效率也不同。
铁球分类
现有一批球磨机上的铁球,需要将它分成四类:直径不大于20的属于第一类;直径大于20而不大于50的属于第二类;直径大于50而不大于100的属于第三类;其余的属于第四类;假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。
:
两种判断二叉树示意图
那么究竟将这个判断过程表示成哪一个判断框,才能使其执行时间最短呢?让我们对上述判断框做一具体的分析。
假设有1000个铁球,则各类铁球的个数分别为:100、200、300、400;
:
左图
右图
序号
比较式
比较次数
序号
比较式
比较次数
1
a<=20
1000
1
a>100
1000
2
a<=50
900
2
a>50
600
3
a<=100
700
3
a<=20
300
合计
2600
合计
1900
两种判断二叉树比较次数
过上述分析可知,。为了找出比较次数最少的判断框,将涉及到树的路径长度问题。

最优二叉树,也称哈夫曼(Haffman)树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树。
那么什么是二叉树的带权路径长度呢?
在前面我们介绍过路径和结点的路径长度的概念,而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值,则可将这一概念加以推广。设二叉树具有n个带权值的叶结点,那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度,记为:
n
∑
k=1
WPL= Wk·Lk
其中Wk为第k个叶结点的权值,Lk 为第k个叶结点的路径长度。,它的带权路径长度值WPL=2×2+4×2+5×2+3×2=28。
在给定一组具有确定权值的叶结点,可以构造出不同的带权二叉树。例如,给出4个叶结点,设其权值分别为1,3,5,7,我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。。
这五棵树的带权路径长度分别为:
(a)WPL=1×2+3×2+5×2+7×2=32
3
5
4
2
(b)WPL=1×3+3×3+5×2+7×1=29
(c)WPL=1×2+3×3+5×3+7×1=33
(d)WPL=7×3+5×3+3×2+1×1=43 一个带权二叉树
(e)WPL=7×1+5×2+3×3+1×3=29