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

《数据结构算法之树的应用.ppt》由会员分享，可在线阅读，更多相关《数据结构算法之树的应用.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、树的应用树的应用二叉树遍历的应用二叉树遍历的应用o1.查找数据元素查找数据元素o2.求二叉树的高度求二叉树的高度o3.求叶子结点数求叶子结点数 设有设有100100个学生某门课程的考试成绩的分布如下表个学生某门课程的考试成绩的分布如下表所示：所示：一、问题的提出一、问题的提出(判断树判断树)分数05960697079 808990100学生比例数0.050.150.400.300.10学生成绩数据分布情况表学生成绩数据分布情况表*问题：问题：现在要编写程序依次根据每个学生的成绩现在要编写程序依次根据每个学生的成绩打印出该学生的成绩等级。打印出该学生的成绩等级。分数05960697079 808

2、990100学生比例数0.050.150.400.300.10学生成绩数据分布情况表学生成绩数据分布情况表方法方法1：a60打印打印badyesa70no打印打印passyesa80no打印打印generalyesa90no打印打印goodyes打印打印excellentno5%的的学生学生15%的的学生学生40%的的学生学生30%的的学生学生10%的的学生学生共做共做315次比次比较较读取一个学生成绩读取一个学生成绩a循环一百次循环一百次分数05960697079 808990100学生比例数0.050.150.400.300.10学生成绩数据分布情况表学生成绩数据分布情况表方法方法2：a8

3、0打印打印badyesa90noyesnoa70yesnoa60yesno打印打印“good打印打印excellent打印打印pass打印打印general5%的的学生学生15%的的学生学生40%的的学生学生30%的的学生学生10%的的学生学生共做共做220次次比较比较读取一个学生成绩读取一个学生成绩a循环一百次循环一百次思考：思考：如何找到一棵如何找到一棵最优的最优的判断树使得编写判断树使得编写出来的程序的运行时间是最高效的？出来的程序的运行时间是最高效的？1.1.哈夫曼树的哈夫曼树的有关概念有关概念 结点的路径长度：结点的路径长度：从根结点沿某条路径到某结点途中所经历的边的条数从根结点沿某

4、条路径到某结点途中所经历的边的条数称为该结点的路径长度。称为该结点的路径长度。二、哈夫曼树及其应用二、哈夫曼树及其应用 树的路径长度：树的路径长度：从根结点到每一个从根结点到每一个叶子结点叶子结点的路径长度之和。的路径长度之和。树的带权路径长度树的带权路径长度(WPL)：树中所有树中所有叶子结点叶子结点的的带权路径长度带权路径长度之和称为树的带权之和称为树的带权路径长度。路径长度。结点的带权路径长度：结点的带权路径长度：某结点的路径长度与该结点上的权值的乘积称为该结某结点的路径长度与该结点上的权值的乘积称为该结点的带权路径长度。点的带权路径长度。1.1.哈夫曼树的哈夫曼树的有关概念有关概念 二

5、、哈夫曼树及其应用二、哈夫曼树及其应用实例实例：已知某二叉树的四个叶子结点已知某二叉树的四个叶子结点 a,b,c,d分别带权分别带权7，5，2，4，则可构造出有如下几，则可构造出有如下几种不同形式的二叉树：种不同形式的二叉树：aaa777b5b5c2d4c2d4b5c2d 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哈夫曼树的定义：哈夫曼树的定义：二、哈夫曼树及其应用二、哈夫曼树及其应用

6、 设有设有n个叶子结点的二叉树，其第个叶子结点的二叉树，其第i个个叶子结点的权值为叶子结点的权值为wi(i=1,2,3,.n),且第且第i个个叶子结点的路径长度为叶子结点的路径长度为li,则使则使WPL=wi*li最小的二叉最小的二叉树树称称为为“最最优优二叉二叉树树”或称或称为为“哈夫曼哈夫曼树树”。i=1n2.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用问题：问题：已知已知n个叶子的权值为个叶子的权值为w1,w2,.wn，构，构造一棵最优二叉树。造一棵最优二叉树。2.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用方法

