数据结构算法之树的应用.ppt

树的应用 二叉树遍历的应用 o 1.查找数据元素 o 2. 求二叉树的高度 o 3. 求叶子结点数 设有100个学生某门课程的考试成绩的分布如下表 所示： 一、问题的提出(判断树) 分数05960697079 808990100 学生比例数0.050.150.400.300.10 学生成绩数据分布情况表 *问题：现在要编写程序依次根据每个学生的成绩 打印出该学生的成绩等级。 分数05960697079 808990100 学生比例数0.050.150.400.300.10 学生成绩数据分布情况表 方法1： a60 打印 “bad“ yes a70 no 打印 “pass“ yes a80 no 打印 “general “ yes a90 no 打印 “good“ yes 打印 “excellent “ no5%的 学生 15%的 学生 40%的 学生 30%的 学生 10%的 学生 共做315次比 较 读取一个学生成绩a 循环一百次 分数05960697079 808990100 学生比例数0.050.150.400.300.10 学生成绩数据分布情况表 方法2： a80 打印 “bad“ yes a90 no yes no a70 yes no a60 yes no 打印 “good“ 打印 “excellent “ 打印 “pass“ 打印 “general “ 5%的 学生 15%的 学生 40%的 学生 30%的 学生 10%的 学生 共做220次 比较 读取一个学生成绩 a 循环一百次 思考：如何找到一棵最优的判断树使得编写 出来的程序的运行时间是最高效的？ 1.哈夫曼树的有关概念 结点的路径长度： 从根结点沿某条路径到某结点途中所经历的边的条数 称为该结点的路径长度。 二、哈夫曼树及其应用 树的路径长度： 从根结点到每一个叶子结点的路径长度之和。 树的带权路径长度(WPL)： 树中所有叶子结点的带权路径长度之和称为树的带权 路径长度。 结点的带权路径长度： 某结点的路径长度与该结点上的权值的乘积称为该结 点的带权路径长度。 1.哈夫曼树的有关概念 二、哈夫曼树及其应用 实例：已知某二叉树的四个叶子结点 a,b,c,d 分别带权7，5，2，4，则可构造出有如下几 种不同形式的二叉树： a a a 7 7 7 b 5 b 5 c 2 d 4 c 2 d 4 b 5 c 2 d 4 树的带权路径长度为： WPL=2*7+2*5+2*2+ 2*4=36 树的带权路径长度为： WPL=2*4+3*7+3*5+ 1*2=46 树的带权路径长度为： WPL=1*7+2*5+3*2+ 3*4=35 哈夫曼树的定义： 二、哈夫曼树及其应用 设有n个叶子结点的二叉树，其第i个 叶子结点的权值为wi(i=1,2,3,.n),且第i个 叶子结点的路径长度为li ,则使 WPL=wi*li最小的二叉树树称为为“最优优 二叉树树”或称为为“哈夫曼树树”。 i=1 n 2.哈夫曼树的求解过程 二、哈夫曼树及其应用 问题： 已知n个叶子的权值为w1,w2,.wn，构 造一棵最优二叉树。 2.哈夫曼树的求解过程 二、哈夫曼树及其应用 方法： 步骤1:构造一个具有n棵二叉树的森林 F=T1,T2,Tn，其中Ti是只有一个根结点且根结 点的权值为wi的二叉树。 步骤2:在F中选取两棵其根结点的权值最小的二叉树，从 F中删除这两棵树，并以这两棵二叉树为左右子树构造一 棵新的二叉树添加到F中，该新的二叉树的根结点的权值 为其左右孩子二叉树的根结点的权值之和。 步骤3:判断F中是否只有唯一的一棵二叉树。若是，则求 解过程结束；否则，转步骤2。 2.哈夫曼树的求解过程 二、哈夫曼树及其应用 实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。 a40b30c5d10e15 15 2.哈夫曼树的求解过程 二、哈夫曼树及其应用 实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。 a40b30c5d10e15 15 2.哈夫曼树的求解过程 二、哈夫曼树及其应用 实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。 a40b30 c5d10 e1515 30 2.哈夫曼树的求解过程 二、哈夫曼树及其应用 实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。 a 40 b30 c5d10 e1515 30 60 2.哈夫曼树的求解过程 二、哈夫曼树及其应用 a40 b30 c5d10 e1515 30 60 100 3.哈夫曼编码 二、哈夫曼树及其应用 等长编码： 以英文字符编码为例，一般英文字符编码是采 用7位二进制数编码（ASCII码）。7位二进制数 可以为27个不同的英文字符编码。 下面为讨论问题简单起见，假设被编码的字符 集中只有4个（即22个）不同字符，故只要两位二 进制数即可完成编码。 设这4个不同的字符为A，B，C，D，则可进 行等长编码如下： 3.哈夫曼编码 二、哈夫曼树及其应用 等长编码： 设这4个不同的字符为A，B，C，D，则可进 行等长编码如下： 3.哈夫曼编码 二、哈夫曼树及其应用 等长编码： 设这4个不同的字符为A，B，C，D，则可进 行等长编码如下： A: 00 B: 01 C: 10 D: 11 则对于电文“ABACCDA”的二进制电码为： 00010010101100 总长为14位 译码时，两位一分进行译码，可唯一得到电文 ：ABACCDA 。 3.哈夫曼编码 二、哈夫曼树及其应用 压缩编码： 例如：对于刚才的4个字符的编码问题，可以按如 下不等长编码方案进行编码： A: 0 B: 00 C: 1 D: 01 问题：译码时可能出现多意性，即译码不唯一。 则对于电文“ABACCDA”的二进制电码为： 000011010 总长为9位 如000011010中的前4个0的译码会有如下几 种不同译码： 0000AAAA；0000ABA； 0000BB 思考：如何解 决这一问题？ 问题的关键在于编码 是否为无前缀编码。 3.哈夫曼编码 二、哈夫曼树及其应用 无前缀压缩编码（既哈夫曼编码）： *思想：利用哈夫曼树设计出来的不等长的编码方 案一定是无前缀的。 *方法： 步骤1：将各字符按照其“出现频率”的统计数字安排一 个“权值”并作为“叶子”，并求出相应的哈夫曼树； 步骤2：树中各结点到其左孩子的边上的权值设为0、到 其右孩子的边上的权值设为1（即所谓左0右1）； 步骤3：从根开始到“叶子”所经历的边上的数值的序列 即为该“叶子”所对应的字符的编码。 三、实例 已知某通信用电文仅由A、B、C、D这4个字符构成， 其出现的频率分别为：8、4、6、2，请给出它们的哈夫 曼编码，要求写出相应的哈夫曼树。 解：根据哈夫曼算法，求得哈夫曼树如下： 20 812 2 66 4 B D A C 0 1 01 01 从根开始到叶子得各字 符的哈夫曼编码如下： A :0 B:100 C:11 D:101 则对于电文“ABACCDA”的 二进制电码为： 0100011111010 总长为13位 四、小结: 4.哈夫曼树的应用：哈夫曼编码的设计问题。 2.哈夫曼树的定义： WPL=wi*li最小的二叉树树称为为“最优优二叉树树”或称 为为“哈夫曼树树”。 3.哈夫曼树求解的算法思想：3个步骤。 1.哈夫曼树的引入：程序优化问题。 i=1 n n o 哈夫曼树的性质 n 哈夫曼树中没有度为1的结点 n 一棵有N个叶子的哈夫曼树中有2N-1个结点 n 给定权值的哈夫曼树不唯一 n 权值越大的节点离根节点越近 作业: 1.假设用于通信的电文仅由6个字母 A,B,C,D,E,F 组成,这6个字母在电文中出现的频率高低依次为： 3,4,5,8,9,4,试为这6个字母设计哈夫曼编码。 2.证明:若哈夫曼树中有n个叶子结点,则该哈夫曼树 中共有2n-1个结点。（提示：哈夫曼树中无度数为 1的结点 ） 线索二叉树 o 当以二叉链表作为存储结构时，只能找到结 点的左，右孩子的信息，而不能直接得到结 点在任一序列中的前驱和后继信息。 o 如果增加前驱和后继指针，降低存储效率 o 因为在有n个结点的二杈链表中必定存在 n+1个空链域，故可以利用这些空链域来 存放结点的前驱和后继信息。 结构 o leftThread=0 时 left指向左儿子； o leftThread=1 时 left指向前驱； o rightThread=0 时 right指向左子女； o rightThread=1 时 right指向后继； leftleftThreadelementrightThreadright 注意： o 一是何种“序”的线索化，是先序、中序还是 后序； o 二是要“前驱”线索化、“后继”线索化还是“ 全”线索化（前驱后继都要）； o 三是只有空指针处才能加线索。 二叉搜索树 o二叉搜索树又称为二叉排序树，其定义 是一个递归过程： n 它或者是一棵空树；或者是具有下列性质 定义的二叉树： o 若左子树不空，则左子树上所有结 点的值均小于根结点的值；若右子树不 空，则右子树上所有结点的值均大于或 等于根结点的值。 n 左右子树都分别是一棵二叉搜索树 。 o 中序遍历二叉搜索树可以得到解决一个按关 键字有序的序列。 o 构造二叉搜索树的目的不是为了排序，而是 用来加速查找。 o 二叉搜索树的建立： n 由空集为初始状态，将结点按关键字依次插入 到二叉树中去。先将第一个结点作为二叉树的 根结点，插入其它结点时，若结点的值小于根 结点的值，则插入左子树，否则插入右子树， 该过程依次进行，直到整个过程结束。 n 动态生成二叉排树时，树的形状、高度不仅依 赖于记录关键字的大小，还与记录输入的先后 顺序有关 70，35，85，20，70，90 70 35 85 20 7090 20 ，35， 70 ， 70 ， 85 ，90 20 35 70 70 85 90 o查找结点 n 根据前面的定义可知，二叉搜索树的查 找是一个递归的过程，具体如下： o 若二叉排序树为空，则查找失败， 输出相关信息。 o 若二叉查找树不为空，将给定值x 与查找树的根结点关键字进行比较。 o 若比较结果为相等，则查找成功， 整个查找结束。 n 否则，完成下面的判断： o (i) 若给定的值x小于根结点关键 字的值，查找将按照递归的方式在左 子树上进行。 o (ii)若给定的值x大于根结