数据结构 第七章 查找.ppt

《数据结构 第七章 查找.ppt》由会员分享，可在线阅读，更多相关《数据结构 第七章 查找.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章查 找1本章要点本章要点n查找的有关概念：查找、查找表、查找方法、查找查找的有关概念：查找、查找表、查找方法、查找分类、关键字、文件、文件系统等；分类、关键字、文件、文件系统等；n顺序表查找、有序表查找、索引表查找顺序表查找、有序表查找、索引表查找(分块查找分块查找)的概念及实现；的概念及实现；n二叉排序树、平衡二叉树、二叉排序树、平衡二叉树、B-B-树与树与B+B+树的概念及实树的概念及实现；现；n哈希表的概念、哈希函数构造、处理冲突方法及查哈希表的概念、哈希函数构造、处理冲突方法及查找性能分析。找性能分析。2查查找找，也也称称检检索索，在在我我们们的的日日常常生生活活中中，是是

2、几几乎乎天天天天都要进行的工作。都要进行的工作。从字典中查找单词从字典中查找单词；从通讯录中查找电话从通讯录中查找电话；从图书馆系统中查找图书从图书馆系统中查找图书；从教务系统中查找课程或成绩从教务系统中查找课程或成绩；从网络中查找资料等从网络中查找资料等有有些些是是人人工工进进行行的的，如如查查字字典典、查查电电话话等等，而而有有些些是是计算机进行的计算机进行的。如何加快查找的速度？如何加快查找的速度？37.1 查找的基本概念查找的基本概念n查找表(Search Table)：指在其中使用查询操作的查找：指在其中使用查询操作的查找对象集合对象集合,一般是由同一类型的数据元素一般是由同一类型的

3、数据元素(或记录或记录)构成。构成。由由于于”集集合合”中中的的数数据据元元素素之之间间存存在在着着完完全全松松散散的的关关系系,因此查找表是一种非常灵便的数据结构。因此查找表是一种非常灵便的数据结构。n查找(Searching)：根根据据给给定定的的条条件件，在在查查找找表表中中确确定定一个或全部满足条件的记录或数据元素。一个或全部满足条件的记录或数据元素。即即：为为在在一一个个含含有有众众多多的的数数据据元元素素(或或记记录录)的的查查找找表表中找出某个中找出某个”特定的特定的”数据元素数据元素(或记录或记录)。n查找结果：查找结果：查找成功:查找不成功:4n对查找表经常进行的操作有对查找

4、表经常进行的操作有:1)1)确认符合条件的确认符合条件的“特定元素特定元素”是否存在；是否存在；2)2)检索某个检索某个“特定元素特定元素”的各种属性或属性修改等；的各种属性或属性修改等；3)3)如果没有在查找表中找到该如果没有在查找表中找到该“特定元素特定元素”,则插入该元素则插入该元素;4)4)从查找表中删去找到的某个从查找表中删去找到的某个“特定元素特定元素”。n若对查找表只作前两种统称为若对查找表只作前两种统称为“查询和检索查询和检索”的操作的操作,不影响原查找表的结构，则称此类查找表为不影响原查找表的结构，则称此类查找表为静态查找表(StaticSearchTable);(Stati

5、cSearchTable);若在查找过程中同时插入查找表中不存在的数据元素若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素或者从查找表中删除已存在的某个数据元素,从而造成了从而造成了查找表因查找而动态变化，则称此类表为查找表因查找而动态变化，则称此类表为动态查找表(Dynamic Search Table)(Dynamic Search Table)。5n关键字(Key):是数据元素是数据元素(或记录或记录)中某个数据项的值中某个数据项的值,用它可以标识用它可以标识(识别识别)一个数据元素一个数据元素(或记录或记录)。主关键字(Primary Key):次

