哈夫曼树1讲述.ppt

哈夫曼树（最优树）及其应用 路径长度的概念 树的路径长度（用PL表示）：从树的根到每一个结点的路径长度之和 PL = 0＋1＋1＋2＋2＋2＋2＋3 ＝13 0 1 4 3 2 5 6 7 PL = 0＋1＋1＋2＋2＋3＋3＋3 ＝15 0 1 4 3 2 5 6 7 结点的权： 给树的每个结点赋予的一个具有某种实际意义的实数。 结点的带权路径长度： 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度： 树中叶子结点带权路径长度之和。 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 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 哈夫曼树 （最优树） 加权路径长度最小的二叉树就是哈夫曼树。 公式： * * 具有不同带权路径长度的二叉树 哈夫曼树 带权路径长度达到最小的扩充二叉树即为哈夫曼树。哈夫曼树中，权值大的结点离根最近。 * * 问题2：什么样的带权树路径长度最小？ 例如：给定一个权值序列{2,3,4,7}，可构造的多种二叉树的形态。 (a) WPL=2×2＋2×3+2×4+2×7=32 2 3 4 7 4 2 3 7 (b) WPL=1×2＋2×3+3×4+3×7=41 4 2 3 7 3 7 4 2 (c) WPL=1×7＋2×4+3×3+3×2=30 18 a 7 11 c d b 5 6 2 4 (d) a b c d 7 5 2 4 (a) 哈夫曼树的构造 例：给定权值{7，5，2，4}，构造哈夫曼树。 (b) 6 a b c d 7 5 (c) 11 b 5 a c d 7 方法： （1）初始化：由原始数据生成森林； （2）找最小树：在森林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。规定左子树根结点的权值小于右子树根结点的权值。 （3）删除与加入：将新的二叉树加入到森林F中，去除原两棵权值最小的树； （4）判断：重复2、3步骤，直至F中只剩一棵树为止。 哈夫曼树的应用 （1）判定树 在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构来实现。 a60 a70 a80 a90 不及格 中等 良好 优秀 及格 Y N Y N Y N Y N (a) 输入10000个数据，则需进行28000次比较。 分数 0—59 60—69 70—79 80—89 90—99 比例 0.05 0.15 0.4 0.3 0.10 70≤a 80 a60 及格 中等 良好 80≤a90 60≤a70 不及格 优秀 Y N Y Y Y N N N (b) 不及格 Y a90 a80 a70 a60 优秀 中等 及格 良好 Y N N N (c) Y Y Y 学生成绩分布不是均匀的情况： 以比例数为权构造一棵哈夫曼树，如（b)判断树所示。 再将每一比较框的两次比较改为一次，可得到（c)判定树。 输入10000个数据，仅需进行22000次比较。 * * 2、哈夫曼编码 (1)前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。 (2)哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。 哈夫曼树的应用 14 6 8 3 3 4 4 2 2 0 0 0 0 1 1 1 1 T ; A C S 各字符编码是 T ； A C S ????? 00 01 10 110 111 上述电文编码： 11010111011101000011111000011000 方法： （1）用{ 2，4， 2，3， 3 }作为叶子结点的权值生成一棵哈夫曼树，并将对应权值wi的叶子结点注明对应的字符； （2）约定左分