查找二叉树用折半查找法,该方法优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
构建二叉搜索树的时候,把n个数据插入并维护它二叉搜索的特性时间复杂度是 n*log(n),中序遍历n,所以最终时间复杂度是n*log(n)+n,即O(n*log(n))。因为要新开一个存储结构存二叉搜索树,所以空间复杂度是O(n).
(是,如果有左子树 则查询左子树,如果没左子树,但是有右边子树则查询右子树木..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