6、关键字(Secondary Key):n查找方法查找方法:查找操作的方法与查找表的存储结构有关查找操作的方法与查找表的存储结构有关。为了提高查为了提高查找的效率，需要在查找表中的元素之间人为地附加某种找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，即用另外一种结构来表示查找表。确定的关系，即用另外一种结构来表示查找表。比如，查阅电话号码簿或查字典。比如，查阅电话号码簿或查字典。6n查找算法的时间复杂度查找算法的时间复杂度：基本操作执行次数的量：基本操作执行次数的量级来衡量。级来衡量。给定值与关键字进行比较给定值与关键字进行比较 n平均查找长度平均查找长度(Average Searc

7、h Length，ASL)：将：将给定值与查找表中关键字进行比较的记录个数的平给定值与查找表中关键字进行比较的记录个数的平均值作为衡量查找算法好坏的依据。均值作为衡量查找算法好坏的依据。由于查找的结果有成功和不成功两种：由于查找的结果有成功和不成功两种：查找成功的平均查找长度：查找成功的平均查找长度：查找不成功的平均查找长度：查找不成功的平均查找长度：查找过程中使用辅助空间的多少，就是相应算法查找过程中使用辅助空间的多少，就是相应算法的空间复杂度。的空间复杂度。7本章所涉及的关键字类型和数据元素类型说明:典型的关键字类型说明典型的关键字类型说明:tygedef float KeyType;/t

8、ygedef float KeyType;/实型实型typedef int typedef int KeyType;/KeyType;/整型整型typedef char *KeyType;/typedef char *KeyType;/字符串型字符串型数据元素类型数据元素类型:typedef struct typedef struct KeyType key;/KeyType key;/关键字域关键字域 ././其它域其它域 ElemType;ElemType;87.2 静态查找表静态查找表n静态查找是指如果查找过程只是查询或检索，原查静态查找是指如果查找过程只是查询或检索，原查找表没有因为查

9、找而变化的查找。一般静态查找表是找表没有因为查找而变化的查找。一般静态查找表是指用顺序表或链表表示的查找表。指用顺序表或链表表示的查找表。n一、顺序表的查找对对以以顺顺序序表表或或线线性性链链表表表表示示静静态态查查找找表表。本本书书仅仅讨讨论在顺序存储结构模块中的实现。论在顺序存储结构模块中的实现。typedef struct typedef struct ElemType*elem;/ElemType*elem;/数据元素存储空间基址数据元素存储空间基址 /建表时按实际长度分配建表时按实际长度分配,0,0号单元留空号单元留空 int length;/int length;/表长度表长度SS

10、TList;SSTList;9n顺序表：是指采用顺序存储结构表示的查找表。是指采用顺序存储结构表示的查找表。n顺序查找(Sequential Serarch)：是指从顺序表的一是指从顺序表的一端开始，让给定值依次与每个元素的关键字比较，若端开始，让给定值依次与每个元素的关键字比较，若某个元素的关键字等于给定值，则查找成功，并返回某个元素的关键字等于给定值，则查找成功，并返回该元素的下标；若没有找到关键字值为给定值，则查该元素的下标；若没有找到关键字值为给定值，则查找失败，返回空指针或其他特点信息。找失败，返回空指针或其他特点信息。顺序查找既适用于顺序表，也适用于链式存储结构顺序查找既适用于顺序

