数据结构 树与二叉树精.ppt

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

1、数据结构 树与二叉树第1页，本讲稿共24页7.7二叉排序树(1)若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1定义：定义：二叉排序树二叉排序树(二叉搜索树二叉搜索树或或二叉查找树二叉查找树)或者是一棵空树；或者是具有如下特性的二叉树或者是一棵空树；或者是具有如下特性的二叉树(3)它的左、右子树也都分别是二叉排序树。(2)若它的右子树不空，则右子树上所有结点 的值均大于等于根结点的值；第2页，本讲稿共24页7.7二叉排序树503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不不对对二叉排序树进行中序遍历，得到一个有序序列二叉排序树进行中序遍历，

2、得到一个有序序列第3页，本讲稿共24页7.7二叉排序树452412145390中序遍历中序遍历:12,14,24,45,53,90二叉排序树的构造二叉排序树的构造特点：树结构在查找的过程中动态生成。特点：树结构在查找的过程中动态生成。每次插入的结点只能成为新的每次插入的结点只能成为新的叶子结点叶子结点例：关键字序列为 45，24，53，12，14，90 第4页，本讲稿共24页7.7二叉排序树二叉排序树构造二叉排序树构造递归算法与非递归算法递归算法与非递归算法p142第5页，本讲稿共24页7.7二叉排序树二叉排序删除节点二叉排序删除节点（1）若被删除节点为叶结点，则可以直接删除（2）若被删除结点

3、没有左子树，则可以用其右子树的跟结点取代被删除结点的位置（3）若被删除结点没有右子树，则可以用其左子树的跟结点取代被删除结点的位置（4）若被删除结点的左、右子树均存在，则要找到右子树中值最小的结点（r），用该节点取代被删除节点的位置。由于由r指出的节点的位置一定没有左子树，所以用其右孩子来取代r所指节点的位置。第6页，本讲稿共24页7.7二叉排序树二叉排序删除节点二叉排序删除节点（1）若被删除节点为叶结点，则可以直接删除（2）若被删除结点没有左子树，则可以用其右子树的跟结点取代被删除结点的位置（3）若被删除结点没有右子树，则可以用其左子树的跟结点取代被删除结点的位置（4）若被删除结点的左、右子

4、树均存在，则要找到右子树中值最小的结点（r），用该节点取代被删除节点的位置。由于由r指出的节点的位置一定没有左子树，所以用其右孩子来取代r所指节点的位置。第7页，本讲稿共24页7.7二叉排序树1）若给定值）若给定值等于等于根结点的关键字，则查找成功；根结点的关键字，则查找成功；2）若给定值）若给定值小于小于根结点的关键字，则继续在左子树上进行查根结点的关键字，则继续在左子树上进行查找；找；3）若给定值）若给定值大于大于根结点的关键字，则继续在右子树上进行查找。根结点的关键字，则继续在右子树上进行查找。否则否则二叉排序树的查找二叉排序树的查找查找算法查找算法若二叉排序树若二叉排序树为空为空，则查

5、找不成功；，则查找不成功；第8页，本讲稿共24页7.7二叉排序树平均查找长度平均查找长度：确定一个元素在树中的位置所需进行的比较次数：确定一个元素在树中的位置所需进行的比较次数节点内路径长度节点内路径长度（IPL）：从二叉树根节点到某节点所经过）：从二叉树根节点到某节点所经过的分枝数，定义为该节点的内经长度的分枝数，定义为该节点的内经长度二叉树内路径长度二叉树内路径长度：外路径长度（外路径长度（XPL）：）：外边结点外边结点内部结点内部结点EPL：二叉树中所有外边结点的路径之和二叉树中所有外边结点的路径之和二叉排序树的查找二叉排序树的查找查找长度查找长度第9页，本讲稿共24页7.7二叉排序树查

6、找成功的平均查找长度查找成功的平均查找长度ASL=（IPL+n)/n查找失败的平均查找长度查找失败的平均查找长度ASL=EPL/n=(IPL+2n)/n平均查找长度平均查找长度ASL=(IPL+n+EPL)/(n+n+1)=(2IPL+3n)/2n+1二叉排序树的查找二叉排序树的查找查找长度查找长度第10页，本讲稿共24页7.9 哈夫曼树及其应用问题的提出：问题的提出：例：编制一个将百分制转换为五级分制的程序。例：编制一个将百分制转换为五级分制的程序。例：编制一个将百分制转换为五级分制的程序。例：编制一个将百分制转换为五级分制的程序。如：如：如：如：if(a60)b=”bad”;if(a60)

