《哈夫曼树和图的应用》由会员分享，可在线阅读，更多相关《哈夫曼树和图的应用（25页珍藏版）》请在金锄头文库上搜索。
1、在此幻灯片插入公司的徽标 从“插入”菜单 选择图片 找到徽标文件 单击“确定” 重新设置徽标大小 单击徽标内任意位置。徽标外部 出现的方框是“调整控点” 使用这些重新设置对象大小 如果在使用尺寸调整控点前按下 shift 键，则对象改变大小但维 持原比例。 10 65 865 姓名 学号 成绩 班级 李红 9761059 95 机97.6 A BC DE FG Date 1 2.5.3哈夫曼树及其应用 1、哈夫曼树 树的路径长度的概念： 从一个结点到另一个结点之间的分支数 目称为这对结点之间的路径长度。 树的路径长度是从树的根到每一结点的 路径长度之和。 Date 2 1 2 45 3 67
2、PL=0+1+1+2+2+2+2=10 树的路径长度用PL表示 。 Date 3 1 2 45 3 67 PL=0+1+1+2+2+2+2=10 1 2 45 C 67 PL=0+1+1+2+2+3+3=12 树的路径长度用PL表示 。 Date 4 结点带权的路径长度： 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度： 树中叶子结点带权路径长度之和。 abcd 7524 WPL=7*2+5*2+2*2+4*2=36 Date 5 树的带权路径长度记作： 其中：Wk为树中每个叶子结点的权； L k为每个叶子结点到根的路径长度。 abcd 7524 WPL=7*2+5*2+2*
3、2+4*2=36 WPL最小的二叉树就称作最优二叉树或哈夫曼树 。 Date 6 abcd 7524 WPL=7*2+5*2+2*2+4*2=36 d c ab 2 4 75 WPL=7*3+5*3+2*1+4*2=46 a b cd 7 5 24 WPL=7*1+5*2+2*3+4*3=35 哈夫曼树 （最优树） 加权路径长度最小的二叉树就 是哈夫曼树。 公式： Date 7 6 75 cd (b) 11 b 5 7 cd (c) 18 a 7 11 cd b 5 6 24 (d) abcd 7524 (a) 2、哈夫曼树的构造 例：给定权值7，5，2，4，构造哈夫曼树。 方法： （1）由原
4、始数据生成森林； (2) 在森林中选取两棵根结点权值最小的和次小的二 叉树作为左右子树构造一棵新的二叉树，其根结点的 权值为左右子树根结点权值之和。规定左子树根结点 的权值小于右子树根结点的权值。 （3）将新的二叉树加入到森林F中，去除原两棵权值 最小的树； （4）重复2、3步骤，直至F中只剩一棵树为止。 注意：参看书中P53的例子。 Date 8 3、哈夫曼树的应用 （1）判定树 在解决某些判定问题时，利用哈夫曼树可以得到最 佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构 来实现。 a60 a70 a80 a90 不及格 中等 良好优秀
5、 及格 YN YN Y N YN (a) 输入10000个 数据，则需进 行31500次比 较。 Date 9 分数0596069707980899099 比例0.050.150.40.30.10 70a 80 a60 及格 中等 良好 80a90 60a70 不及格 优秀 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个 数据，仅需进 行22
6、000次比 较。 Date 10 14 68 3344 22 0 00 0 1 11 1 T;A CS 各字符编码是 T ； A C S 00 01 10 110 111 上述电文编码： 11010111011101000011111000011000 方法： （1）用 2，4， 2，3， 3 作为叶子结点的权值生成一棵哈 夫曼树，并将对应权值wi的叶子结点注明对应的字符； （2）约定左分支表示字符“0”，右分支表示字符1 （3）从叶子结点开始，顺着双亲反推上去，直到根结点，路 径上的0或1连接的序列就是结点对应的字符的二进制编码 的逆序。 （2）哈夫曼编码-利用哈夫曼树构造通讯中电文编码（前
7、缀码） 例2：要传输的电文是CAS；CAT；SAT；AT 要传输的字符集是 D=C，A，S，T， ； 每个字符出现的频率是W= 2，4， 2，3， 3 注意：编码的总长度恰好为哈夫曼树的带权路径长。 Date 11 11月1日上机作业： 1. 折半查找 2. 顺序查找 3. 选择排序 4. 快速排序 Date 12 2.6.1 图的基本概念 2.6 图 BAC D 6 3 2 1 5 顶点:图中的数据元素 V表示顶点的非空有限集合。 VR表示两个顶点之间关系的集合。 Date 13 图 有向图 无向图 在有向图中，表示从V1到V3的一条弧。 V1为弧尾或初始点，V3为弧头或终端点。 在无向图中
8、，(V1，V3)表示V1和V3之间的一条边。 V1V3 V2V4 V1V3 V2V4 Date 14 V1V3 V2V4 V1V3 V2V4 顶点集合V=V1 ， V2 ， V3 ， V4 弧的集合G=, , , 顶点集合V=V1 ， V2 ， V3 ， V4 边的集合E=(V1, V3), (V1, V2), (V1, V4),(V2, V4) G=( V, E ) 顶点(V1, V3)与 (V3, V1)表示同一条边 Date 15 BAC D 6 3 2 1 5 权：与图的边或弧相关的数。 网：带权的图。 顶点的度：依附于该顶点的边数或弧数。 出度：（仅对有向图）以该顶点为尾的弧数。 入
9、度：（仅对有向图）以该顶点为头的弧数。 路径：顶点A与顶点C之间存在一条路径。路 径上边或弧的数目称为该路径的路径长度。 Date 16 （1）图的连接矩阵表示法 （2）图的邻接表示法 2.6.2 图的存储结构 Date 17 V1V3 V2V4 V1V3 V2V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0 图的连接矩阵表示法 Date 18 邻接矩阵表示法对求顶点的度很方便。 在无向图中： 顶点的度数=矩阵中对应
10、该顶点的行或列中非 零元素的个数。 在有向图中： 顶点的出度=矩阵中对应该顶点的行中非零元 素的个数。 顶点的入度=矩阵中对应该顶点的列中非零元 素的个数。 Date 19 V1V3 V2V4 V1V3 V2V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0 入度 出度 1 1 1 1 2 1 0 1 度数 3 2 1 2 Date 20 V1V3 V2V4 1 2 3 4 2 1 11 3 4 42 1 34 1 2
11、 3 4 V1V3 V2V4 4 图的邻接表表示法：即对图中每个顶点建立一个单链表，第i个 单链表中的结点表示依附于该顶点Vi的边（或弧） Date 21 2.6.3 图的应用 图的应用非常广泛，例如： 用图可以表示一座城市的交通联系的情况； 用有值图可以表示两座城市之间的距离、车费、或 班次数目。 表示城市之间建立的通讯网络 可以描述化学结构式。 图中两点之间的最短距离问题。 Date 22 作业： P77 第26题、第28题 第30题（1）、（2）、(3) 第31题（1）、（2）、（3） Date 23 28.有n个叶子结点的哈夫曼树，其结点总数为2n-1 26. 1100 Date 24 35 8 17 11 55 9 2728 CD A E B 0 0 0 0 1 1 1 1 26. 设电文中出现的字符 为A, B, C, D, E，每个字 母在电文中出现的次数分 别为 9, 7 , 3, 5,11，按哈 夫曼得出C的编码是： C的编码是1100 Date 25
