典型查找算法课件.ppt

1、第第9章章 典型查找算法典型查找算法 顺序查找、折半查找和分块查找的方法顺序查找、折半查找和分块查找的方法和算法，相应的平均查找长度和算法，相应的平均查找长度二叉排序树查找方法和算法，二叉平衡二叉排序树查找方法和算法，二叉平衡树概念树概念散列表的概念，散列函数的构造方法，散列表的概念，散列函数的构造方法，处理冲突的方法及散列表各种运算的实处理冲突的方法及散列表各种运算的实现算法现算法 1第第9章章 典型查找算法典型查找算法 9.1 9.1 实例：学生分配座位实例：学生分配座位 9.2 9.2 静态查找静态查找 9.3 9.3 动态查找动态查找 9.4 9.4 散列查找散列查找 本章总结本章总结

2、29.1 实例：学生分配座位实例：学生分配座位 9.1.1 问题描述问题描述 9.1.2 问题的分析问题的分析 9.1.3 实现算法实现算法 9.1.4 基本概念基本概念 39.1.1 问题描述问题描述 教室中的学生座位分配教室中的学生座位分配是一个最简单是一个最简单的例子。假定某教室有的例子。假定某教室有35个座位，如果个座位，如果不加限定任意就坐或按某种规律就座，则不加限定任意就坐或按某种规律就座，则要查找某学生要查找某学生时就要时就要将待查找的学生与当将待查找的学生与当前座位上的学生进行比较前座位上的学生进行比较。49.1.2 问题的分析问题的分析 用计算机来解决查找学生问题，通常需要做

3、以下工作：第一，学生信息以什么形式表示和存储学生信息以什么形式表示和存储；第二，查找的具体实现方法查找的具体实现方法(算法)。5struct student int num1;/表示座号int num2;/表示学号char name12;/表示姓名 ；struct listStudent stusize;/保存学生记录Int len;/学生人数;学生信息的存储方式：学生信息的存储方式：6 从第一个学生开始，从第一个学生开始，依次与查找的学生进依次与查找的学生进行比较行比较。在查找过程中，若某个学生的记录与。在查找过程中，若某个学生的记录与所查找学生记录所查找学生记录相等相等，则查找，则查找成功

