|
|
|
|
知识点：
二叉树的应用
查找
折半查找
|
|
关键词：
二分查找
章/节：
常用数据结构
|
|
|
|
|
|
|
|
对于给定的关键字有序序列5,10,13,25,33,40,47,52,61,72，进行二分查找（即折半查找）时，查找过程中的关键字比较序列不可能为( ) 。
|
|
|
|
|
| A.
33,10,5
|
|
|
| B.
33,52,40,47
|
|
|
| C.
33, 13, 5
|
|
|
| D.
33, 52, 61,72
|
|
|
|
|
|
|
|
| |
|
为保障您的权益，请登录
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
二叉树运算是数据结构的重要内容，为加深对二叉树内容的理解，这里给出一些应用实例。为方便描述，二叉树的顺序存储结构用一维数组R表示，而二叉链表的节点存储结构定义如下：
|
|
|
|
|
|
（1）以二叉链表为存储结构，写一个算法用括号形式（key, LT, RT）打印二叉树，其中key是根节点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一个节点x的树打印形式是x，而不应是（X,）的形式。相应的算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
将已知二叉树改建为中序线序树算法的主要思路是：对二叉树进行中序遍历，若当前被访问节点的左子节点指针为空，则让它指向当前节点的前驱节点；若其前驱节点的右子节点指针为空，则让它指向当前节点。相应的算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
|
|
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
折半查找也称为二分查找，其基本思想是：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（表明查找不成功）为止。
|
|
|
|
设查找表的元素存储在一维数组r［1..n］中，那么在表中的元素已经按关键字递增（或递减）排序的情况下，进行折半查找的方法是：首先比较key值与表r中间位置（下标为mid）的记录的关键字，若相等，则查找成功。若key>r［mid］.key，则说明待查记录只可能在后半个子表r［mid+1..n］中，下一步应在后半个子表中再进行折半查找；若keyr的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。
|
|
|
|
【函数】设有一个整型数组中的元素是按非递减的方式排列的，在其中进行折半查找的算法如下：
|
|
|
|
|
|
折半查找的过程可以用一棵二叉树描述，方法是：以当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树上的结点，这样构造的二叉树称为折半查找判定树。例如，具有11个结点的折半查找判定树如下图所示，结点中的数字表示元素的序号。
|
|
|
|
|
|
|
从折半查找判定树可以看出，查找成功时，折半查找的过程恰好走了一条从根结点到被查结点的路径，关键字进行比较的次数即为被查找结点在树中的层数。因此，折半查找在查找成功时进行比较的关键字数最多不超过树的高度，而具有n个结点的判定树的高度为 ，所以折半查找在查找成功时和给定值进行比较的关键字个数至多为 。
|
|
|
给判定树中所有结点的空指针域加上一个指向一个方型结点的指针，称这些方型结点为判定树的外部结点（与之相对，称那些圆形结点为内部结点），如下图所示。那么折半查找不成功的过程就是走了一条从根结点到外部结点的路径。和给定值进行比较的关键字个数等于该路径上内部结点个数。因此，折半查找在查找不成功时和给定值进行比较的关键字个数最多也不会超过 。
|
|
|
|
|
|
|
|
那么折半查找的平均查找长度是多少呢？为了方便起见，不妨设结点总数为n=2h-1，则判定树是深度为h=log2（n+1）的满二叉树。在等概率情况下，折半查找的平均查找长度为：
|
|
|
|
|
|
当n值较大时，ASLbs≈log2（n+1）-1。
|
|
|
|
折半查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列。因此，折半查找适用于表不易变动，且又经常进行查找的情况。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
