精华内容
下载资源
问答
  • 折半查找判定树判断
    千次阅读
    2022-04-19 16:41:57

    折半查找判定树画法思路:

    1.先画出满足有序表长度的最大满二叉树,然后将剩余结点个数一个个插入该树。【二叉树前n层最多(2^n)-1个结点,第n层最多2^(n-1)个结点】

    2,从上往下看,比较每个结点左右节点个数,如果左右子树结点个数相同则优先放右边,左边比右边少就放左边,直到往下塞到二叉树底部成为叶子结点。

    更多相关内容
  • 折半查找        也被称作二分查找,即将需要查找的元素与数组中间的元素进行比较;若比中间的元素小,则再与...下面主要介绍如何快速判断树是否为折半查找判定树   &nb

    折半查找

           也被称作二分查找,即将需要查找的元素与数组中间的元素进行比较;若比中间的元素小,则再与前子表的中间元素进行比较,以此类推直至查找到所需查找元素,或者所需查找元素不在此表中。

    折半查找判定树(此树必为平衡树)

           即由折半查找过程中所产生的树,首尾除以二取整。

    下面主要介绍如何快速判断树是否为折半查找判定树

           以2017年408中的选择真题为例:
           下列二叉树中,可能成为折半查找判定树(不含外部节点)的是(__)。
    在这里插入图片描述
    【分析】:首先折半查找判断树是执行折半查找过程中形成的树,那么他的子树有着相同的结构。

    • 当表中元素个数为偶数个时,那么折半所产生的子表中,必然会出现两种情况:①前子表比后子表多一个元素;②后子表比前子表多一个元素;那么以这种结构推其后所有的子表应均满足此结构。
    • 当表中元素个数为奇数个时,那么折半所产生的子表中,只会产生一种情况,即前后子表元素个数相同,那么以这种结构推其后所有的子表应均满足此结构。
    • 若二叉树出现例如上题中BC此类关于根节点对称的结构,那么它一定不是折半查找二叉树。

    基于上述三点即可以快速看出本题答案为A。至于D选项为何错误,读者可以自行分析便可轻易知晓。

    展开全文
  • 2017的真题,或者用这个性质去做,或者根据判定树的构造方法去做,即,先标好中序遍历的次序,然后去看每次生成的新节点是不是都遵循相同的生成规则。通过defineUPPERBOUND和LOWERBOUND可以绘制向上取整、向下取整的...

    编译器: std=c++14 or higher;环境:Mac OS X (M1 Core);
    通过define UPPERBOUND和LOWERBOUND可以绘制向上取整、向下取整的判定树。
    和王道所讲的规律是一致的;
    2017的真题,或者用这个性质去做,或者根据判定树的构造方法去做,即,先标好中序遍历的次序,然后去看每次生成的新节点是不是都遵循相同的生成规则。
    Lowerbound的例子

    #include <iostream>
    #include <vector>
    using namespace std;
    #define UPPERBOUND
    const int N = 1005;
    
    int lchild[N], rchild[N];
    
    int draw(int l, int r) {
    	if (l > r) return -1;
    	if (l == r) return l;
    	#ifdef UPPERBOUND
    	int mid = (l + r + 1) >> 1;
    	#endif
    
    	#ifdef LOWERBOUND
    	int mid = (l + r) >> 1;
    	#endif
    	int L = draw(l, mid - 1), R = draw(mid + 1, r);
    	if (L != -1)
    		lchild[mid + 1] = L + 1;
    	if (R != -1)
    		rchild[mid + 1] = R + 1;
    	//printf("%d, %d, %d\n", L + 1, mid + 1, R + 1);
    	return mid;
    }
    
    vector<pair<int, int>> ret;
    
    int dfs(int u, int depth, int ind) {
    	int p = 0;
    	if (lchild[u]) {
    		p = max(p, dfs(lchild[u], depth + 1, ind * 2 - 1));
    	} else {
    		ret.push_back({depth + 1, ind * 2 - 1});
    	}
    	if (rchild[u]) {
    		p = max(p, dfs(rchild[u], depth + 1, ind * 2));
    	} else {
    		ret.push_back({depth + 1, ind * 2});
    	}
    	//cout << u << ' ' << p << endl;
    	return p + 1;
    }
    
    typedef short unsigned int hu;
    enum { M = 10 };
    
    //中间这一段输出是抄的洛谷输出二叉树的题解
    
    int k,n,m,p,x,y;
    char c[800][1600];
    bool f[800][1600];//在第x,y点,a,b是用来判节点的,k表示点还是边,xx,yy表示这个点或这个边的父亲
    
    void dfs1(int x,int y,int a,int b,int k,int xx,int yy){
        if(x==n){c[x][y]='o';return;}
        if(k==1){
            c[x][y]='o';
            int X=xx+1,Y=(yy-1)*2+1;//左儿子
            if(!f[X][Y])dfs1(x+1,y-1,a+1,b,2,X,Y);
            X=xx+1,Y=yy*2;//又儿子
            if(!f[X][Y])dfs1(x+1,y+1,a+1,b,3,X,Y);
        }else
        if(k==2){
            c[x][y]='/';
            if(a*2==b)dfs1(x+1,y-1,1,a,1,xx,yy);//这个就是判断接下来是边还是点
            else    dfs1(x+1,y-1,a+1,b,2,xx,yy);
        }else
        if(k==3){
            c[x][y]=92;
            if(a*2==b)dfs1(x+1,y+1,1,a,1,xx,yy);
            else    dfs1(x+1,y+1,a+1,b,3,xx,yy);
        }
    }
    void make(int k){
        n=3;
        for(int i=3;i<=k;i++)n*=2;
        m=6*(1<<(k-2))-1;//计算画布大小
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)c[i][j]=' ';//填充画布
        dfs1(1,m/2+1,1,n,1,1,1);
    }
    
    void toTerminal(vector<pair<int, int>> got) {
    	memset(f, 0, sizeof f);
    	memset(c, 0, sizeof c);
    	for (int i = 0; i < p; i ++) {
    		int x = got[i].first, y = got[i].second;
    		f[x][y] = 1;
    	}
    	if(k==1)n=m=1,c[1][1]='o';else make(k);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)cout<<c[i][j];cout<<endl;
        }
    }
    
    int main() {
    	for (int i = 1; i < 50; i ++) {
    		memset(lchild, 0, sizeof lchild);
    		memset(rchild, 0, sizeof rchild);
    		int root = draw(0, i - 1) + 1;
    		ret.clear();
    		int depth = dfs(root, 1, 1);
    		int ans = 0;
    		for (auto [a, b]: ret) {
    			if (a <= depth)
    				ans ++;
    		}
    		k = depth, p = ans;
    		vector<pair<int, int>> gotcha;
    		for (auto [a, b]: ret) {
    			if (a > depth)
    				continue;
    			gotcha.push_back({a, b});
    		}
    		printf("Case %d:: \n", i);
    		toTerminal(gotcha);
    	}
    }
    
    展开全文
  • 折半查找判定树

    千次阅读 2019-12-02 20:04:22
    通常称这个描述折半查找过程的二叉树为折半查找判定树,简称判定。 判定的构造方法 ⑴ 当n=0时,折半查找判定树为空; ⑵ 当n>0时, 折半查找判定树的根结点为mid=(n+1)/2, 根结点的左子树是与有序表r...

    判定树:折半查找的过程可以用二叉树来描述
    树中的每个结点对应有序表中的一个记录
    结点的值为该记录在表中的位置
    通常称这个描述折半查找过程的二叉树为折半查找判定树,简称判定树。

     

    判定树的构造方法

    ⑴ 当n=0时,折半查找判定树为空;
    ⑵ 当n>0时,
        折半查找判定树的根结点为mid=(n+1)/2,
        根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树,
        根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

     

    判定树的特点

    • 任意两棵折半查找判定树,若它们的结点个数相同,则它们的结构完全相同

    • 具有n个结点的折半查找树的高度为

     

    判定树的性质

    • 任意结点的左右子树中结点个数最多相差1

    • 任意结点的左右子树的高度最多相差1

    • 任意两个叶子所处的层次最多相差1

     

     

    展开全文
  • 折半查找判定树

    千次阅读 2020-12-20 20:27:31
    转载自博客 首先折半查找判定树一定是一颗AVL平衡 其次折半查找过程中mid=(low+high)/2向上取整或向下取整是不能改变的,所以在当查找序列中节点总数是偶数时,必然有一侧比另一侧少一个节点 ...
  • 下列二叉树中,可能成为折半查找判定树的是

    千次阅读 多人点赞 2020-11-21 10:57:34
    这道题考察的是折半查找时中间点的选择,当剩余序列为偶数个时,我们应该向上取整还是向下取整。例如对1,2,3,4四个数进行排序时,应该选2做中间点还是选3做中间点。实际上并没有要求,选哪个都能完成折半查找,...
  • 二叉排序(vs折半查找判定树

    千次阅读 2020-06-21 11:40:35
    二叉排序
  • 折半查找判定树的画法(较简单易懂!)

    万次阅读 多人点赞 2021-06-27 10:40:13
    折半查找判定树的画法思路: 1.先画出满足有序表长度的最大满二叉树,然后将剩下的结点个数一个个插入该 2.从上往下看,比较每个结点的左右子树结点个数,如果左右子树结点个数相同优先放右边,左边比右边少就放...
  • 【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。 判定树如下: 图1-1判定树 ...
  • 折半查找二叉判定树

    千次阅读 多人点赞 2021-04-05 00:51:30
    二叉判定树 又称 二叉排序,是具有以下性质的二叉树: 若左子树不为空,则左子树上各个节点的...已知一个顺序存储是有序表为(15,26,34,39,45,56,58,63,74,6),试画出对应的二叉判定树,求其平均查找长度。 ...
  • 二叉树判断是否为折半查找树 题目 网上有好多教程,看的我很头大。经过朋友的讲解,豁然顿悟。废话不说。 要做对这道题,首先就是先要搞懂折半查找树是怎样的构建的过程,折半查找,顾名思义,就是通过一次次的折半...
  • 假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,...
  • 【数据结构】折半查找及其二叉判定树画法

    万次阅读 多人点赞 2019-09-25 23:55:40
    折半查找又叫二分查找,是数据结构中一种很重要的查找方式。 其特点有以下几个: 只能对有序的顺序表进行查找。 是一种静态查找。 查找的平均时间复杂度为o(log...折半查找和二叉排序查找的平均查找长度均取决...
  • 折半查找判定树及平均查找长度

    万次阅读 多人点赞 2016-01-08 18:16:27
    折半查找判定树及平均查找长度 从折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表继续上述操作。所以,对表中每个记录的查找过程,可用二叉树来描述,二叉树中的每个...
  • 考研之数据结构026_算法查找_折半查找(重要)一、算法思想二、算法实现1、查找效率ASL三、查找判定树(重要)一、特性:2、奇数个数据元素3、 偶数个数据元素:四、折半查找效率 一、算法思想 折半查找:又称“二分...
  • 任意两棵折半查找判定树,若它们的结点个数相同,则它们的结构完全相同 任意结点的左右子树中结点个数最多相差1 任意结点的左右子树的高度最多相差1 任意两个叶子所处的层次最多相差1 完全二叉树:如果二叉树的深度...
  • 查找表的概念 查找表是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。 在查找表中只做查找操作,而不改动表中数据元素,称此类查找表为静态查找表;反之,在查找表中做查找操作的...
  • 【数据结构】顺序查找和折半查找

    千次阅读 多人点赞 2021-04-03 08:07:36
    摘要:在本篇文章中,主要讲述了在数据结构中所涉及的几大查找算法,包括:顺序查找、折半查找、分块查找和散列表查找。这些查找方式都是数据结构中最基本的查找方式,并且在数据结构中运用广泛。在查找算法中,最为...
  • 在这里,我们不妨设折半查找是向下取整的,所以存在: 情况一:当剩余查找个数为偶数的时候,在中表现为对应节点左边的子节点总数比右边子节点总数少一个。例如,在结点1,2,3,4中查找 low=1,high=4 min=2(下...
  • 数据结构(九):查找——顺序查找、折半查找(动图)
  • 示意图 算法分析 折半查找过程可以用一颗二叉判定树来表示,而具有n个结点的判定树的深度为[log2n]+1,所以折半查找法在查找成功和不成功时,与给定值进行比较的关键字个数都不会超过[log2n]+1. 现讨论折半查找算法的...
  • 动态查找表:不仅进行查找操作,而且在查找过程中还伴随着插入(查找的数据元素不在表中时)、删除某个数据元素的操作。 3、关键字(key):是数据元素(或记录)的某个数据项的值,用它可标识(识别)一个数据元素...
  • 折半查找成功时的平均查找长度

    万次阅读 2019-02-14 09:30:30
    /** * 实验题目: * 求折半查找成功时的平均...* 设计程序,建立有序序列R[0...n-1]进行二分查找产生的判断树, * 在此基础上完成如下功能: * 1、输出n=11时的判定树并求成功情况下的平均查找长度ASL。 * 2、通过构...
  • 1.顺序查找 2.折半查找 3.分块查找 4.王道课后题
  • 折半查找与其判别(对于固定个数的n个序列其判定树的形式是固定的) 11个元素的:
  • 查找学习要点

    2020-10-15 10:04:48
    折半查找的过程及性能; 二叉排序的构造及查找; 平衡二叉树的调整; 散列表的构造和查找; 各种查找技术的时间性能及对比。 本章的难点是: 二叉排序的删除操作; 平衡二叉树的调整方法。 本章要以静态查找...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,765
精华内容 706
关键字:

折半查找判定树判断