返回
首页>资讯

二叉树查找问题

时间: 2023-03-30 14:31:49

二叉树查找问题

查找二叉树用折半查找法,该方法优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

利用搜索二叉树(查找二叉树)的中序遍历排序的问题

构建二叉搜索树的时候,把n个数据插入并维护它二叉搜索的特性时间复杂度是 n*log(n),中序遍历n,所以最终时间复杂度是n*log(n)+n,即O(n*log(n))。因为要新开一个存储结构存二叉搜索树,所以空间复杂度是O(n).

书上有个例题看不懂啊,二叉树查找数据元素,C高手帮帮忙O_O (菜鸟在线)

(是,如果有左子树 则查询左子树,如果没左子树,但是有右边子树则查询右子树木..2个都没有,则返回null)
但是一个查询程序应该不应该return ,因为return 的话 就会当左子树查询不到,则返回null,就不会在继续查询了
所以不用return 那么这个程序应该算中序遍历.
中(根) 左 右 这样的顺序就是中序遍历;
这样程序就变成..
1,设第一次进入这个函数 传入根节点 ,他先判断这个根节点是否 符合要求?符合 返回点:不符合 进入步骤2
2,当根节点不符合要求,判断其是否含有左孩子,如果有 传入左子树根节点(就是其左孩子).重新进入步骤1;如果上面 左孩子为空 进入步骤3
3,当根节点不符合要求 其左孩子不符合要求 则判断其右孩子,其右孩子如果不为空,传入右子树根节点(就是其右孩子).重新进入步骤1;如果上面右孩子为空,则进入步骤4
4,当以上的所有都不符合要求 意味,以此为根节点的子树找不到合适的数字,(但是不能否认所有子数都没有符合要求的结果)

关于二叉树的建立和输出查找,有例题。

// c
#include <stdio.h>
#include <malloc.h>
typedef struct node
{
    int x;
    struct node *l, *r;
}node;
node * newnode(int x)
{
    node *t = (node *)malloc(sizeof(node));
    t->x = x;
    t->l = t->r = NULL;
    return t;
}
int main()
{
    int N, x;
    char dir;
    node *Tree = NULL, *p, *q;
    scanf("%d", &N);
    while(N--)
    {
        scanf("%d", &x);
        if(Tree == NULL)
        {
            Tree = newnode(x);
            continue;
        }
        p = q = Tree;
        while(p)
        {
            q = p;
            if(x > p->x)
                p = p->r;
            else
                p = p->l;
        }
        if(x > q->x)
            q->r = newnode(x);
        else
            q->l = newnode(x);
    }
       
    p = Tree;
    scanf("%d", &N);
    fflush(stdin);
    while(N--)
    {
        scanf("%c", &dir);
        if(dir == 'L')
            p = p->l;
        else
            p = p->r;
    }
    printf("%d", p->x);
}

声明: 我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理,本站部分文字与图片资源来自于网络,转载是出于传递更多信息之目的,若有来源标注错误或侵犯了您的合法权益,请立即通知我们(管理员邮箱:daokedao3713@qq.com),情况属实,我们会第一时间予以删除,并同时向您表示歉意,谢谢!

猜你喜欢

本站内容仅供参考,不作为诊断及医疗依据,如有医疗需求,请务必前往正规医院就诊
祝由网所有文章及资料均为作者提供或网友推荐收集整理而来,仅供爱好者学习和研究使用,版权归原作者所有。
如本站内容有侵犯您的合法权益,请和我们取得联系,我们将立即改正或删除。
Copyright © 2022-2023 祝由师网 版权所有

邮箱:daokedao3713@qq.com

备案号:鲁ICP备2022001955号-4

网站地图