4、成功，返回该学返回该学生在表中位置生在表中位置；若全部比较完毕，没有符合条；若全部比较完毕，没有符合条件的学生记录，则查找件的学生记录，则查找不成功不成功，返回返回-1。查找学生的方法：查找学生的方法：79.1.3 实现算法实现算法 int search(List&L,int s)/从表L.stu0,L.stu1,L.stun-1的n个元素中查找关键字为S的元素，若查找成功返回该生学号，否则返回-1 int i;for(i=0;iL.len;i+)if(L.stui=s)break;if(i0i0，从而节省比较的时间。从而节省比较的时间。顺序查找的平均查找长度为：顺序查找的平均查找长度为：有时

5、，表中各结点的查找概率并不相等。因有时，表中各结点的查找概率并不相等。因 此若事先知道表中各结点查找概率的分布情此若事先知道表中各结点查找概率的分布情 况，则可将表中结点按查找概率从大到小排况，则可将表中结点按查找概率从大到小排 列，以便提高顺序查找的效率。列，以便提高顺序查找的效率。顺序查找的特点：算法简单，但查找效率低。顺序查找的特点：算法简单，但查找效率低。111(1)/2nnsqiiiiASLpcinn16 折半查找又称为折半查找又称为二分查找二分查找。折半要求折半要求查找表是有序的查找表是有序的。折半查找的折半查找的基本思想基本思想是：是：首先将待查的首先将待查的K值与有序表值与有序

6、表R0到到Rn-1的的中间中间位置位置mid上的上的结点的关键字进行比较，结点的关键字进行比较，若相等若相等，则则查找完成查找完成；否则，若否则，若Rmid.keyK，则，则说明待查找的结点说明待查找的结点只可能在左表只可能在左表R0到到Rmid-1中，只需在左子表中，只需在左子表中继续查找；否则在右子表中继续查找。这样，中继续查找；否则在右子表中继续查找。这样，经过一次键字的比较就缩小了一半的查找区间。经过一次键字的比较就缩小了一半的查找区间。重复执行，直到找到关键字为重复执行，直到找到关键字为K的元素或当前查的元素或当前查找区间为空找区间为空(即表明查找失败即表明查找失败)为止。为止。9.

7、2.29.2.2 折半查找折半查找1705 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=21K=21的过程（查找成功）的过程（查找成功）midhighlowlowhighmidlowhighmid1805 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=85K=85的过程（查找失败）的过程（查找

8、失败）05 13 19 21 37 56 64 75 80 88 92 lowhighmidmidlowhighmidlowhighlowhigh19折半查找算法（折半查找算法（low和和high分别表示当前查找区分别表示当前查找区间的下界和上界）间的下界和上界）int BINSEARCH(SSTable ST,keytype K)int low,mid,high;low0;highn-1;while(low=high)mid(low+high)/2;/整除整除 if(K=ST.Rmid.key)return mid;if(KST.Rmid.key)highmid-1;else lowmid+

9、1;return-1;/查找失败查找失败20 虽然折半查找的效率较高，但它要求被查找虽然折半查找的效率较高，但它要求被查找序列事先按关键字排好序，而排序本身是一种很序列事先按关键字排好序，而排序本身是一种很费时的运算；另外，折半查找只适用于顺序存储费时的运算；另外，折半查找只适用于顺序存储结构，因此，折半查找特别适用于那种一经建立结构，因此，折半查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。就很少改动、而又需要经常查找的线性表。21二叉判定树：二叉判定树：表示折半查找的查找过程。树中的每个结点表示表中一个元素，每棵子树的根结点表示当前查找根结点表示当前查找区间的中间点元素区间

10、的中间点元素，它的左子树和右子树分别对应该区左子树和右子树分别对应该区间的左子表和右子表间的左子表和右子表。二叉判定树是一棵二叉排序树。二叉判定树是一棵二叉排序树。二分查找的平均查找长度为：二分查找的平均查找长度为：)21()2(11111hhiinnhiASL229.2.3 分块查找分块查找 分块查找分块查找(索引顺序查找索引顺序查找)基本思想：基本思想：首先把一个线性表(即主表)按照一定的函数关系或条件划分成若干个逻辑子表逻辑子表，为每个子表分别建立一个索引索引项项，由所有子表的索引项构成一个索引表索引表。当进行分块查找时，先根据所给的关键字查找索引表，从中查找出给定先根据所给的关键字查找

11、索引表，从中查找出给定值值K K刚好小于等于索引值的那个索引项，找到待查块，然刚好小于等于索引值的那个索引项，找到待查块，然后再到主表中查找该块，从中查找待查的记录后再到主表中查找该块，从中查找待查的记录。实现算法：实现算法：（略）索引表是有序的索引表是有序的，所以在索引表上既可以采用顺序查找，也可以采用折半查找，而每个块中的记录排列是任意任意的的，所以在块内只能采用顺序查找。23平均查找长度为：平均查找长度为：设将长度为设将长度为n n的表均匀分成的表均匀分成b b块，每块有块，每块有s s个记录，个记录，则则b=n/s，查找表中每条记录的概率相等，则每块查找表中每条记录的概率相等，则每块查

12、找的概率为查找的概率为1/b，块中每条记录的查找概率为块中每条记录的查找概率为1/s。则顺序查找索引表时：则顺序查找索引表时：1)(21212111L1121ssnsbisjbLASLsibj24 分块有序表的索引存储表示分块有序表的索引存储表示 25索引表结点的数据类型定义如下：索引表结点的数据类型定义如下：#define MaxIndex typedef struct KeyType key;int addr(link);IdxType;在这种结构下，查找过程要分为两步：首先在这种结构下，查找过程要分为两步：首先查找索查找索引表引表。因为索引表是有序表，所以可采用二分查找或顺。因为索引表是

13、有序表，所以可采用二分查找或顺序查找，以确定给定值所在的块。因为块中的记录可以序查找，以确定给定值所在的块。因为块中的记录可以是任意排列的，所以再在已确定的是任意排列的，所以再在已确定的块块中进行中进行顺序查找顺序查找。26分块查找算法如下：分块查找算法如下：int IdxSerch(SeqList A,IdxType index,int b,KeyType k,int n)/分块查找关键字为分块查找关键字为k的记录，索引表为的记录，索引表为index0.b-1 int low=0,high=b-1,mid,i;int s=n/b;/每块记录个数每块记录个数 while(low=high)/在

14、索引表中进行二分查找，找到的位置放在在索引表中进行二分查找，找到的位置放在low中中 mid=(low+high)/2;if(indexmid.keyk)low=mid+1 else high=mid-1;if(lowb)/在块中顺序查找在块中顺序查找 for(i=indexlow.addr;i=indexlow.addr+s-1&i(*q)-elem.key)/*kx大于当前结点*q的元素关键码*/*p=*q;*q=(*q)-rc;/*将当前结点*q的右子女置为新根*/elseif(kxelem.key)/*kx小于当前结点*q的元素关键码*/*p=*q;*q=(*q)-lc;/*将当前结点

15、*q的左子女置为新根*/elseflag=1;break;/*查找成功，返回*/*while*/return flag;35时间复杂度：时间复杂度：分析：在二叉排序树上进行查找的过程中，根结点为待查结点时，给定值同树中结点的比较次数仅为一次，待查结点位于最后一层时，比较的次数为树的深度。普通情况下，对二叉排序树进行查找的时间复杂度为O()；最差情况下(二叉排序树为一棵单支树)，其时间复杂度为O(n)。n2log45245312371001224374553100(a)深度为3的二叉排序树(b)深度为6的二叉排序树 为使得由任何初始序列构成的二叉排序树的平均查找长度是对数级的，所以我们可使得构造

16、的二叉排序树是一个平衡二叉树。36三.二叉排序树插入操作和构造一棵二叉排序树 向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。37 图9.5 从空树开始建立二叉排序树的过程 38【算法9.5】int InsertNode(NodeType*t,KeyType kx)/*在二叉排序树*t上插入关键码为kx的结点*/NodeType*q,*s,*p=*t;int flag=0;

17、if(!SearchElem(*t,&p,&q,kx);/*在*t为根的子树上查找*/s=(NodeType*)malloc(sizeof(NodeType);/*申请结点,并赋值*/s-elem.key=kx;s-lc=NULL;s-rc=NULL;flag=1;/*设置插入成功标志*/if(!p)t=s;/*向空树中插入时*/elseif(kxp-elem.key)p-rc=s;/*插入结点为p的右子女*/elsep-lc=s;/*插入结点为p的左子女*/return flag;399.3.2 二叉平衡树二叉平衡树 二叉平衡树二叉平衡树(AVL树)：或者是一棵空树，或者是一棵具有如下性质的

18、非空二叉树：它的左子树和右子树都是二叉平衡树，且左子树左子树和右子树的深度之差的绝对值不大于和右子树的深度之差的绝对值不大于1 1。二叉平衡树中结点的左子树的深度减去它的右子树的深度的值定义为平衡因子平衡因子BFBF，则BFBF的值只可能为的值只可能为1 1、0 0和和1 1。40对二叉排序树插入结点而构造平衡二叉树的规律：对二叉排序树插入结点而构造平衡二叉树的规律：设最小子树根结点的指针为a，则失去平衡后进行调整的规律：LLLL型：型：单向右旋平衡处理单向右旋平衡处理 RRRR型：型：单向左旋平衡处理单向左旋平衡处理 LR LR型：型：双向旋转双向旋转(先左后右先左后右)平衡处理平衡处理 R

19、L RL型：型：双向旋转双向旋转(先右后左先右后左)平衡处理平衡处理时间复杂度：时间复杂度：在查找过程中和给定值进行比较的关键字的个数不超过树的深度，所以，在二叉平衡树上进行查找的时间复杂度为时间复杂度为O(O(log2n)。41平衡二叉树和非平衡二叉树平衡二叉树和非平衡二叉树 1317141116121513111214151617(a)(b)1-1-10100-2-1-30-2-10图9.942 图9.9给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的树中，左子树与右子树高度之差，这个数字称为结点的平衡因子。由平衡二叉树定义，所有结点的平衡因子只能取-1，0，1三个值之一。若二叉

20、排序树中存在这样的结点，其平衡因子的绝对值大于1，这棵树就不是平衡二叉树。如图9.9（a）所示的二叉排序树。在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况：43对二叉排序树插入结点而构造平衡二叉树的规律：对二叉排序树插入结点而构造平衡二叉树的规律：设最小子树根结点的指针为a，则失去平衡后进行调整的规律：LLLL型：型：单向右旋平衡处理单向右旋平衡处理 RRRR型：型：单向左旋平衡处理单向左旋平衡处理 LR LR型：型：双向旋转双向旋转(先左后右先左后右)平衡处理平衡处理

21、RL RL型：型：双向旋转双向旋转(先右后左先右后左)平衡处理平衡处理时间复杂度：时间复杂度：在查找过程中和给定值进行比较的关键字的个数不超过树的深度，所以，在二叉平衡树上进行查找的时间复杂度为时间复杂度为O(O(log2n)。44一.左单旋转（RR型）在图(a)所示的树上插入结点x，如图(b)所示。结点x插入在结点c的右子树E上，导致结点a的平衡因子绝对值大于1，以结点a为根的子树失去平衡。45【调整策略】调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。由于结点c的左子树D可作为结点a的右子树，将结点a为根的子树调整为左子树是B，右子树是D，再将结点a为根的子树调整为结点

22、c的左子树，结点c为新的根结点，如图(c)。【平衡化调整操作判定】沿插入路径检查三个点a、c、E，若它们处于“”直线上的同一个方向，则要作左单旋转，即以结点c为轴逆时针旋转。46说明：1.旋转操作的正确性可以由二叉排序树的特性：中序遍历所得关键字序列自小至大有序证明之。2.当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转即可。因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所由祖先结点的平衡度。47二.右单旋转（LL型）右单旋转与左单旋转类似，沿插入路径检查三个点a、c、E，若它们处于“/”直线上的同一个方向，则要作右单旋转，即以结点c为轴顺时针旋转

23、，如图9.11所示。48 如图9.12为插入前的子树，根结点a的左子树比右子树高度高1，待插入结点x将插入到结点b的右子树上，并使结点b的右子树高度增1，从而使结点a的平衡因子的绝对值大于1，导致结点a为根的子树平衡被破坏，如图9.12 插入前图9.13(a)、9.14(d)所示。图9.12 插入前49三.先左后右双向旋转（LR型）图9.13 5051 沿插入路径检查三个点a、b、c，若它们呈“”字形，需要进行先左后右双向旋转：1.首先，对结点b为根的子树，以结点c为轴，向左逆时针旋转，结点c成为该子树的新根，如图(b、e)；2.由于旋转后，待插入结点x相当于插入到结点b为根的子树上，这样a、

24、c、b三点处于“/”直线上的同一个方向，则要作右单旋转，即以结点c为轴顺时针旋转，如图(c、f)。52四.先右后左双向旋转（RL型）先右后左双向旋转和先左后右双向旋转对称，自行补充整理。539.4 散列查找散列查找 9.4.1 散列存储和散列函数的构造方法散列存储和散列函数的构造方法 9.4.2 解决冲突的方法解决冲突的方法 9.4.3 散列查找实现算法和性能分析散列查找实现算法和性能分析 549.4.1 散列存储和散列函数构造散列存储和散列函数构造基本术语：基本术语：散列存储散列存储：以数据中每个元素的关键字：以数据中每个元素的关键字K K为自变量，为自变量，通过一个函数通过一个函数f(k)

25、f(k)计算出函数值，把这个值同存储空计算出函数值，把这个值同存储空间中一个唯一的存储位置相对应，将该元素存储到这间中一个唯一的存储位置相对应，将该元素存储到这个存储位置中。函数个存储位置中。函数f(k)f(k)称为称为散列函数散列函数或或哈希函数哈希函数。f(k)f(k)的值称为的值称为散列地址散列地址或或哈希地址哈希地址；进行散列存储的；进行散列存储的地址空间称为地址空间称为散列表散列表或或哈希表哈希表。冲突冲突：实际应用中，由于散列函数的构造方法不实际应用中，由于散列函数的构造方法不同，常会出现同，常会出现多个元素同时占用一个存储单元多个元素同时占用一个存储单元的情况，的情况，即散列地址

26、相同，这种现象叫冲突即散列地址相同，这种现象叫冲突。具有相同函数值具有相同函数值的不同关键字的元素，称为的不同关键字的元素，称为同义词同义词。55常用的构造散列函数的方法：常用的构造散列函数的方法：直接定址法直接定址法:取关键字或关键字的某个现行函数值为哈希地址。取关键字或关键字的某个现行函数值为哈希地址。即：即：H(keyH(key)=key)=key 或或 H(keyH(key)=)=akey+bakey+b。数字分析法数字分析法假设关键字是以假设关键字是以r r为基的数为基的数(如：以如：以1010为基的十进制数为基的十进制数)，并且哈希表中可，并且哈希表中可能出现的关键字都是事先知道的

27、，则可取关键字的若干数位组成哈希地址。能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。平方取中法：平方取中法：取关键字平方后的中间几位为哈希地址。取关键字平方后的中间几位为哈希地址。折叠法折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。后取这几部分的叠加和（舍去进位）作为哈希地址。除留余数法除留余数法 取关键字被某个不大于哈希表表长取关键字被某个不大于哈希表表长m m的数的数p p除后所得余数为哈希地址。即除后所得余数为哈希地址。即 H(keyH(

28、key)=key MOD p,p=m)=key MOD p,p=m该方法是一种最简单，也最常用的构造哈希函数的方法。该方法是一种最简单，也最常用的构造哈希函数的方法。随机数法随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址。选择一个随机函数，取关键字的随机函数值为它的哈希地址。即即:H(keyH(key)=)=random(keyrandom(key)569.4.2 解决冲突的方法解决冲突的方法 常用的解决冲突的方法有以下几种：常用的解决冲突的方法有以下几种：开放定地址开放定地址链地址法链地址法 再哈希法再哈希法建立一个公共溢出区建立一个公共溢出区 57 从发生冲突的那个单元开始，

29、按照一定次序，从散列表中查找出一个空闲存储单元，把发生冲突的待插入元素存入到该单元中的一类解决冲突的方法。设H(key)为散列函数，m为散列表长度。则开放定址法中找下一个空闲空间的散列函找下一个空闲空间的散列函数为：数为：Hi=(H(key)+Hi=(H(key)+d di i)%m)%m 其中，i=1,2k；d di i称为增称为增量量，以di的取值分为以下三种：(1)di=1,2,3m-1,称线性探测再散列线性探测再散列。(2)di=12,-12，22，-22，k2,(km/2)称二次探测再散二次探测再散列列。(3)di=随机数序列，称为随机探测再散列随机探测再散列。开放定址法：开放定址法

30、：58 把具有相同散列地址的关键字放在同一链表中相同散列地址的关键字放在同一链表中，称为同义词链表同义词链表。通常把具有相同散列地址的关键字都存放在一个同义词链表中，有m个散列地址就有m个链表，同时用数组tm存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以ti为头指针的单链表中。链地址法：链地址法：599.4.3 散列查找实现算法和性能分析散列查找实现算法和性能分析散列表的长度表中记录数算法思想：算法思想：在哈希表上进行查找的过程和哈希造表的过程一致。给在哈希表上进行查找的过程和哈希造表的过程一致。给定定K K值，根据造表时设定的哈西函数求得哈希地址，若表中此位置上没有值，根据

31、造表时设定的哈西函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若何给定值相等，则查找成功；记录，则查找不成功；否则比较关键字，若何给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找否则根据造表时设定的处理冲突的方法找“下一地址下一地址”，直至哈希表中某，直至哈希表中某个位置为个位置为“空空”或者表中所填记录的关键字等于给定值时为止。或者表中所填记录的关键字等于给定值时为止。结论：结论：l 由于产生“冲突”，查找过程仍是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度作为衡量散列表的查找效率的量度。l 查找过程中比较个数取决于因素：散列函数、解决冲突

32、的方法和散列表的装填因子。装填因子装填因子定义：=越小，发生冲突的可能性就越小；越大，发生冲突的可能性就越大。60本章本章总结总结 本章主要介绍了数据处理中的几种典型的查找方法、及几种典型的查找方法、及实现算法和各种查找方法的性能分析实现算法和各种查找方法的性能分析。查找：查找：指在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素（或记录）。查找过程：查找过程：是数据处理的一个环节，它的下一环节是对查找到的结果进行处理，根据所做的操作的不同根据所做的操作的不同，将查找方法分为静态查找静态查找和动态查找动态查找。静态查找方法介绍了顺序查找、二分查找和分块查找三种方法。动态查找方

33、法介绍了二叉排序树查找和二叉平衡树查找。61 顺序查找顺序查找既适用于顺序表，也适用与单链表，时间复时间复杂度是杂度是O（n），），平均查找长度为（平均查找长度为（n+1）/2。折半查找折半查找只适用于顺序存储的有序表顺序存储的有序表。折半查找的时的时间复杂度为间复杂度为O（log2n）。折半查找的查找过程可以画成一棵二叉判定树二叉判定树，它是一棵二叉排序树是一棵二叉排序树。分块查找过程分为两部分：分块查找过程分为两部分：先在索引表索引表中查找；然后在主表的对应块主表的对应块中顺序查找。二叉排序树查找二叉排序树查找：根据二叉排序树的定义根据二叉排序树的定义，首先访问根结点，若其值等于给定值则查

34、找成功；若给定值比根结点大，继续向右子树中查找；否则给定值比根结点小，继续在左子树中查找，直到找到该结点或找不到为止，此时查找失败。62 二叉平衡树的BFBF的值只可能为的值只可能为1 1、0 0和和1 1。二叉平衡树的构造过程中进行调整的方法共有四种。二叉平衡树的查找过程也与二叉排序树类似，从根结点开始，向左或右子树进行查找。散列存储是一种存储方法，也是一种查找方法散列存储是一种存储方法，也是一种查找方法。散列存储通过对元素的关键字按给定函数进行计算，得到存储地址，此地址称为散列地址散列地址，用于计算地址的给定函数称为散列函数散列函数，用于存储元素的地址空间称为散列表散列表。构造散列函数方法

35、有直接定址法、数字分析法、平均取中法、直接定址法、数字分析法、平均取中法、折叠法和除留余数法折叠法和除留余数法。常用的解决冲突的方法常用的解决冲突的方法有开放定址有开放定址法、链地址法法、链地址法。平均查找长度等于平均查找长度等于查找每个元素时的比较次数之和除以所有元素的个数。63习题：习题：1.请指出在顺序表请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用拆半法查找关键码中，用拆半法查找关键码12需做需做多少次关键码比较。多少次关键码比较。（）（）A.2 B.3 C.4 D.5 答案是C。第一次和15比较；第二次和7比较；第三次和10比较；第四次和14比较;比较

36、后结束，没找到。642.对一棵查找树根结点而言，左子树中所有结点与对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是右子树中所有结点的关键字大小关系是()A、小于小于 B、大于大于 C、等于、等于、D、不小于不小于答案是A653.在一棵空的二叉查找树中依次插入关键字序列为在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、5、1，29，请画出所，请画出所得到的二叉查找树。得到的二叉查找树。664.为什么有序的单链表不能进行折半查找为什么有序的单链表不能进行折半查找?答：因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。5.5.将二叉排序树将二叉排序树T T的先序序列中的关键字依次插入一空树的先序序列中的关键字依次插入一空树中，所得二叉排序树中，所得二叉排序树TT与与T T是否相同是否相同?为什么为什么?答：这两棵二叉树完全相同。建立二叉排序树，每棵子树都是从上到下的建立过程；先序输出顺序：根，左，右。总是先输出根结点。它每棵子树的输出顺序也是从上到下的顺序。对二叉排序树来说用任何一种从上到下的输出序列，来构造二叉排序树形状都是相同的。例如二叉树的层序遍历序列。67