7、：方法：步骤步骤1:构造一个具有构造一个具有n棵二叉树的森林棵二叉树的森林F=T1,T2,.,Tn，其中，其中Ti是只有一个根结点且根结是只有一个根结点且根结点的权值为点的权值为wi的二叉树。的二叉树。步骤步骤2:在在F中选取两棵其根结点的权值最小的二叉树，从中选取两棵其根结点的权值最小的二叉树，从F中删除这两棵树，并以这两棵二叉树为左右子树构造一中删除这两棵树，并以这两棵二叉树为左右子树构造一棵新的二叉树添加到棵新的二叉树添加到F中，该新的二叉树的根结点的权值中，该新的二叉树的根结点的权值为其左右孩子二叉树的根结点的权值之和。为其左右孩子二叉树的根结点的权值之和。步骤步骤3:判断判断F中是否

8、只有唯一的一棵二叉树。若是，则求中是否只有唯一的一棵二叉树。若是，则求解过程结束；否则，转步骤解过程结束；否则，转步骤2。2.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有实例：已知有5个叶子结点的权值分别为：个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。；试画出一棵相应的哈夫曼树。a40b30c5d10e15152.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有实例：已知有5个叶子结点的权值分别为：个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的

9、哈夫曼树。；试画出一棵相应的哈夫曼树。a40b30c5d10e15152.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有实例：已知有5个叶子结点的权值分别为：个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。；试画出一棵相应的哈夫曼树。a40b30c5d10e1515302.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有实例：已知有5个叶子结点的权值分别为：个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。；试画出一棵相应的哈夫曼树。a40b3

10、0c5d10e151530602.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用a40b30c5d10e151530601003.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用等长等长编码：编码：以英文字符编码为例，一般英文字符编码是采以英文字符编码为例，一般英文字符编码是采用用7位二进制数编码（位二进制数编码（ASCII码）。码）。7位二进制数位二进制数可以为可以为27个不同的英文字符编码。个不同的英文字符编码。下面为讨论问题简单起见，假设被编码的字符下面为讨论问题简单起见，假设被编码的字符集中只有集中只有4个（即个（即22个）不同字符

11、，故只要两位二个）不同字符，故只要两位二进制数即可完成编码。进制数即可完成编码。设这设这4个不同的字符为个不同的字符为A，B，C，D，则可进，则可进行等长编码如下：行等长编码如下：3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用等长等长编码：编码：设这设这4个不同的字符为个不同的字符为A，B，C，D，则可进，则可进行等长编码如下：行等长编码如下：3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用等长等长编码：编码：设这设这4个不同的字符为个不同的字符为A，B，C，D，则可进，则可进行等长编码如下：行等长编码如下：A:00 B:01 C:10 D:11

12、则对于电文则对于电文“ABACCDA”的二进制电码为：的二进制电码为：00010010101100 总长为总长为14位位 译码时，两位一分进行译码，可唯一得到电文：译码时，两位一分进行译码，可唯一得到电文：ABACCDA 。3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用压缩编码：压缩编码：例如：例如：对于刚才的对于刚才的4个字符的编码问题，可以按如个字符的编码问题，可以按如下不等长编码方案进行编码：下不等长编码方案进行编码：A:0 B:00 C:1 D:01问题：问题：译码时可能出现多意性，即译码不唯一。译码时可能出现多意性，即译码不唯一。则对于电文则对于电文“ABAC

13、CDA”的二进制电码为：的二进制电码为：000011010 总长为总长为9位位 如如000011010中的前中的前4个个0的译码会有如下几的译码会有如下几种不同译码：种不同译码：0000AAAA；0000ABA；0000BB思考：如何解思考：如何解决这一问题？决这一问题？问题的关键在于编码问题的关键在于编码是否为是否为无前缀编码无前缀编码。3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用无前缀无前缀压缩编码（既哈夫曼编码）：压缩编码（既哈夫曼编码）：*思想思想：利用哈夫曼树设计出来的不等长的编码方：利用哈夫曼树设计出来的不等长的编码方案一定是无前缀的。案一定是无前缀的。*

