二叉树 查找 遍历

《二叉树 查找 遍历》由会员分享，可在线阅读，更多相关《二叉树 查找 遍历（67页珍藏版）》请在金锄头文库上搜索。

1、第7章 查找(Search) 7.1 查找基本概念7.2 基于线性表静态查找7.3 基于树表动态查找7.4 哈希查找*1第7章 查找Introduction查找是非数值处理中一种最基本、最重要的操作。查找，也称检索，是一种运算，是软件设计中经常 遇到的一种运算。数据结构不同，查找方法也会不 同。查找方法的好坏直接影响着计算机的使用效率 。查找概述Date2第7章 查找7.1、查找基本概念1）查找 Search：又称检索，是指在大量的数据中寻找关键 字等于给定值的记录。若存在这样一个记录，则称查找成功 ，否则称查找不成功。分为:静态查找;动态查找; 2）关键字 (Keyword)：就是数据元素中

2、可以唯一标识一个 数据元素的数据项。例如：学生管理登记卡中的学号。 3）平均查找长度 (Average Search Length) (ASL)算法评价 :评价时考虑：（1） 速度；（2） 占用存储空间；（3） 复杂程度。Date3第7章 查找引入平均查找长度，作为查找算法评价的依据。平均查找长度：为确定记录在表中的位置所进行的 和关键字比较的次数的期望值，简写为ASL.含有n个元素的表中找一个元素成功的ASL为：Pi为查找第i个元素的概率；Ci为 查到第i个元素所需的比较次数。ASL= Pi Cii=1nDate4第7章 查找结构体数组typedef structchar name10;Ke

3、yType key;DataType;DataType rMaxnum;name0 name9 keyr0r1rMaxnumname0 name9 key设表中记录以顺序存储结构组织。每个记录包括：关键字，其他数据项等。 其类型说明用C语言描述如下：4) 类型说明：Date5第7章 查找5）查找方法: 顺序表静态查找， 树表动态查找，哈希查找7.2、基于线性表的静态查找顺序表上的查找主要有三种方法:顺序查找法:针对顺序表存储结构折半查找法:针对有序顺序表存储结构分块查找:针对索引顺序表存储结构 Date6第7章 查找i=01826322137566475i=1i=5i=4i=3i=2基本思想：