11、表，也适用于链式存储结构。10int SearchSeq2(SSTList ST,KeyType int SearchSeq2(SSTList ST,KeyType x x)/在顺序表在顺序表STST中顺序查找其关键字等于中顺序查找其关键字等于keykey的数据元素。的数据元素。/若找到若找到,则函数值为该元素在表中的位置则函数值为该元素在表中的位置,否则为否则为0 0 ST.elem0.key=ST.elem0.key=x x;/;/设置设置“监视哨监视哨”i=ST.length;i=ST.length;while(ST.datai!=x)i-;while(ST.datai!=x)i-;re

12、turn i;return i;/SearchSeq2/SearchSeq2分析分析：该算法的思想和第该算法的思想和第2 2章中的函数章中的函数LocateElem_SqLocateElem_Sq一致。只是增加一致。只是增加了监视哨，即把了监视哨，即把ST.elem0ST.elem0赋值为赋值为要查找到的关键字要查找到的关键字x x,目的在于免目的在于免去查找过程中每一步都要检测整个表是否查找完毕。去查找过程中每一步都要检测整个表是否查找完毕。监视哨也可设在高下标处。监视哨也可设在高下标处。11n根据第一章的内容，根据第一章的内容，衡量一个算法好坏的量度有三条衡量一个算法好坏的量度有三条:时间

13、复杂度时间复杂度(衡量算法执行的时间量级衡量算法执行的时间量级);空空间间复复杂杂度度(衡衡量量算算法法的的数数据据结结构构所所占占存存储储以以及及大大量量的的附附加加存储存储);算法的其它性能。算法的其它性能。n查找算法中的基本操作：查找算法中的基本操作：将记录的关键字和给定值进行比较。将记录的关键字和给定值进行比较。n衡量查找算法好坏的依据：衡量查找算法好坏的依据：其关键字和给定值进行过比较的记录个数的平均值其关键字和给定值进行过比较的记录个数的平均值n平均查找长度(ASL,(ASL,Average Average Search Search Length):Length):为为确确定定记

14、记录录在在查查找找表表中中的的位位置置,需需和和给给定定值值进进行行比比较较的的关关键键字字个个数的期望值。数的期望值。查找操作的性能分析12n含有含有n个记录的表个记录的表,查找成功时的平均查找长度为查找成功时的平均查找长度为:ASL=PiCii=1n其中：其中：P Pi i为查找第为查找第i i个记录的概率，且个记录的概率，且PPi i=1=1i=1i=1n n C Ci i为找到表中其关键字与给定值相等的第为找到表中其关键字与给定值相等的第i i个记录时，和给个记录时，和给定值已进行过比较的关键字个数。从顺序查找的过程可见定值已进行过比较的关键字个数。从顺序查找的过程可见,Ci,Ci取决

15、于所查记录在表中的位置取决于所查记录在表中的位置:查找表中最后一个记录时查找表中最后一个记录时,仅需仅需比较一次比较一次;而查找表中第一个记录时而查找表中第一个记录时,则需比较则需比较n n次。次。一般情况下，一般情况下，C Ci i=n-i+1=n-i+1。假设假设n=ST.1ength,n=ST.1ength,则顺序查找的平均查找长度为则顺序查找的平均查找长度为:ASL=nPASL=nPl l+(n-1)P+(n-1)P2 2+2P+2Pn-1n-1+P+Pn n 假设每个记录的查找概率相等假设每个记录的查找概率相等,即即:则：则：Pi=1n13即在顺序表中查找，最大比较次数与表长相同，最

16、小即在顺序表中查找，最大比较次数与表长相同，最小比较次数是比较次数是1 1，查找成功时的平均查找长度约为表长的一，查找成功时的平均查找长度约为表长的一半。半。当查找不成功时，即查找到监视哨结束，比较次数为当查找不成功时，即查找到监视哨结束，比较次数为(n+1)(n+1)。假设在查找过程中，成功与不成功的可能性相同，。假设在查找过程中，成功与不成功的可能性相同，对每个记录的查找概率也相等，则对每个记录的查找概率也相等，则p pi i=1/(2n)=1/(2n)。此时顺序。此时顺序查找平均查找长度为：查找平均查找长度为：14不过在现实中不过在现实中,表中各个记录的查找概率并不相等，如表中各个记录的

17、查找概率并不相等，如果表中各记录的查的概率已知果表中各记录的查的概率已知,且且P Pn n,P,Pn-1n-1PP2 2PPl l时时,则则ASLASL达到极小值。达到极小值。在一般情况下在一般情况下,记录的查找概率预先无法测定，为了提记录的查找概率预先无法测定，为了提高查找效率高查找效率,我们可以在每个记录中附设一个我们可以在每个记录中附设一个访问频度域,并使表中的记录始终保持按访问频度非递减有序的次序并使表中的记录始终保持按访问频度非递减有序的次序排列。排列。15以以有有序序表表表表示示静静态态查查找找表表时时,即即顺顺序序存存储储的的线线性性表表,且且记记录录按按关关键键字字keykey

18、排排列列有有序序,则则SearchSearch函函数数可可用用折折半半查查找来实现。找来实现。1.折半(对分)查找:折半查找(Binary(Binary Search)Search)，先先确确定定待待查查记记录录所所在在的的范范围围(区区间间),),然然后后每每次次将将待待查查记记录录所所在在区区间间缩缩小小一一半半，直到找到或找不到该记录为止。直到找到或找不到该记录为止。1)1)确定待查记录所在的范围确定待查记录所在的范围(区间区间););2)2)将将给给定定的的关关键键字字值值与与该该区区间间的的中中间间元元素素进进行行比比较较，若若相相等等则则查查找找成成功功;若若不不相相等等,由由中中