14、方法方法：步骤步骤1：将各字符按照其：将各字符按照其“出现频率出现频率”的统计数字安排的统计数字安排一个一个“权值权值”并作为并作为“叶子叶子”，并求出相应的哈夫曼树；，并求出相应的哈夫曼树；步骤步骤2：树中各结点到其左孩子的边上的权值设为：树中各结点到其左孩子的边上的权值设为0、到、到其右孩子的边上的权值设为其右孩子的边上的权值设为1（即所谓左（即所谓左0右右1）；）；步骤步骤3：从根开始到：从根开始到“叶子叶子”所经历的边上的数值的序所经历的边上的数值的序列即为该列即为该“叶子叶子”所对应的字符的编码。所对应的字符的编码。三、实例三、实例 已知某通信用电文仅由已知某通信用电文仅由A、B、C

15、、D这这4个字符构成，个字符构成，其出现的频率分别为：其出现的频率分别为：8、4、6、2，请给出它们的哈夫，请给出它们的哈夫曼编码，要求写出相应的哈夫曼树。曼编码，要求写出相应的哈夫曼树。解解：根据哈夫曼算法，求得哈夫曼树如下：根据哈夫曼算法，求得哈夫曼树如下：208122664BDAC010101 从根开始到叶子得各字从根开始到叶子得各字符的哈夫曼编码如下：符的哈夫曼编码如下：A:0 B:100 C:11 D:101 则对于电文则对于电文“ABACCDA”的二的二进制电码为：进制电码为：0100011111010 总长为总长为13位位四、小结四、小结:4.4.哈夫曼哈夫曼树的应用：哈夫曼编码

16、的设计问题。树的应用：哈夫曼编码的设计问题。2.2.哈夫曼哈夫曼树的定义：树的定义：WPL=wi*li最小的二叉最小的二叉树树称称为为“最最优优二叉二叉树树”或称或称为为“哈夫曼哈夫曼树树”。3.3.哈夫曼哈夫曼树求解的算法思想：树求解的算法思想：3个步骤。个步骤。1.1.哈夫曼哈夫曼树的引入：程序优化问题。树的引入：程序优化问题。i=1nno哈夫曼树的性质哈夫曼树的性质n哈夫曼树中哈夫曼树中没有没有度为度为1的结点的结点n一棵有一棵有N个叶子的哈夫曼树中有个叶子的哈夫曼树中有2N-1个结点个结点n给定权值的哈夫曼树给定权值的哈夫曼树不唯一不唯一n权值越权值越大大的节点离根节点越的节点离根节点

17、越近近 作业作业:1.假设用于通信的电文仅由假设用于通信的电文仅由6个字母个字母 A,B,C,D,E,F组成组成,这这6个字母在电文中出现的频率高低依次为：个字母在电文中出现的频率高低依次为：3,4,5,8,9,4,试为这试为这6个字母设计哈夫曼编码。个字母设计哈夫曼编码。2.证明证明:若哈夫曼树中有若哈夫曼树中有n个叶子结点个叶子结点,则该哈夫曼树则该哈夫曼树中共有中共有2n-1个结点。（提示：哈夫曼树中无度数为个结点。（提示：哈夫曼树中无度数为1的结点的结点）线索二叉树o当以二叉链表作为存储结构时，只能找到结当以二叉链表作为存储结构时，只能找到结点的左，右孩子的信息，而不能直接得到结点的左

18、，右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息。点在任一序列中的前驱和后继信息。o如果增加前驱和后继指针，降低存储效率如果增加前驱和后继指针，降低存储效率o因为在有因为在有n个结点的二杈链表中必定存在个结点的二杈链表中必定存在n+1个空链域，故可以利用这些空链域来存个空链域，故可以利用这些空链域来存放结点的前驱和后继信息。放结点的前驱和后继信息。结构oleftThread=0 时时 left指向左指向左儿子儿子；oleftThread=1 时时 left指向前驱；指向前驱；orightThread=0 时时 right指向左子女；指向左子女；orightThread=1 时时

