折半查找的判定树怎么生成的？

折半查找的判定树怎么生成的~

根是中点下标
左子树是从起点到中点前一个（也就是前面一半）序列折半查找的判定树
右子树是从中点下一个到终点（也就是后面一半）序列折半查找的判定树

长度为n的折半查找判定树的构造方法为：
⑴ 当n=0时，折半查找判定树为空；
⑵ 当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

题目中 长度为10的折半查找判定树的具体生成过程为：
⑴ 在长度为10的有序表中进行折半查找，不论查找哪个记录，都必须先和中间记录进行比较，而中间记录的序号为(1+10)/2=5（注意是整除即向下取整），即判定树的根结点是5，如图(a)所示；

⑵ 考虑判定树的左子树，即将查找区间调整到左半区，此时的查找区间是[1，4]，也就是说，左分支上为根结点的值减1，代表查找区间的高端high，此时，根结点的左孩子是(1+4)/2=2，如图(b)所示；

⑶ 考虑判定树的右子树，即将查找区间调整到右半区，此时的查找区间是[6，10]，也就是说，右分支上为根结点的值加1，代表查找区间的低端low，此时，根结点的右孩子是(6+10)/2=8，如图(c)所示；

⑷ 重复⑵⑶步，依次确定每个结点的左右孩子，如图(d)所示。

按照比较的次数生成判定树，比较1次的是根结点，比较2次的在第二层，比较3次的在第三层，......一次类推，也可以说是每次的mid即形成判定树的结点，左子树上的结点是有序表前半部分的所有结点，右子树是后半部分的结点。

使用判定树进行描述时，应该从问题的文字描述中分清哪些是判定条件，哪些是判定的决策，根据描述材料中的联结词找出判定条件的从属关系、并列关系、选择关系，根据它们构造判定树。

扩展资料：

折半查找法的优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

传统的加倍折半法主要应用于线段（或角）倍半关系的证明。随着“方法”的引申，其功能也随之得到了增强。它的用途远远超出了原先的范围，几乎适用于所有含“2”的类型题。下面，分“结论中含有2”和“题设中含有2”两中情况作简单的介绍。

计算机编程中经常使用到二分法进行比大小、数据查找等操作的程序编写，即将所需要进行处理的数据分成两部分，然后在其中一部分中进行类比查询，如果没有就将另一部分进行拆分，选其中一半进行查询，依次进行，直到得出结果；

分段查找法与此类似，先对数据进行拆分，然后根据处理能力对其中一部分进行查询，如果有，则查询结束，如果没有，对剩余部分进行继续拆分查找。

参考资料来源：百度百科--判定树

参考资料来源：百度百科--折半查找法

按照比较的次数生成判定树，比较1次的是根结点，比较2次的在第二层，比较3次的在第三层，......一次类推，也可以说是每次的mid即形成判定树的结点，左子树上的结点是有序表前半部分的所有结点，右子树是后半部分的结点。

使用判定树进行描述时，应该从问题的文字描述中分清哪些是判定条件，哪些是判定的决策，根据描述材料中的联结词找出判定条件的从属关系、并列关系、选择关系，根据它们构造判定树。

扩展资料：

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

传统的加倍折半法主要应用于线段（或角）倍半关系的证明。随着“方法”的引申，其功能也随之得到了增强。特别是完全领会了加倍折半法的基本思想后，许多疑难问题就会迎刃而解。

参考资料来源：百度百科——折半查找法

参考资料来源：百度百科——判定树

按照比较的次数生成判定树，比较1次的是根结点，比较2次的在第二层，比较3次的在第三层，......一次类推，也可以说是每次的mid即形成判定树的结点，左子树上的结点是有序表前半部分的所有结点，右子树是后半部分的结点。

可以看下这个，还不错～～http://wk.baidu.com/view/d2f67d8083d049649b6658e9?pcf=2#page/1/1409832667566

画出在递增有序表A[21]中进行折半查找的判定树

---

右江区13422639623： 二叉排序树的构造与查找 - ？
容聪天福： 一样的,折半查找树是二叉判定树,跟二叉排序树是不同的

右江区13422639623： 数据结构怎样折半查找? - ？
容聪天福： 举个例子说明吧,在下面一堆数中找数字2 编写代码是先定义3个int类型的变量m,f,l, 初始时,将f==1的地址,l==7的地址,m=(f+l)/2 先遍历m处的数据,它大于2,说明2在它的左边,这个时候将l的值改一下,改成l=m-1(为什么呢?因为你把l改...

右江区13422639623： 数据结构折半查找 - ？
容聪天福： 这个答案不太全吧,查找长度为5的序列不是只有两个数,如果说下标的起点和终点才是两个数,以下开始按起点和终点来确定 首先需要判断起点下标是0还是1 如果是1,合法下标范围是1..17,第一次折半查找查找的下标是(1+17)/2 = 9;如...

右江区13422639623： 画出对{10,15,19,21,29,32}进行折半查找20的过程 - ？
容聪天福： 设下标起点为1,则表长为6的折半查找的判定树如下: 3 / \1 5 \ / \2 4 6 按下标换成关键字就是这样: 19 / \10 29 \ / \15 21 32 这样查找20的过程就是:首先比较19 然后比较29 再比较21,查找失败,比较3次

右江区13422639623： 【求解大计基题目】对于下列数据,给出折半查找数据89的操作步骤: - 100 - 1 2 3 7 15 89 - ？
容聪天福：[答案] 显然折半查找的表长为7,依次查找3、15 、89 具体过程构造一颗结点为7的判定树就可以清楚地看到了

右江区13422639623： 有关键字递增的数组A【30】,按折半查找进行查找,查找程度为5的元素个数为15,对不对?这类题怎么做. - ？
容聪天福： 构造折半查找的判定树就可以了 第1层1个结点 第2层2个结点 第3层4个结点 第4层8个结点,共计1+2 + 4 + 8 = 15 剩余30-15 = 15在第5层,也就是说比较次数为5次,因此答案正确

右江区13422639623： 如何计算折半查找的平均查找长度 (T - T!) - ？
容聪天福：[答案] 如果你是要求给定的一组有序的记录关键字序列的话,例如{13,18,24,35,47,50,62,83,90}.你要先求出其折半查找判定树.{47(18(13,24( ,35)),62(50,83( ,90)))}.这树你可以还原吧.所以平均查找长度为( 1*1+2*2+3*4+4*2)/9=25/9,只看每一层的结点数....

右江区13422639623： 折半查找问题(数据结构) - ？
容聪天福： 34:2次56:1次58:3次63:4次94:4次

右江区13422639623： c语言中的折半查找法是什么原理? - ？
容聪天福： 递归,分治,思想将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止.如果xa[n/2],则我们只要在数组a的右半部继续搜索x.

右江区13422639623： 数据结构的折半查找怎么回事 - ？
容聪天福： 举个例子吧,折半查找的前提是数据以及按升序或降序排列,比如1,2,3,4,5,6,7,8,9,10,如过让你找出3,折半查找的过程如下: n=3;//要查找的数字 num=10;//升序排列的数字最大值 num1=0;//升序排列的数字最小值 if(nnum=num/2;//在num的前半部分找,后半部分都是比n大的 else num1=num/2;//在num的后半部分找,前半部分都是比n小的 然后就继续迭代 大概就是这个意思,你看看能不能理解,我是这样理解的