数据结构41-树与树的表示课件

1、第五章 树和二叉树第五章 树和二叉树知 识 点树的基本概念二叉树及二叉树的存储结构顺序、链式二叉树的遍历二叉排序树二叉树的应用哈夫曼树二叉树的应用难 点二叉树遍历算法的设计修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题1234567知 识 点1234567要 求 熟练掌握以下内容:理解树型结构的基本概念和术语二叉树定义和存储结构二叉树的遍历次序及二叉树遍历算法树和二叉树之间的相互转换方法线索二叉树的建立及遍历算法树的应用：二叉排序树和哈夫曼树了解以下内容：了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。要 求为什么要有树型结构？ 分层次组织在管理上具有更高的效率! 数据管理

2、的基本操作之一：查找 如何实现有效率的查找？为什么要有树型结构？ 分层次组织在管理上具有更高的效率!查找表：在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表。关键字：查找表中每个记录由多个数据项(属性)组成，若一个或几个属性能够唯一确定一条记录，称这个属性(或属性组合)为关键字。查找：又称为查询或检索，是在查找表中找出关键字值与给定值相同的记录。例如：查找姓名为刘光的记录。查找的基本概念：查找表：在计算机中，被查找的数据对象是由同一类型的记录构成的例如：查找姓名为“李龙”的记录。对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有

3、关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该输出不成功的信息。查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的次数的平均值，作为衡量查找算法效率的标准。关键字例如：查找姓名为“李龙”的记录。对于给定的关键字的值，如果在查找方法评价： 要衡量一种查找算法的优劣，主要是看给定值与关键字的比较次数。将找到给定值所需的与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准。平均查找长度ASL(Average Search Length)：为确定记录在查找表中的位置，需和给定值进行比较

4、的关键字的个数的期望值叫查找算法的平均查找长度。数据结构4逻辑上的一张查找表要存储在存储器中如何进行查找？选择一种查找方法逻辑上的一张查找表要存储在存储器中如何进行查找？选择如何进行查找？(1)查找方法的选择首先取决于查找表的数据结构。表内数据存储方式的不同在很大程度上决定了查找的效率。因此在研究各种查找算法时，首先必须理清每种算法所需要的数据结构，特别是存储结构。(2)还要弄清表中记录的排列顺序，是按关键字有序的还是随机的。静态查找表仅作查询和检索操作的查找表。动态查找表查找同时做插入、删除操作的查找表。查找表可分为两类:选择一种查找方法如何进行查找？(1)查找方法的选择首先取决于查找表的数

5、据结构可以有不同的数据结构，实现的查找方法也不同。最简单：线性表以线性表作为静态查找表，介绍其上的三种查找方法： 顺序查找、二分查找、分块查找7.1.1 顺序查找查找过程：从表的一端开始按顺序逐个进行记录的关键字和给定值的比较。数据结构：线性表 为了讨论方便，以顺序表 作为静态查找表。表类型定义如下：7.1 静态查找表可以有不同的数据结构，实现的查找方法也不同。7.1 静态查找typedef int keytype; /*关键字类型 */typedef struct keytype key; /*关键字域 */ datatype others; /*其他数据项，可根据需要自行定义*/ElemT

6、ype; /*查找表中数据元素(记录)类型 */typedef struct ElemType *elem; /*顺序表基地址，0号单元闲置 */ int length; /*顺序表长度 */stable; /*查找表类型 */typedef int keytype; /*关键字类型 *例： 21 13 5 19 56 37 64 92 75 88 80/*假设从后往前查找，成功返回记录位置，失败返回0。*/int seqsearch1(stable *ST,keytype key) int i; for(i=ST-length; i0& ; i-); return i; 0 1 2 3 4

7、5 6 7 8 9 10 11ST.elemST.lengthST为一静态顺序查找表/*key为要查找的给定值 */*i0，该条件可避免i出界，检测整个表是否搜索完毕 */ST-elemi.key!=key int i; for(i=ST-length; i0; i-) if(ST-elemi.key=key) return i; return 0; /*等价于return i;*/ 查找过程：从表的一端开始依次将记录的关键字和给定值比较。例： 21 13 5 19 56 37 i找64监视哨iiii查找成功，比较次数=5改进的算法：int seqsearch2(stable *ST,keyt

8、ype key) int i; ST-elem0.key=key; for(i=ST-length; ST-elemi.key!=key; i-); return i;找60ii查找失败，比较次数=126460 0 1 2 3 4 5 6 7 8 9 10 11ST.elem例： 21 13 5 19 56 37 64 92 75 88 80/*设置监视哨，避免i出界，同时比较次数减少 */n-(i-1)/* 设置监视哨 */n+1/*假设从后往前查找，成功返回记录位置，失败返回0。*/i找64监视哨iiii查找成功，比较次数=5改进的算法：in监视哨的作用：利用在0号单元所设的“监视哨”控制

9、住了循环变量 i 的出界，同时省去了i是否出界的比较。经验告诉我们，在表长大于1000的情况下，它将使查找算法的时间几乎缩短了一倍。监视哨的作用：(1)查找成功：查找第i个元素比较次数：n-i+1算法性能分析顺序查找方法的ASL(2)查找失败比较次数：n+1适用范围：顺序表和链表，且不要求记录有序。缺点：不适合表内记录较多的情况。(1)查找成功：算法性能分析顺序查找方法的ASL(2)查7.1.2 二分查找二分查找也称为折半查找，它的查找效率较高，但它要求数据在线性表中按查找的关键字域有序排列。一种缩小区间的查找方法，每次将待查记录所在区间缩小一半。方法：首先用待查找的给定值k与表正中间元素的关

