二叉树查找问题

二叉树查找问题

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

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

构建二叉搜索树的时候，把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)，情况属实，我们会第一时间予以删除，并同时向您表示歉意,谢谢!