19、间间元元素素将将查查找找区区间间分分成成两两部部分分,若若给给定定关关键键字字小小于于中中间间元元素素,则则在在前前半半区区间间继继续续查查找找;若给定关键字大于中间元素若给定关键字大于中间元素,则在后半区间继续查找。则在后半区间继续查找。3)3)重复上述过程重复上述过程,直到查找成功直到查找成功,或失败。或失败。二、有序表的查找16n例例7-17-1:有如下有如下1010个元素的有序表个元素的有序表(假设关键字即为数据元素的值假设关键字即为数据元素的值)：(02,09,13,17,25,31,42,58,70,82)(02,09,13,17,25,31,42,58,70,82)现要查找关键字

20、为现要查找关键字为1313和和6565的数据元素。的数据元素。分析：分析：假设指针假设指针lowlow和和highhigh分别指示待查元素所在范围的下界和分别指示待查元素所在范围的下界和上界上界,指针指针midmid指示区间的中间位置指示区间的中间位置,即即mid=(low+high)/2mid=(low+high)/2。给定值给定值key=13key=13的查找过程的查找过程:02 09 13 17 25 31 42 58 70 82lowhighmidhighmidlowmid17再看再看key=65key=65的查找过程的查找过程:02 09 13 17 25 31 42 58 70 8

21、2lowhighmidlowmidlowmidhigh 从上述例子可见从上述例子可见,折半查找过程是以处于区间中间位折半查找过程是以处于区间中间位置记录的关键字和给定值比较置记录的关键字和给定值比较,若相等若相等,则查找成功；若则查找成功；若不等不等,则缩小范围则缩小范围,直至新的区间中间位置记录的关键字直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小等于给定值或者查找区间的大小(high-low)(high-low)小于零时小于零时(表表明查找不成功明查找不成功)为止。为止。上述折半查找过程算法如下。上述折半查找过程算法如下。18int SearchBinary(SSTList

22、ST,KeyType key)int SearchBinary(SSTList ST,KeyType key)/在有序表在有序表STST中折半查找关键字等于中折半查找关键字等于keykey的数据元素。的数据元素。/若找到，则函数值为该元素在表中的位置，否则为若找到，则函数值为该元素在表中的位置，否则为0 0 low=1;high=ST.length;/low=1;high=ST.length;/置区间初值置区间初值 while(low=high)while(low=high)mid=(low+high)/2;mid=(low+high)/2;if(key=ST.elemmid).key if(

23、key=ST.elemmid).key return mid;/return mid;/查找成功，返回该元素的位置查找成功，返回该元素的位置 else if(keyST.elemmid.key)else if(key50)(n50)时时,可有下列近似结果：可有下列近似结果：ASL ASLbsbs=log=log2 2(n+1)-1(n+1)-1可见，折半查找的效率比顺序查找高。可见，折半查找的效率比顺序查找高。但折半查找只能适用于但折半查找只能适用于有序表有序表,且限于顺序存储结构且限于顺序存储结构(对对线性链线性链表无法进行折半查找表无法进行折半查找)。折半查找的平均查找长度:23n斐波那契

24、查找是是根根据据斐斐波波那那契契序序列列的的特特点点对对表表进进行行分分割的。割的。假设开始时表中记录个数比某个裴波那契数小假设开始时表中记录个数比某个裴波那契数小1,1,即即n=Fn=Fu u-1,-1,然后将给定值然后将给定值keykey和和ST.elemFST.elemFu-1u-1.key.key进行比较进行比较,若相等若相等,则查找成功则查找成功;若若keyST.elemFkeyST.elemFu-1u-1.key,.key,则继续则继续在自在自ST.elem1ST.elem1至至ST.elemFST.elemFu-1u-1-1-1的子表中进行查找的子表中进行查找,否则继续在自否则继