19、right指向后继；指向后继；leftleftThreadelementrightThreadright注意：o一是何种一是何种“序序”的线索化，是先序、中序还是的线索化，是先序、中序还是后序；后序；o二是要二是要“前驱前驱”线索化、线索化、“后继后继”线索化还是线索化还是“全全”线索化（前驱后继都要）；线索化（前驱后继都要）；o三是只有空指针处才能加线索。三是只有空指针处才能加线索。二叉搜索树二叉搜索树 o二叉二叉搜索搜索树又称为二叉排序树，其定义树又称为二叉排序树，其定义是一个递归过程：是一个递归过程：n它或者是一棵空树；或者是具有下列性质它或者是一棵空树；或者是具有下列性质定义的二叉树：

20、定义的二叉树：o 若左子树不空，则左子树上所有结若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于或空，则右子树上所有结点的值均大于或等于根结点的值。等于根结点的值。n 左右子树都分别是一棵二叉左右子树都分别是一棵二叉搜索搜索树树 。o中序中序遍历二叉搜索树可以得到解决一个按关遍历二叉搜索树可以得到解决一个按关键字有序的序列。键字有序的序列。o构造二叉搜索树的目的不是为了排序，而是构造二叉搜索树的目的不是为了排序，而是用来加速查找。用来加速查找。o二叉二叉搜索搜索树的建立：树的建立：n由由空空集集为为初初始始状状态

21、态，将将结结点点按按关关键键字字依依次次插插入入到到二二叉叉树树中中去去。先先将将第第一一个个结结点点作作为为二二叉叉树树的的根根结结点点，插插入入其其它它结结点点时时，若若结结点点的的值值小小于于根根结结点点的的值值，则则插插入入左左子子树树，否否则则插插入入右右子子树树，该过程依次进行，直到整个过程结束。该过程依次进行，直到整个过程结束。n动动态态生生成成二二叉叉排排树树时时，树树的的形形状状、高高度度不不仅仅依依赖赖于于记记录录关关键键字字的的大大小小，还还与与记记录录输输入入的的先先后后顺序顺序有关有关70，35，85，20，70，9070358520709020，35，70，70，8

22、5，90203570708590o查找结点查找结点n根据前面的定义可知，二叉根据前面的定义可知，二叉搜索搜索树的查树的查找是一个递归的过程，具体如下：找是一个递归的过程，具体如下：o 若二叉排序树为空，则查找失败，若二叉排序树为空，则查找失败，输出相关信息。输出相关信息。o 若二叉查找树不为空，将给定值若二叉查找树不为空，将给定值x与查找树的根结点关键字进行比较。与查找树的根结点关键字进行比较。o 若比较结果为相等，则查找成功，若比较结果为相等，则查找成功，整个查找结束。整个查找结束。n否则，完成下面的判断：否则，完成下面的判断：o (i)若给定的值若给定的值x小于根结点关键小于根结点关键字的

23、值，查找将按照递归的方式在左字的值，查找将按照递归的方式在左子树上进行。子树上进行。o (ii)若给定的值若给定的值x大于根结点关键大于根结点关键字的值，查找将按照递归的方式在右字的值，查找将按照递归的方式在右子树上进行。子树上进行。o(iii)重复以上过程，直到查找结束重复以上过程，直到查找结束（成功或者失败）。（成功或者失败）。50308020908540358832查找关键字查找关键字50505030403550508090=50,35,90,95查找失败查找失败o算法分析：算法分析：n对于深度为对于深度为d d的二叉搜索树，若设第的二叉搜索树，若设第i i层有层有n ni i个结点，个结点，则在等查找概率情况下，其平均查找长度为：则在等查找概率情况下，其平均查找长度为：ASL=最好情况下，最好情况下，O（log2n）最坏情况下，最坏情况下，O（n）ASL