7、b=”bad”;else if(a70)b=”pass”else if(a70)b=”pass”else if(a80)b=”general”else if(a80)b=”general”else if(a90)b=”good”else if(a90)b=”good”else b=”excellent”;else b=”excellent”;第11页，本讲稿共24页7.9 哈夫曼树及其应用显显显显然然然然，此此此此程程程程序序序序很很很很简简简简单单单单，只只只只要要要要利利利利用用用用条条条条件件件件语语语语句句句句便便便便可可可可完完完完成成成成。如如如如果果果果上上上上述述述述程程程程序

8、序序序需需需需反反反反复复复复使使使使用用用用，而而而而且且且且每每每每次次次次的的的的输输输输入入入入量量量量很很很很大大大大，则则则则应应应应考考考考虑虑虑虑上上上上述述述述程程程程序序序序的的的的质质质质量量量量问问问问题题题题，即即即即其其其其操操操操作作作作所所所所需需需需要要要要的的的的时时时时间间间间。因因因因为为为为在在在在实实实实际际际际中中中中，学学学学生生生生的的的的成成成成绩绩绩绩在在在在五五五五个个个个等等等等级上的分布是不均匀的，假设其分布规律如下表所示：级上的分布是不均匀的，假设其分布规律如下表所示：级上的分布是不均匀的，假设其分布规律如下表所示：级上的分布是不均

9、匀的，假设其分布规律如下表所示：分数分数分数分数 0 059 6059 6069 7069 7079 8079 8089 9089 90100100比例数比例数比例数比例数 0.05 0.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.10则则则则80%80%以上的数据需进行三次或三次以上的比较才能得出结果。以上的数据需进行三次或三次以上的比较才能得出结果。以上的数据需进行三次或三次以上的比较才能得出结果。以上的数据需进行三次或三次以上的比较才能得出结果。第12页，本讲稿共24页7.9 哈夫曼树及其应用叶子结点的权值叶子结点的权值：对叶子结点赋予的一：对叶子结点赋

10、予的一个有意义的数值量。个有意义的数值量。二叉树的带权路径长度二叉树的带权路径长度：设二叉树具有：设二叉树具有n个带权值的叶子结点，从根结点到各个个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权叶子结点的路径长度与相应叶子结点权值的乘积之和。值的乘积之和。记为：记为：WPLWPL=n nk kk kk klw1 1第第第第k k个叶子的权值；个叶子的权值；个叶子的权值；个叶子的权值；从根结点到第从根结点到第从根结点到第从根结点到第k k个叶子的路径长度个叶子的路径长度个叶子的路径长度个叶子的路径长度第13页，本讲稿共24页编码编码：给每一个对象标记一个二进制位：给每一个对象

11、标记一个二进制位串来表示一组对象。例：串来表示一组对象。例：ASCII，指令系，指令系统统等长编码等长编码：表示一组对象的二进制位串：表示一组对象的二进制位串的长度相等。的长度相等。不等长编码不等长编码：表示一组对象的二进制位：表示一组对象的二进制位串的长度不相等。串的长度不相等。不不不不等等等等长长长长编编编编码码码码什什什什么么么么情情情情况况况况下空间效率高？下空间效率高？下空间效率高？下空间效率高？等等等等长长长长编编编编码码码码什什什什么么么么情情情情况况况况下下下下空间效率高？空间效率高？空间效率高？空间效率高？7.9 哈夫曼树及其应用第14页，本讲稿共24页7.9 哈夫曼树及其应

12、用前缀编码：一组编码中任一编码都不是前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀其它任何一个编码的前缀。前缀编码保证了在解码时不会有多种可前缀编码保证了在解码时不会有多种可能。能。第15页，本讲稿共24页7.9 哈夫曼树及其应用哈夫曼树：哈夫曼树：哈夫曼树：哈夫曼树：给定一组具有确定权值的给定一组具有确定权值的给定一组具有确定权值的给定一组具有确定权值的叶子叶子叶子叶子结点，带权路径结点，带权路径结点，带权路径结点，带权路径长度最小长度最小长度最小长度最小的二叉树的二叉树的二叉树的二叉树。例：给定例：给定例：给定例：给定4 4个叶子结点，其权值分别为个叶子结点，其权值分别为个叶子结

13、点，其权值分别为个叶子结点，其权值分别为22，3 3，4 4，77，可以构造出形状不，可以构造出形状不，可以构造出形状不，可以构造出形状不同的同的同的同的多个二叉树。多个二叉树。多个二叉树。多个二叉树。WPL=32 WPL=41 WPL=30WPL=32 WPL=41 WPL=30234723477423第16页，本讲稿共24页7.9 哈夫曼树及其应用 哈夫曼树的特点：哈夫曼树的特点：哈夫曼树的特点：哈夫曼树的特点：1.1.权值越大的叶子结点越靠近根结点，而权值越小的权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。叶子结点越远离根结点。2.2.只有度为只有度为只有度为只有度为