25、续在自ST.elemFST.elemFu-1u-1+1+1至至ST.elemFST.elemFu u-1-1的子表的子表中进行查找中进行查找,后一子表的长度为后一子表的长度为F Fu-2u-2-1-1。斐斐波波那那契契查查找找的的平平均均性性能能比比折折半半查查找找好好,但但最最坏坏情情况况下下的的性性能能(虽虽然然仍仍是是O(logO(logn n)却却比比折折半半查查找找差差。它它还还有有一个优点就是分割时只需进行加、减运算。一个优点就是分割时只需进行加、减运算。3.其他查找算法24n插值查找是是根根据据给给定定值值keykey在在查查找找区区间间的的相相对对位位置置来来来来确确定定进进行

26、行比比较较的的关关键键字字ST.elemi.keyST.elemi.key的的查查找找方方法法。令令：其其中中ST.elemlowST.elemlow和和ST.elemhighST.elemhigh分分别别为为有有序序表表中中具有最小关键字和最大关键字的记录。具有最小关键字和最大关键字的记录。如如果果keyST.elemi.keykeyST.elemi.keykeyST.elemi.key，则则确确定定新新的的查查找找区区间为间为i+1,highi+1,high。插值查找适用于关键字均匀分布的表。插值查找适用于关键字均匀分布的表。25n分块查找，也叫索引顺序表的查找。也叫索引顺序表的查找。索引

27、的分类：稠密索引、稀疏索引的分类：稠密索引、稀疏(分块分块)索引索引n索索引引顺顺序序表表：将将查查找找表表,分分成成若若干干个个子子表表(块块),),并并为为每每个个子子表表建建立立一一个个索索引引项项,所所有有索索引引项项构构成成一一个个索索引引表表,且且索索引引表表按按keykey升升序序排排列列,对对查查找找表表本本身身,可可以以是是有有序序的的,也也可可以以是是分分块块有有序序的的(即即块块内内不不一一定定有有序序),),但但后后一一块块中中任任一一元元素素的的keykey均均大大于于前前一一块块中中的的keykey的的最大值。最大值。n分块查找分块查找：(1)(1)先先查查索索引引

28、表表,以以确确定定记记录录所所在在的的块块(子子表表)。用用顺顺序序或或折折半半均均可可;(2)(2)在块内顺序查找。在块内顺序查找。三、分块查找26key=47key=65例例:有一张表有一张表(13,9,20,7,25,18,29,33,47,41,38,36,53,58,(13,9,20,7,25,18,29,33,47,41,38,36,53,58,72,67,75,62),72,67,75,62),给它分成三个子表给它分成三个子表(R1.R6),(R7.R12),(R1.R6),(R7.R12),(R13.R18)(R13.R18)。对每个子表建立一个索引项对每个子表建立一个索引项,

29、包括两项内容包括两项内容:关键关键字项字项(其值为该子表内的最大关键字其值为该子表内的最大关键字)和指针项和指针项(指示该子表的第指示该子表的第一个记录在表中位置一个记录在表中位置)。如图所示。如图所示:27n性能分析性能分析分块查找的算法实际为顺序查找和折半查找算法的简单合成。分块查找的算法实际为顺序查找和折半查找算法的简单合成。分块查找的平均查找长度为：分块查找的平均查找长度为：ASLASLbsbs=L=Lb b+L+Lw w 其其中中:L:Lb b为为查查找找索索引引表表确确定定所所在在块块的的平平均均查查找找长长度度,L,Lw w为为在在块块中中查找元素的平均查找长度。查找元素的平均查

30、找长度。一一般般情情况况下下,为为进进行行分分块块查查找找,可可以以将将长长度度为为n n的的表表均均匀匀地地分分成成m m块块,每块含有每块含有s s个记录个记录,即即s=s=n/mn/m;又又假假定定表表中中每每个个记记录录的的查查找找概概率率相相等等,则则每每块块查查找找的的概概率率为为1/m,1/m,块中每个记录的查找概率为块中每个记录的查找概率为1/s1/s。28若用顺序查找确定所在块若用顺序查找确定所在块,则分块查找的平均查找长度为则分块查找的平均查找长度为:ASLbs=Lb+Lw=此时的平均查找长度不仅和表长此时的平均查找长度不仅和表长n n有关有关,而且和每一块中的记录而且和每

