1、第第五五章章 树和二叉树树和二叉树 知知 识识 点点树的基本概念树的基本概念二叉树二叉树及二叉树的存储结构及二叉树的存储结构顺序、链顺序、链式式二叉树的二叉树的遍历遍历二叉排序树二叉排序树二叉树的应用二叉树的应用哈夫曼树哈夫曼树二叉树的应用二叉树的应用 难难 点点二叉树遍历算法的设计二叉树遍历算法的设计修改二叉树遍历算法，进行二叉树其它相修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题关的操作，解决实际应用问题1234567 要要 求求 熟练掌握以下内容熟练掌握以下内容:理解理解树型结构树型结构的基本概念和术语的基本概念和术语二叉树二叉树定义和存储结构定义和存储结构二叉树的遍历次
2、序及二叉树遍历算法二叉树的遍历次序及二叉树遍历算法树树和和二叉树二叉树之间的之间的相互转换相互转换方法方法线索二叉树线索二叉树的建立及遍历算法的建立及遍历算法树的树的应用应用：二叉排序树二叉排序树和和哈夫曼树哈夫曼树了解以下内容：了解以下内容：了解了解最优树最优树的特性，掌握的特性，掌握建立最优树建立最优树和和哈哈夫曼编码夫曼编码的方法。的方法。为什么要有树型结构？分层次组织在管理上具有更高的效率!数据管理的基本操作之一：查找 如何实现有效率的查找？在计算机中，被在计算机中，被是由是由构成的集合构成的集合，可称之为，可称之为。查找表中每个查找表中每个由多个由多个组成，若一个或几个属性组成，若一
3、个或几个属性能够唯一确定一条记录，称这个属性能够唯一确定一条记录，称这个属性(或属性组合或属性组合)为关键字。为关键字。又称为又称为或或，是在查找，是在查找表中找出表中找出与与相同的记相同的记录。录。查找姓名为查找姓名为“李龙李龙”的记录。的记录。对于给定的关键字的值，如果在对于给定的关键字的值，如果在表中经过查找能找到相应的记录表中经过查找能找到相应的记录，则称，则称，一般可，一般可该该记录的有关信息或指示该记录在记录的有关信息或指示该记录在查找表中的位置。查找表中的位置。若表中不存在相应的记录，则称若表中不存在相应的记录，则称，此时应该，此时应该不成不成功的信息。功的信息。查找算法中的查找
4、算法中的是记录的是记录的与与所进行的所进行的，其其通常取决于通常取决于。因此，通常以。因此，通常以进行进行，作，作为为的标准。的标准。查找方法评价：查找方法评价：要衡量一种查找算法的优劣，要衡量一种查找算法的优劣，看给定值与看给定值与关键字的比较次数。将找到给定值所需的与关键字的关键字的比较次数。将找到给定值所需的与关键字的来作为衡量一个查找算法好坏的标来作为衡量一个查找算法好坏的标准。准。平均查找长度平均查找长度ASL(Average Search Length)：为确定为确定记录在记录在查找查找表中的位置，需表中的位置，需和和给定值给定值进行比较的进行比较的关键关键字的个数的期望值字的个数
5、的期望值叫查找算法的叫查找算法的平均查找长度。平均查找长度。个元素所需比较次数为找到表中第概率均等，即一般情况下，认为查找个元素的概率，为查找表中第其中：个记录的表，对含有icnppipcpASLniiniiiniii/1,111如何进行查找？如何进行查找？如何进行查找？如何进行查找？(1)首先取决于首先取决于。表内表内的不同在很大程度上决定了的不同在很大程度上决定了。因此在研究因此在研究时，首先必须理清每种算法所需要的时，首先必须理清每种算法所需要的，特别是，特别是。(2)还要弄清表中还要弄清表中，是按关键字，是按关键字的还是的还是的。的。静态查找表静态查找表仅作仅作和和操作的查找表。操作的
6、查找表。动态查找表动态查找表同时做同时做、操作的查找表。操作的查找表。查找表可分为两类查找表可分为两类:q 可以有可以有，实现的，实现的也也。q 最简单：线性表最简单：线性表q 以以作为静态查找表，介绍其上的三种查找方法：作为静态查找表，介绍其上的三种查找方法：顺序查找、二分查找、分块查找顺序查找、二分查找、分块查找7.1.1 顺序查找顺序查找q查找过程：查找过程：从从开始开始逐个进行记逐个进行记录的关键字和给定值的比较。录的关键字和给定值的比较。q数据结构：数据结构：线性表线性表 为了讨论方便，以为了讨论方便，以顺序表顺序表 作为静态查找表。作为静态查找表。q表类型表类型定义如下：定义如下：
7、7.1 静态查找表静态查找表typedef int keytype;/*关键字类型关键字类型*/typedef struct keytype key;/*关键字域关键字域*/datatype others;/*其他数据项，可根据需要自行定义其他数据项，可根据需要自行定义*/ElemType;/*查找表中数据元素查找表中数据元素(记录记录)类型类型*/typedef struct ElemType*elem;/*顺序表基地址，顺序表基地址，0号单元闲置号单元闲置*/int length;/*顺序表长度顺序表长度*/stable;/*查找表类型查找表类型*/例：例：21 13 5 19 56 37
8、 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 5 6 7 8 9 10 11ST.elemST.lengthST为一为一静态顺序查找静态顺序查找表表/*key为要查找的给定值为要查找的给定值*/*i0，该条件可避免，该条件可避免i出界，出界，检测整个表是否搜索完毕检测整个表是否搜索完毕*/ST-elemi.key!=key int i;for(
9、i=ST-length;i0;i-)if(ST-elemi.key=key)return i;return 0;/*等价于等价于return i;*/q查找过程：从查找过程：从开始依次将记录的关键字和给定值比较。开始依次将记录的关键字和给定值比较。i找找64监视哨监视哨iiii查找成功，比较次数查找成功，比较次数=5改进的算法：改进的算法：int seqsearch2(stable*ST,keytype key)int i;ST-elem0.key=key;for(i=ST-length;ST-elemi.key!=key;i-)return i;找找60ii查找失败，比较次数查找失败，比较次
10、数=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出界，同出界，同时比较次数减少时比较次数减少*/*设置监视哨设置监视哨*/*假设假设从后往前从后往前查找，成功返回记录位置，失败返回查找，成功返回记录位置，失败返回0。*/监视哨的作用监视哨的作用：利用在利用在0号单元号单元所设的所设的“监视哨监视哨”控制住了控制住了循环变量循环变量 i 的出界的出界，同时，同时省去了省去了i是否出界的比较是否出界的比较。经验告诉我们，在表长大于经验告诉我们，在表长大于10
11、00的情况下，它将使的情况下，它将使查找算法的时间几乎缩短了一倍。查找算法的时间几乎缩短了一倍。(1)查找查找成功成功：查找第查找第i个元素个元素比较次数：比较次数：n-i+1q算法性能分析算法性能分析顺序查找方法的顺序查找方法的ASL21n2)1n(nn1)1in(n1cpASLn1pn1in1iiisuci 则则概概率率相相等等设设表表中中每每个个元元素素的的查查找找(2)查找查找失败失败比较次数比较次数：n+11 nASLunsucq适用范围：适用范围：顺序表和链表，且不要求记录有序。顺序表和链表，且不要求记录有序。q缺点：缺点：不适合表内记录较多的情况。不适合表内记录较多的情况。7.1
12、.2 二分查找二分查找也称为也称为，它的查找，它的查找，但它要求数据在线性表中，但它要求数据在线性表中。一种一种的查找方法，每次将的查找方法，每次将所所在区间缩小一半。在区间缩小一半。首先用待查找的首先用待查找的与与相比较，此元素的下标相比较，此元素的下标 。2/)1(nm1.有序顺序表有序顺序表以以升序升序为例为例2.low、high和和mid分别指向分别指向待查元素待查元素所在区间的下界所在区间的下界、上界上界和中点和中点，key为给定值为给定值。初始时，令初始时，令low=1，high=n，mid=(low+high)/2。让让key与与mid指向的记录比较指向的记录比较若若key=ST
13、-elemmid.key，返回返回mid；若若keyelemmid.key，则则high=mid-1；若若keyST-elemmid.key，则则low=mid+1。在新的查找区间内重复上述操作，直至在新的查找区间内重复上述操作，直至lowhigh时，时，返回返回0。缩小查找区间缩小查找区间缩小查找区间缩小查找区间05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem例如：例如：key=64 的查找过程如下：lowhighmid mid midlow 指示查找区间的下界high 指示查找区间的上界mid=(low+h
14、igh)/2highlow ST.length例：例：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 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
15、 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmidlow high查找失败查找失败int binsearch(stable*ST,keytype key)int low=1,high=ST-length,mid;while(lowelemmid.key=key)return mid;if(keyelemmid.key)/*在左半区间查找在左半区间查找*/high=mid-1;else low=mid+1;/*在右半区间查找在右半区间查找*/return 0;每次循环都把每次循环都把，所以二分，所以二分查找性能只与查找性能只与有关，与元素取值无
16、关。有关，与元素取值无关。3.折半折半(二分二分)查找的查找的二分查找的过程描述二分查找的过程描述是一棵是一棵，树的根是查找树的根是查找区间的区间的中间记录中间记录在表中的在表中的位置位置(或或关键字值关键字值)，左左半区间半区间构成构成左子树左子树，右半区间右半区间构成构成右子树右子树，左或，左或右半区间对应的二叉树又是符合前面性质的二分右半区间对应的二叉树又是符合前面性质的二分查找判定树。查找判定树。二分查找判定树的形态只与二分查找判定树的形态只与表中记录个数表中记录个数n有关有关，与表中的元素值无关。，与表中的元素值无关。i123456789 10 11Ci6391425781011含有
17、含有11个记录的二分查找的判定树如下：个记录的二分查找的判定树如下：12233334444 走了一条从走了一条从根根结结点到所点到所查找记录查找记录结点的路径，关键字的结点的路径，关键字的恰好恰好为该记录结点在树中的为该记录结点在树中的。查找成功时的比较次数查找成功时的比较次数：ASLsuc=(1+2*2+4*3+4*4)/11=3因此，二分查找法在因此，二分查找法在进行的关键字的进行的关键字的最多不超过树的深度最多不超过树的深度。而该判定树的形状近似于而该判定树的形状近似于完全二叉树完全二叉树。一般情况下，一般情况下，表长为表长为n的折半查找的的折半查找的判定树判定树的的深度深度和含有和含有
18、n个结点的个结点的完全二叉树完全二叉树的的深度深度相同。相同。设表长是设表长是n，则树的高度是，则树的高度是h log2n 1。设表中每个记录查找概率均等：设表中每个记录查找概率均等：和树的高度成正比。和树的高度成正比。任意任意n个记录的折半查找在个记录的折半查找在成功时成功时的的ASL：ASLsuc=O(log2n)O O(l lo og gn n)1 11 1)(n nl lo og g1 11 1)(n nl lo og gn n1 1n n2 2j jn n1 1c cn n1 1c cp p则则：A AS SL L2 22 2h h1 1j j1 1j jn n1 1i ii in
19、n1 1i ii ii is su uc cj是待查记录所是待查记录所在的层次在的层次(也是也是比较次数比较次数)，2j-1是是j层上最多结层上最多结点数。点数。O(log2n)求求ASL时，将完全二叉树看成时，将完全二叉树看成满二叉树满二叉树。补充外部结点补充外部结点6391425781011455611查找失败时查找失败时走了一条从走了一条从根结点根结点到到某个外部结点某个外部结点的路径，的路径，关键字的关键字的比较次数比较次数恰好为该路径上恰好为该路径上记录结点的总数记录结点的总数。最坏情况下，即最坏情况下，即和关键字的比较次数也和关键字的比较次数也不不超过判定树的深度超过判定树的深度，
20、ASLunsuc=O(log2n)。lowhigh时时给定给定13个数据元素的个数据元素的有序顺序表有序顺序表（1,13,25,37,49,61,73,84,96,108,110,125,130）采用采用折半查找折半查找方法，则：方法，则：（1）查找给定值为）查找给定值为37的元素，将依次与哪些元素比较？的元素，将依次与哪些元素比较？（2）查找给定值为）查找给定值为82的元素，将依次与哪些元素比较？的元素，将依次与哪些元素比较？（3）在等概率情况下，计算）在等概率情况下，计算查找成功时查找成功时的的平均查找长度平均查找长度。73251081493761138412511013096(1)查找查
21、找37依次与依次与73，25，49，37比较。比较。(2)查找查找82依次与依次与73，108，84比较。比较。ASLsuc113*(1+2*2+3*4+4*6)=3.154(3)1 2 3 4 5 6 7 8 9 10 11 12 13树树(tree)是是n(n 0)个结点的有限集个结点的有限集T。当当n=0时，称为时，称为空树空树；当当n0时，满足如下条件时，满足如下条件：1)有且仅有有且仅有一个特定的结点，称为树的一个特定的结点，称为树的根根(root)；2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交互不相交的有限集的有限集T1,T2,Tm，其中每一个集合本身又是
22、一棵其中每一个集合本身又是一棵符合本定义的树符合本定义的树，称为根称为根root的的子树子树(subtree)。递归定义递归定义图图 树的定义树的定义5.1 树的定义和基本操作树的定义和基本操作 结点的分类：从不同角度结点的分类：从不同角度 树的特征：树的特征：根、分支、叶子结点根、分支、叶子结点 计算机角度：计算机角度：终端结点、非终端结点终端结点、非终端结点 族谱关系：族谱关系：双亲和孩子（一个结点可以承担两个角色）、双亲和孩子（一个结点可以承担两个角色）、祖先和子孙祖先和子孙、兄弟和堂兄弟结点、兄弟和堂兄弟结点 结点结点表示表示树中的元素树中的元素，包括包括数据项及若干指向数据项及若干指
23、向其子树的分支其子树的分支(根和子树根之间的连线为根和子树根之间的连线为“分支分支”)孩子孩子结点子树的根称为该结点的孩子结点子树的根称为该结点的孩子 双亲双亲孩子结点的孩子结点的上层结点上层结点叫该结点的双亲叫该结点的双亲 兄弟兄弟同一双亲的孩子同一双亲的孩子 堂兄弟堂兄弟同一层上不同父亲的结点同一层上不同父亲的结点 祖先祖先指从指从根结点根结点到该结点的到该结点的路径路径上的所有结点上的所有结点 子孙结点子孙结点一个结点的一个结点的直接后继直接后继和和间接后继间接后继 结点的度结点的度与该结点相连接的孩子结点数与该结点相连接的孩子结点数 叶子叶子度为度为0的结点，又称为的结点，又称为终端结
24、点终端结点 分支结点分支结点度不为度不为0的结点，也称为的结点，也称为非终端结点非终端结点 基本术语基本术语ABCDEFGHIJKLM度度：分为：分为结点的度结点的度和和树的度树的度。树的度：树的度：树中树中所有结点度的最大值所有结点度的最大值。结点的层次结点的层次(或深度或深度)：从根结点开始到该结点的层次数。从根结点开始到该结点的层次数。树是一种分层结构，从根结点算起，根为第一层，它树是一种分层结构，从根结点算起，根为第一层，它的孩子为第二层的孩子为第二层。树的深度树的深度(或层数或层数)：树中：树中所有结点的层次的最大值所有结点的层次的最大值。树形结构是树形结构是非线性非线性结构。树的形态多种多样，本章我结构。树的形态多种多样，本章我们主要讨论一种们主要讨论一种最常用的树最常用的树二叉树二叉树(拥有其独特拥有其独特的性质和操作的性质和操作)。ABCDEFGHIJKLM树的概念29