14、0 0（叶子结点）和度为（叶子结点）和度为2（分支结点）的结点，（分支结点）的结点，（分支结点）的结点，（分支结点）的结点，不存在度为不存在度为不存在度为不存在度为1的结点的结点的结点的结点.234723477423第17页，本讲稿共24页7.9 哈夫曼树及其应用第第第第1 1步：初始化步：初始化步：初始化步：初始化W22，3 3，4，55 哈夫曼树的构造过程哈夫曼树的构造过程哈夫曼树的构造过程哈夫曼树的构造过程3524第第第第2 2步：选取与合并步：选取与合并步：选取与合并步：选取与合并32 5第第第第3 3步：删除与加入步：删除与加入步：删除与加入步：删除与加入5432 5第18页，本讲稿

15、共24页7.9 哈夫曼树及其应用WW22，3 3，4 4，5 哈夫曼树的构造过程哈夫曼树的构造过程重复第重复第重复第重复第2 2步步步步5432 554 9重复第重复第重复第重复第3 3步步步步 554 932第19页，本讲稿共24页7.9 哈夫曼树及其应用重复第重复第重复第重复第2 2步步步步重复第重复第重复第重复第3 3步步步步 554 932 554 93214WW2，3 3，4 4，55 哈夫曼树的构造过程哈夫曼树的构造过程哈夫曼树的构造过程哈夫曼树的构造过程第20页，本讲稿共24页7.9 哈夫曼树及其应用例：一组字符例：一组字符A,B,C,D,E,F,G出现出现的频率分别是的频率分别

16、是9,11,5,7,8,2,3，设计，设计最经济的编码方案。最经济的编码方案。第21页，本讲稿共24页7.9 哈夫曼树及其应用9523510191126871545000000111111ABDCEFG编码方案：编码方案：A：00B：10C：010D：110E：111F：0110G：0111第22页，本讲稿共24页7.9 哈夫曼树及其应用 哈夫曼算法的存储结构哈夫曼算法的存储结构哈夫曼算法的存储结构哈夫曼算法的存储结构 设置一个数组（向量）设置一个数组（向量）设置一个数组（向量）设置一个数组（向量）huffTree2n-1huffTree2n-1保存哈夫曼树中各保存哈夫曼树中各保存哈夫曼树中各

17、保存哈夫曼树中各点的信息，数组（向量）元素的结点结构点的信息，数组（向量）元素的结点结构点的信息，数组（向量）元素的结点结构点的信息，数组（向量）元素的结点结构 。weightweight：权值域，保存该结点的权值；：权值域，保存该结点的权值；：权值域，保存该结点的权值；：权值域，保存该结点的权值；lchildlchild：指针域，结点的左孩子结点在数组中的下标；：指针域，结点的左孩子结点在数组中的下标；：指针域，结点的左孩子结点在数组中的下标；：指针域，结点的左孩子结点在数组中的下标；rchildrchild：指针域，结点的右孩子结点在数组中的下标；：指针域，结点的右孩子结点在数组中的下标；

18、：指针域，结点的右孩子结点在数组中的下标；：指针域，结点的右孩子结点在数组中的下标；parentparent：指针域，该结点的双亲结点在数组中的下标。：指针域，该结点的双亲结点在数组中的下标。：指针域，该结点的双亲结点在数组中的下标。：指针域，该结点的双亲结点在数组中的下标。weight lchild rchild parent第23页，本讲稿共24页树树 结结 构构树树 二二 叉叉 树树逻辑结构逻辑结构逻辑结构逻辑结构存储结构存储结构存储结构存储结构树树的的定定义义基基本本术术语语抽抽象象数数据据类类型型双双亲亲表表示示法法孩孩子子表表示示法法孩孩子子兄兄弟弟表表示示法法二二叉叉树树的的定定义义特特殊殊的的二二叉叉树树二二叉叉树树的的性性质质抽抽象象数数据据类类型型顺顺序序存存储储结结构构二二叉叉链链表表斜树斜树满二叉树满二叉树完全二叉树完全二叉树三三叉叉链链表表线线索索链链表表树树的的遍遍历历前序遍历前序遍历后序遍历后序遍历层序遍历层序遍历二二叉叉树树的的遍遍历历前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历遍历操作的遍历操作的实现实现基于遍历的基于遍历的其他算法其他算法相互转换小结小结:第24页，本讲稿共24页