数据结构算法之树的应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,树的应用,二叉树遍历的应用,1.查找数据元素,2.求二叉树的高度,3.求叶子结点数,设有,100,个学生某门课程的考试成绩的分布如下表所示：,一、问题的提出,(,判断树,),分数,059,6069,7079,8089,90100,学生比例数,0.05,0.15,0.40,0.30,0.10,学生成绩数据分布情况表,*,问题：,现在要编写程序依次根据每个学生的成绩打印出该学生的成绩等级。,分数,059,6069,7079,8089,90100,学生比例数,0.05,0.15,0.40,0.30,0.10,学生成绩数据分布情况表,方法,1,：,a60,打印,bad,yes,a70,no,打印,pass,yes,a80,no,打印,general,yes,a90,no,打印,good,yes,打印,excellent,no,5%,的学生,15%,的学生,40%,的学生,30%,的学生,10%,的学生,共做,315,次比较,读取一个学生成绩,a,循环一百次,分数,059,6069,7079,8089,90100,学生比例数,0.05,0.15,0.40,0.30,0.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,个叶子结点的权值为,w,i,(i=1,2,3,.n),且第,i,个叶子结点的路径长度为,l,i,则使,WPL=,w,i,*l,i,最小的二叉树称为“最优,二叉树”或称为“,哈夫曼树,”。,i=1,n,2.,哈夫曼树的,求解过程,二、哈夫曼树及其应用,问题：,已知,n,个叶子的权值为,w,1,w,2,.w,n,，构造一棵最优二叉树。,2.,哈夫曼树的,求解过程,二、哈夫曼树及其应用,方法：,步骤,1:,构造一个具有,n,棵二叉树的森林,F=T,1,T,2,.,T,n,，其中,T,i,是只有一个根结点且根结点的权值为,w,i,的二叉树。,步骤,2:,在,F,中选取两棵其根结点的权值最小的二叉树，从,F,中删除这两棵树，并以这两棵二叉树为左右子树构造一棵新的二叉树添加到,F,中，该新的二叉树的根结点的权值为其左右孩子二叉树的根结点的权值之和。,步骤,3:,判断,F,中是否只有唯一的一棵二叉树。若是，则求解过程结束；否则，转步骤,2,。,2.,哈夫曼树的,求解过程,二、哈夫曼树及其应用,实例：已知有,5,个叶子结点的权值分别为：,5,15,40,30,10,；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,2.,哈夫曼树的,求解过程,二、哈夫曼树及其应用,实例：已知有,5,个叶子结点的权值分别为：,5,15,40,30,10,；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,2.,哈夫曼树的,求解过程,二、哈夫曼树及其应用,实例：已知有,5,个叶子结点的权值分别为：,5,15,40,30,10,；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,30,2.,哈夫曼树的,求解过程,二、哈夫曼树及其应用,实例：已知有,5,个叶子结点的权值分别为：,5,15,40,30,10,；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,30,60,2.,哈夫曼树的,求解过程,二、哈夫曼树及其应用,a,40,b,30,c,5,d,10,e,15,15,30,60,100,3.,哈夫曼编码,二、哈夫曼树及其应用,等长,编码：,以英文字符编码为例，一般英文字符编码是采用,7,位二进制数编码（,ASCII,码）。,7,位二进制数可以为,2,7,个不同的英文字符编码。,下面为讨论问题简单起见，假设被编码的字符集中只有,4,个（即,2,2,个）不同字符，故只要两位二进制数即可完成编码。,设这,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”,的二进制电码为：,总长为,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,8,12,2,6,6,4,B,D,A,C,0,1,0,1,0,1,从根开始到叶子得各字符的哈夫曼编码如下：,A:0 B:100 C:11 D:101,则对于电文“,ABACCDA”,的二进制电码为：,总长为,13,位,四、小结,:,4.,哈夫曼,树的应用：哈夫曼编码的设计问题。,2.,哈夫曼,树的定义：,WPL=,w,i,*l,i,最小的二叉树称为“最优二叉树”或称,为“,哈夫曼树,”。,3.,哈夫曼,树求解的算法思想：,3,个步骤。,1.,哈夫曼,树的引入：程序优化问题。,i=1,n,n,哈夫曼树的性质,哈夫曼树中,没有,度为,1,的结点,一棵有,N,个叶子的哈夫曼树中有,2N-1,个结点,给定权值的哈夫曼树,不唯一,权值越,大,的节点离根节点越,近,作业,:,1.,假设用于通信的电文仅由,6,个字母,A,B,C,D,E,F,组成,这,6,个字母在电文中出现的频率高低依次为：,3,4,5,8,9,4,试为这,6,个字母设计哈夫曼编码。,2.,证明,:,若哈夫曼树中有,n,个叶子结点,则该哈夫曼树中共有,2n-1,个结点。（提示：哈夫曼树中无度数为,1,的结点）,线索二叉树,当以二叉链表作为存储结构时，只能找到结点的左，右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息。,如果增加前驱和后继指针，降低存储效率,因为在有n个结点的二杈链表中必定存在n+1个空链域，故可以利用这些空链域来存放结点的前驱和后继信息。,结构,leftThread=0,时,left,指向左,儿子,；,leftThread=1,时,left,指向前驱；,rightThread=0,时,right,指向左子女；,rightThread=1,时,right,指向后继；,left,leftThread,element,rightThread,right,注意：,一是何种,“,序,”,的线索化，是先序、中序还是后序；,二是要,“,前驱,”,线索化、,“,后继,”,线索化还是,“,全,”,线索化（前驱后继都要）；,三是只有空指针处才能加线索。,二叉搜索树,二叉,搜索,树又称为二叉排序树，其定义是一个递归过程：,它或者是一棵空树；或者是具有下列性质定义的二叉树：,若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于或等于根结点的值。,左右子树都分别是一棵二叉,搜索,树。,中序,遍历二叉搜索树可以得到解决一个按关键字有序的序列。,构造二叉搜索树的目的不是为了排序，而是用来加速查找。,二叉,搜索,树的建立：,由空集为初始状态，将结点按关键字依次插入到二叉树中去。先将第一个结点作为二叉树的根结点，插入其它结点时，若结点的值小于根结点的值，则插入左子树，否则插入右子树，该过程依次进行，直到整个过程结束。,动态生成二叉排树时，树的形状、高度不仅依赖于记录,关键字,的大小，还与记录输入的,先后顺序,有关,70,，,35,，,85,，,20,，,70,，,90,70,35,85,20,70,90,20,，,35,，,70,，,70,，,85,，,90,20,35,70,70,85,90,查找结点,根据前面的定义可知，二叉,搜索,树的查找是一个递归的过程，具体如下：,若二叉排序树为空，则查找失败，输出相关信息。,若二叉查找树不为空，将给定值,x,与查找树的根结点关键字进行比较。,若比较结果为相等，则查找成功，整个查找结束。,否则，完成下面的判断：,(i),若给定的值,x,小于根结点关键字的值，查找将按照递归的方式在左子树上进行。,(ii),若给定的值,x,大于根结点关键字的值，查找将按照递归的方式在右子树上进行。,(iii),重复以上过程，直到查找结束（成功或者失败）。,50,30,80,20,90,85,40,35,88,32,查找关键字,50,50,50,30,40,35,50,50,80,90,=50,35,90,95,查找失败,算法分析：,对于深度为,d,的二叉搜索树，若设第,i,层有,n,i,个结点，则在等查找概率情况下，其平均查找长度为：,ASL=,最好情况下，,O,（,log,2,n,）,最坏情况下，,O,（,n,）,ASL,