4、从第一个元素开始，将给定值与表 中逐个元素的关键字比较，直至检索成功或直 至最后一个元素检索失败为止。1. 顺序查找：Date7第7章 查找int Seqsearch (DataType r ,int key, int n) int i=0;while ( r i .key != key low=0;high=n-1;while(low rmid.key)low=mid+1;else high=mid-1;returu 1; 算法描述初始化循环条件计算中间下标查找成功前半部分后半部分查找失败Date16第7章 查找int binsearch(DataType r,int n,int key)

5、int low,high,mid;low=0;high=n-1;while(low rmid.key)low=mid+1;else high=mid-1;returu 1; low1826324552668091highmid52 66 80 91lowhighmid80 91highLow mid用折半查找法在顺序表中 查找关键字为80的记录！Date17第7章 查找w假设：查找关键字为0-6的数据折半法算法分析3564102二叉判定树n假设：有序表长度为n,且n2h-1n若n=2h-1 则：查找过程为一棵深度为h的满二叉树,n查找的过程形成二叉判定树nASL=1/7(1+22+43)=2.

6、43Date18第7章 查找比顺序查找效率高 只适用于有序的顺序存储的表，算法特点:ASLlog2(n+1)-1ASL=(1/n)2i-1 i i=1n则满二叉树的第 i 层有2i-1个结点。Date19第7章 查找3. 分块查找（索引顺序表查找）将顺序查找法与折半查找法结合 基本思想：使用分块查找算法时，要求将线性表均匀地 分成若干块，每块的元素不要求有序，但一 定要保证块间有序。另外，对表要进行索引 存储。即新建一个索引表，存放各块中最大 关键字。分块查找实际上是先在索引表中进行顺序查 找或折半查找，再在块内进行顺序查找。Date20第7章 查找索引表类型:1.对单关键字建立索引表:2.对

7、多关键字建立索引表:完全索引表 ,多级索引表.3.分块个数建立索引表:等长,不等长主表索引表主表完全索 引表索引表分块查找的基本过程如下： (1) 首先，将待查关键字K与索引表中的关 键字进行比较，以确定待查记录所在的块。具 体的可用顺序查找法或折半查找法进行。 (2) 进一步用顺序查找法，在相应块内查 找关键字为K的元素。 Date21第7章 查找例如：17 ，8，21，19，31，33，25， 22， 43，37，35, 40，61，78，73，55分块17，8，21，19，31，33，25，22，43，37，35，40, 61，73，78，55索引表：21 33 43 7821 33 4

8、3 78关键字 地址数据表8 2131 33 25436137 3573 781922405517Date22第7章 查找typedef structchar name10;KeyType key; DataType;DataType rMax;typedef structKeyType key;int link; indextype;indextype Lrm索引表结构：顺序表结构：表结构说明：Date23第7章 查找int indexsearch(indextype Lr, DataType r,int key,int L,int m)int i,j;i=0; /*在索引表中顺序查找*/w

9、hile(i=m) return -1;else /*在顺序表中顺序查找*/j=Lri.link;while(key!=rj.key else /*在顺序表中顺序查找*/j=Lri.link;while(key!=rj.key else t-R=insertbt(s,t-R);return t;Date33第7章 查找插入的新结点都是二叉排序树的叶子结 点.不必移动其它结点.常用于有序二叉树 的插入,删除. 对二叉排序树采用中序遍历,其结果为一有序 序列. 根结点的选择,决定二叉树的形状,其形状决定 检索的效率.根结点数据值最好选择元素序列的 中间值.特点:Date34第7章 查找BiTree

10、 *btsearch(BiTree *p, int key) /p指向二叉排序树的根结点 while(p!=NULL)if(key=p-key) return p;else if(keykey)p=p-L;else p=p-R;return NULL;算法描述：结束条件查找成功在左子树中查找在右子树中查找查找失败3. 二叉排序树查找Date35第7章 查找BiTree *btsearch(BiTree *p, int key) /p指向二叉排序树的根结点 while(p!=NULL)if(key=p-key) return p;else if(keykey)p=p-L;else p=p-R;r

11、eturn NULL;1510182118162511p ppp演示：Key=8Date36第7章 查找4. 算法分析ASLlog2(n+1)-1二叉排序树查找与折半法查找类似，与关 键字比较的次数不会超过树的深度。最好情况：二叉排序树为一棵平衡二叉树最坏情况：二叉排序树为一棵单支树，与顺序查找情况相同。(n+1)/2适用于经常 做插入,删 除和查找运 算的表.Date37第7章 查找7.4 哈希查找（散列查找）w前述的查找方法建立在“比较”的基础 上，查找的次数依赖于查找过程中进行比 较的次数。 w问题：能否不用比较就能直接计算出记 录的存储地址，从而找到所要的结点？ -采用散列（hash）

12、方法。Date38第7章 查找1.哈希(散列)表的基本概念w哈希（又称杂凑、散列）的基本思想：以记录的关键字值k为自变量，通过一定的函数关系h计 算出对应的函数值h(k),把这个值解释为记录的存储地址（哈 希地址），将记录存入该地址中去。w函数h-哈希函数 h(k)-哈希地址w基本区-分配给哈希表的连续存储空间。w冲突的概念：若对于不同的键值k1和k2,即k1n。Date41第7章 查找2.几种常用的哈希函数 w（1）直接定址法：当关键字是整型数时，取关键字作为哈希地址。H(k)=k 或H(k)=ak+b （a，b为常数）特点：简单；浪费空间；例：一组关键码：例：一组关键码： 942148,

13、941269, 940527, 941630, 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 941805, 941558, 942047, 940001 。散列函数为散列函数为HH ( (k k) = ) = k k - - 940000 940000则有则有HH (942148) = 2148 (942148) = 2148 HH (941269) = 1269 (941269) = 1269H H (940527) = 527 (940527) = 527 HH (941630) = 1630 (941630

14、) = 1630H H (941805) = 1805 (941805) = 1805 HH (941558) = 1558 (941558) = 1558H H (942047) = 2047 (942047) = 2047 HH (940001) = 1 (940001) = 1Date42第7章 查找u（2）除留余数法：选择一个适当的正整数P，用P去除键值，取其余数作为 散列地址，即：h(k)= k % PP的取法：小于等于哈希表表长 m的最大素数.例如，已知待散列元素为（18,75，60，43，54，90，46）， 表长m=10， p=7， 则有H(18)=18%7=4 H(75)=7

15、5%7=5 H(60)=60%7=4 H(43)=43%7=1 H(54)=54%7=5 H(90)=90%7=6 H(46)=4 冲突较多。为减少冲突，可取较大的m值和p值，如: m=p=13， 结果如下： Date43第7章 查找H(18)=18%13=5 H(75)=75%13=10 H(60)=60%13=8 H(43)=43%13=4 H(54)=54%13=2 H(90)=90%13=12 H(46)=46%13=7 P最好取1.1n1.7n的素数。n例：设 n=7， P=11或13 n则： n=100 P=113,127,139544318466075900 1 2 3 4 5 6 7 8 9 10 11 12 Date44第7章 查找u（3）数字分析法设有设有 n n 个个