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