哈夫曼树(最优树) 加权路径长度最小的二叉树就 是哈夫曼树。 公式: WPL=∑WkLK 7 52 4 WPL=7*2+5*2+2*2+4*2=36 c2 7 a 4(d 5(b 2 d)4 7 5 WPL=7*3+5*3+2*1+4*2=46 WPL=7*1+5*2+2*3+4*3=35 2/22 202l/2/
2021/2/22 7 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 d c a b 2 4 7 5 WPL=7*3+5*3+2*1+4*2=46 a b c d 7 5 2 4 WPL=7*1+5*2+2*3+4*3=35 哈夫曼树 （最优树） 加权路径长度最小的二叉树就 是哈夫曼树。 公式： = = n k WPL WKLK 1
2、哈夫曼树的构造 例:给定权值{7,5,2,4},构造哈夫曼树。 6 方法 5 52 C d L)属始数据生成森林 (2)在森林中选取两棵根结点权值最小的和次小的二 叉树作为君子树构造一棵新的二叉树,其根结点的 权值为左右子树根结点权值之和。规是左子树根结点 的权值小于右子树根结点的权值。 3将新树加入到率林,去除原两棘权值 最小的树; (4)复2、,直至F中只剩一树为止。6 注意:参看中P5的例子。 d C (d 2 2/22 202l/2/
2021/2/22 8 6 7 5 c d (b) 11 b 5 7 c d (c) 18 7 a 11 c d b 5 6 (d) 2 4 a b c d 7 5 2 4 (a) 2、哈夫曼树的构造 例：给定权值{7，5，2，4}，构造哈夫曼树。 方法： （1）由原始数据生成森林； (2) 在森林中选取两棵根结点权值最小的和次小的二 叉树作为左右子树构造一棵新的二叉树，其根结点的 权值为左右子树根结点权值之和。规定左子树根结点 的权值小于右子树根结点的权值。 （3）将新的二叉树加入到森林F中，去除原两棵权值 最小的树； （4）重复2、3步骤，直至F中只剩一棵树为止。 注意：参看书中P53的例子
3、哈夫曼树的应用 (1)判定树 在解决某些判定问题时,利用哈夫曼树可以得到最 佳判定算法 例1将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的,可用图(a)二叉树结构 来实现。 N O「不及格 a<70 输入1000个 及格 <80 数据,则需进 行31500次比 中等 a<90 N 较。 良好 优秀 a 2/22 202l/2/
2021/2/22 9 3、哈夫曼树的应用 （1）判定树 在解决某些判定问题时，利用哈夫曼树可以得到最 佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构 来实现。 a<60 a<70 a<80 a<90 不及格 中等 良好 优秀 及格 Y N Y N Y N Y N (a) 输入10000个 数据，则需进 行31500次比 较