31、一块中的记录个数个数s s或索引表的长度有关。在给定或索引表的长度有关。在给定n n的前提下的前提下,m,m是可以选择的。是可以选择的。由数学知识不难推知，当由数学知识不难推知，当m=n/mm=n/m，即，即m=sqrt(n)m=sqrt(n)时，平均查找长时，平均查找长度最小，为度最小，为1+sqrt(n)1+sqrt(n)。若用折半查找确定所在块。若用折半查找确定所在块,则分块查找的则分块查找的平均查找长度为平均查找长度为:29下面给出索引表的存储结构及查找算法：下面给出索引表的存储结构及查找算法：typedef structtypedef struct /索引表结点索引表结点KeyTyp

32、e index;KeyType index;/最大关键字域最大关键字域int start;int start;/指向本块第一指向本块第一个结点的位置个结点的位置 IndexList;IndexList;typedef structtypedef struct /索引主表结点索引主表结点 KeyType key;KeyType key;/关键字域关键字域 MainList;MainList;30intintBlockSearch(MainList ms,IndexList is,int b,BlockSearch(MainList ms,IndexList is,int b,int n,KeyT

33、ype key)int n,KeyType key)/主表为主表为ms1.msn,ms1.msn,索引表为索引表为is0.isb-1,is0.isb-1,/b/b为子表个数为子表个数,key,key为给定值为给定值,n,n为表长为表长 i=0;/i=0;/先查索引表先查索引表 while while(keyisi.index)&(iisi.index)&(i=b)(i=b)printf(n Not found);printf(n Not found);return return 0;0;j=isi.start;j=isi.start;while(jn)&(key!=msj.key)&while

34、(jn)&(key!=msj.key)&(msj.key=isi.index)(msj.key=isi.index)j+;j+;if(key=msj.key)if(key=msj.key)return return j;j;else else return return 0;0;/BlockSearch /BlockSearch31n动态查找表：对对查查找找表表可可以以进进行行插插入入或或删删除除等等操操作作,也也就就是是说说查查找找表表本本身身可可以以是是在在查查找找过过程程中中动动态态生生成成的的,即即对对于于给给定定值值key,key,若若表表中中存存在在其其关关键键字字等等于于keyk

35、ey的的记记录录,则则查查找成功返回找成功返回,不成功则插入关键字等于不成功则插入关键字等于keykey的记录。的记录。二叉排序树二叉排序树平衡二叉树平衡二叉树B-B-树树B+B+树树7.3 动态查找表动态查找表 32 二叉排序树，也也称称二二叉叉查查找找树树，是是二二叉叉树树的的一一个个特特例例，或或者者是是一棵空树一棵空树;或者是具有下列性质的二叉树或者是具有下列性质的二叉树:1)若若它它的的左左子子树树不不空空,则则左左子子树树上上所所有有结结点点的的值值均均小小于于它它的的根根结点的值结点的值;2)若若它它的的右右子子树树不不空空,则则右右子子树树上上所所有有结结点点的的值值均均大大子

36、子它它的的根根结点的值结点的值;3)它的左、右子树也分别为二叉排序树。它的左、右子树也分别为二叉排序树。如图所示：如图所示：一、二叉排序树33n根据上述定义的结构特点可见根据上述定义的结构特点可见,它的查找过程如下：它的查找过程如下：当当二二叉叉排排序序树树不不空空时时,首首先先将将给给定定值值和和根根结结点点的的关关键键字字比比较较，若若相相等等，则则查查找找成成功功，否否则则将将依依据据给给定定值值和和根根结结点点的的关关键键字字之之间间的的大大小小关关系系，分分别别在在左左子子树树或或右右子子树树上上继继续续进进行查找。行查找。n取取二二叉叉链链表表作作为为二二叉叉排排序序树树的的存存储

37、储结结构构,为为了了讨讨论论问问题题的的方方便便，假假设设二二叉叉树树的的关关键键字字值值为为十十进进制制无无符符号号整整数。查找过程算法：数。查找过程算法：34BTNPtr SearchBTree1(BiTree T,KeyType d)BTNPtr SearchBTree1(BiTree T,KeyType d)/在根结点为在根结点为T T的二叉排序树中递归查找关键字为的二叉排序树中递归查找关键字为d d的元素。的元素。/成功返回指向结点的指针，否则返回空指针。成功返回指向结点的指针，否则返回空指针。BTNPtr ptr=T;BTNPtr ptr=T;if(ptr=NULL)return