10、键值相比较，此元素的下标 。7.1.2 二分查找二分查找也称为折半查找，它的查找效率较高1.适用范围：有序顺序表以升序为例2.查找过程low、high和mid分别指向待查元素所在区间的下界、上界和中点，key为给定值。初始时，令low=1，high=n，mid=(low+high)/2。让key与mid指向的记录比较若key=ST-elemmid.key，查找成功，返回mid；若keyelemmid.key，则high=mid-1；若keyST-elemmid.key，则low=mid+1。在新的查找区间内重复上述操作，直至lowhigh时， 查找失败，返回0。缩小查找区间缩小查找区间1.适用

11、范围：有序顺序表以升序为例缩小查找区间缩小查找区ST.elem例如：key=64 的查找过程如下：lowhighmid mid midlow 指示查找区间的下界high 指示查找区间的上界mid = (low+high)/2highlowST.lengthST.elem例如：key=64 的查找过程如下：lowhi例： 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找70low1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92highmidlow1 2 3

12、 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmidlow high查找失败例： 1 2 3 4 int binsearch(stable *ST,keytype key) int low=1,high=ST-length,mid; while(lowelemmid.key=key)

13、 return mid; if(keyelemmid.key) /*在左半区间查找*/ high=mid-1; else low=mid+1; /*在右半区间查找*/ return 0;结论：每次循环都把查找区间缩小一半，所以二分查找性能只与记录个数n有关，与元素取值无关。int binsearch(stable *ST,keyty3.折半(二分)查找的平均查找长度二分查找的过程描述二分查找判定树二分查找判定树：是一棵二叉树，树的根是查找区间的中间记录在表中的位置(或关键字值)，左半区间构成左子树，右半区间构成右子树，左或右半区间对应的二叉树又是符合前面性质的二分查找判定树。结论：二分查找判定

14、树的形态只与表中记录个数n有关，与表中的元素值无关。3.折半(二分)查找的平均查找长度二分查找的过程描述二分6391425781011例：含有11个记录的二分查找的判定树如下：12233334444 查找成功时走了一条从根结点到所查找记录结点的路径，关键字的比较次数恰好为该记录结点在树中的层次数。查找成功时的比较次数：ASLsuc=(1+2*2+4*3+4*4)/11=3因此，二分查找法在查找成功时进行的关键字的比较次数最多不超过树的深度。而该判定树的形状近似于完全二叉树。6391425781011例：含有11个记录的二分查找的判定一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完

15、全二叉树的深度相同。设表长是n，则树的高度是h log2n 1。设表中每个记录查找概率均等：和树的高度成正比。任意n个记录的折半查找在成功时的ASL：ASLsuc=O(log2n)j是待查记录所在的层次(也是比较次数)，2j-1是j层上最多结点数。O(log2n)求ASL时，将完全二叉树看成满二叉树。一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的查找失败时：补充外部结点6391425781011455611查找失败时走了一条从根结点到某个外部结点的路径，关键字的比较次数恰好为该路径上记录结点的总数。最坏情况下，即查找失败时和关键字的比较次数也不超过判定树的深度，ASLunsuc=

16、O(log2n)。例如：找12 比较次数：4lowhigh时查找失败时：补充外部结点6391425781011455例7.1(P175)：给定13个数据元素的有序顺序表（1, 13, 25, 37, 49, 61, 73, 84, 96, 108 , 110, 125, 130）采用折半查找方法，则：（1）查找给定值为37的元素，将依次与哪些元素比较？（2）查找给定值为82的元素，将依次与哪些元素比较？（3）在等概率情况下，计算查找成功时的平均查找长度。73251081493761138412511013096(1)查找37依次与73，25，49，37比较。(2)查找82依次与73，108，8

17、4比较。ASLsuc113*(1+2*2+3*4+4*6)=3.154(3) 1 2 3 4 5 6 7 8 9 10 11 12 13例7.1(P175)：给定13个数据元素的有序顺序表7325树(tree)是n(n 0)个结点的有限集T。 当n=0时，称为空树； 当n0时，满足如下条件： 1)有且仅有一个特定的结点，称为树的根(root)； 2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵符合本定义的树，称为根root的子树(subtree)。递归定义图 树的定义5.1 树的定义和基本操作 树(tree)是n(n 0)个结点的有限集T。递归定义结点的分类：从不同角度 树的特征：根、分支、叶子结点 计算机角度：终端结点、非终端结点 族谱关系：双亲和孩子（一个结点可以承担两个角色）、祖先和子孙 、兄弟和堂兄弟结点结点表示树中的元素，包括数据项及若干指向其子树的分支(根和子树根之间的连线为“分支”)孩子结点子树的根称为该结点的孩子双亲孩子结点的上层结点叫该结点的双亲兄弟同一双亲的孩子堂兄弟同一层上不同父亲的结点祖先指从根结点到该结点的路径上的所有结点子孙结点一个结点的直接后继和间接后继结点的度与该结点相连接的孩子结点数叶子度为0的结点，又称为终端