38、ptr;if(ptr=NULL)return ptr;if(d if(d data)ptr-data)ptr ptr =ptr-leftChild;=ptr-leftChild;else if(d=ptr-data)return ptr;else if(d=ptr-data)return ptr;else ptr=ptr-rightChild;else ptr=ptr-rightChild;return SearchBTree(ptr,d);return SearchBTree(ptr,d);/SearchBTree1/SearchBTree1该算法可以非常容易的改写为非递归形式算法。该算法可

39、以非常容易的改写为非递归形式算法。35对对二二叉叉排排序序树树的的成成功功查查找找过过程程实实际际上上是是走走了了一一条条从从根根到到记记录录所所在在结结点点的的路路径径，比比较较次次数数就就是是结结点点所所在在的的层层次次数数。因因此此，成成功功查查找找时时，关关键键字字的的比比较较次次数数不不超超过过二二叉叉树树的的高高度度。显显然然当当每每个个叶叶子子的的高高度度基基本本一一样样时时，查查询询效效率率与与折折半半查查找找相相当当，平平均均查查找找次次数数为为O(logO(log2 2n)n)，其中，其中n n为结点的个数。为结点的个数。n2.2.二叉排序树二叉排序树的插入和删除的插入和删

40、除二二叉叉排排序序树树是是一一种种动动态态树树表表，其其特特点点是是,树树的的结结构构通通常常不不是是一一次次生生成成的的,而而是是在在查查找找过过程程中中,当当树树中中不不存存在在关关键键字字等等于于给给定定值值的的结结点点时时再再进进行行插插入入。新新插插入入的的结结点点一一定定是是一一个个新新添添加加的的叶叶子子结结点点,并并且且是是查查找找不不成成功功时时查查找找路路径径上上访访问问的的最最后后一一个个结结点点的的左左孩孩子子或或右右孩孩子子结结点点。为为此此,需需将将上上一一小小节节的的二二叉叉排排序序树树的的查查找找算算法法进进行行算法，以便能在查找不成功时返回插入位置。插入算法如

41、下所示：算法，以便能在查找不成功时返回插入位置。插入算法如下所示：36n设有关键字序列设有关键字序列 50,22,7,31,68,26,50,22,7,31,68,26,生成的二生成的二叉排序树过程叉排序树过程:371.1.如果结点当前二叉树如果结点当前二叉树T T为空，创建结点为空，创建结点ptrptr，该结点成为当，该结点成为当前根结点，即将前根结点，即将ptrptr置为置为T T，将给定值，将给定值d d赋值给赋值给ptr-dataptr-data，然后返，然后返回；回；2.2.如果当前二叉树如果当前二叉树T T非空，让动态指针指向根结点，即非空，让动态指针指向根结点，即ptr=Tptr

42、=T，然后将给定值与当前根结点的值进行比较：，然后将给定值与当前根结点的值进行比较：n如果如果ddataddata，并且如果，并且如果ptr-leftChildptr-leftChild等于空，则创建结点等于空，则创建结点S S，S-data=dS-data=d，并将，并将ptr-leftChildptr-leftChild置为置为S S，退出算法，否则，退出算法，否则ptr=ptr-ptr=ptr-leftChildleftChild；n如果如果dptrdptr-datadata，并且如果，并且如果ptr-rightChildptr-rightChild等于空，创建结点等于空，创建结点S S

43、，S-S-data=ddata=d，并将，并将ptr-rightChildptr-rightChild置为置为S S，退出算法，否则，退出算法，否则ptr=ptr-ptr=ptr-rightChildrightChild；n如果如果d=ptr-datad=ptr-data，则停止插入，退出算法。，则停止插入，退出算法。3.3.转向第转向第(2)(2)步，继续查找过程，直到完成插入或找到该结点。步，继续查找过程，直到完成插入或找到该结点。二叉树排序的插入算法步骤：38Status InertNodeBTree(BiTree&T,KeyType d)Status InertNodeBTree(Bi

44、Tree&T,KeyType d)/二叉排序树的插入二叉排序树的插入.如果如果T T中不存在关键字为中不存在关键字为d d的结点的结点,插入插入,否则直接返回。否则直接返回。BTNPtr ptr=NULL;BTNPtr ptr=NULL;if(T=NULL)/if(T=NULL)/是棵空树是棵空树 T=(BiTree)malloc(sizeof(BiTNode);T=(BiTree)malloc(sizeof(BiTNode);T-data=d;return OK;T-data=d;return OK;ptr=T;ptr=T;BTNPtr S=(BiTree)malloc(sizeof(BiT

45、Node);/BTNPtr S=(BiTree)malloc(sizeof(BiTNode);/新结点生成并赋初值新结点生成并赋初值 S-data=d;S-leftChild=S-rightChild=NULL;S-data=d;S-leftChild=S-rightChild=NULL;do do if(ptr-data=d)return OK;if(ptr-data=d)return OK;if(d data)if(d data)if(ptr-leftChild=NULL)if(ptr-leftChild=NULL)ptr-leftChild=S;/ptr-leftChild=S;/新结点

46、为当前结点的左孩子新结点为当前结点的左孩子 return OK;return OK;ptr=ptr-leftChild;ptr=ptr-leftChild;else else if(ptr-rightChild=NULL)if(ptr-rightChild=NULL)ptr-rightChild=S;/ptr-rightChild=S;/新结点为当前结点的右孩子新结点为当前结点的右孩子 return OK;return OK;ptr=ptr-rightChild;ptr=ptr-rightChild;while(1);while(1);return OK;return OK;/InertNod

47、eBTree /InertNodeBTree39结论：1 1）中序遍历这棵二叉排序树：）中序遍历这棵二叉排序树：2 2）插入的新结点都是二叉排序树上新的叶子结点）插入的新结点都是二叉排序树上新的叶子结点,不必移动其不必移动其它结点它结点,仅需改动某个结点的指针仅需改动某个结点的指针,由空变为非空即可由空变为非空即可,即在有即在有序序列上插入一个记录而不需要移动其它记录序序列上插入一个记录而不需要移动其它记录3)3)从上述生成过程可以看出，给定关键字序列生成的最终二叉从上述生成过程可以看出，给定关键字序列生成的最终二叉排序树形状是一定的，但反过来就不一定，即给定的二叉排排序树形状是一定的，但反过

48、来就不一定，即给定的二叉排序树可以有多种关键字序列方式。序树可以有多种关键字序列方式。如如50,22,68,31,7,2650,22,68,31,7,26或或50,22,68,7,31,2650,22,68,7,31,26或或50,68,22,31,26,750,68,22,31,26,7都能得到都能得到相同的相同的二叉排序树二叉排序树 40n在二叉排序树上删去一个结点也要求在删除某个结点之后依旧保在二叉排序树上删去一个结点也要求在删除某个结点之后依旧保持二叉排序树的特性。持二叉排序树的特性。假设删除结点为假设删除结点为N N，它的父结点为，它的父结点为N Np p，它的两个孩子为，它的两个孩

49、子为N NL L与与N NR R。(1)(1)先考虑最简单的情况：先考虑最简单的情况：N NL L与与N NR R中至少有一个为空中至少有一个为空N NL L与与N NR R都为空，表示结点都为空，表示结点N N是叶子结点，则删除该结点比较是叶子结点，则删除该结点比较简单，删除后，不影响原来的二叉排序树。简单，删除后，不影响原来的二叉排序树。N NL L为空，表示为空，表示N N没有左孩子，则删除没有左孩子，则删除N N结点后，直接可以将结点后，直接可以将NRNR作为作为NpNp的子结点，并保持原来的子结点，并保持原来N N是是N Np p的关系，即如果原来的关系，即如果原来N N是是N Np

50、 p的左孩子，则的左孩子，则N NR R还是作为还是作为NpNp的左孩子，如果原来的左孩子，如果原来N N是是N Np p的的右孩子，则右孩子，则N NR R还是作为还是作为NpNp的右孩子。的右孩子。如果如果N NR R为空，方法与为空，方法与(2)(2)类似，即直接将类似，即直接将N NL L作为作为N Np p的子结点。的子结点。二叉排序树上结点的删除41 (2)(2)如果如果N NL L与与N NR R都不为空，这里假定都不为空，这里假定N N为为N Np p的左孩子，在原来的左孩子，在原来二叉排序树中的中序遍历结果为二叉排序树中的中序遍历结果为C C1 1C C2 2.C.Cu uN