![](https://lstatic.shangxueba.com/jiandati/pc/images/pc_jdt_tittleico.png)
在含有n个结点的二叉排序树中查找某个关键字的结点时,最多进行()次比较。A.n/2B.log2nC.log2n+
在含有n个结点的二叉排序树中查找某个关键字的结点时,最多进行()次比较。
A.n/2
B.log2n
C.log2n+l
D.n
![](https://lstatic.shangxueba.com/jiandati/pc/images/jdt_panel_vip.png)
在含有n个结点的二叉排序树中查找某个关键字的结点时,最多进行()次比较。
A.n/2
B.log2n
C.log2n+l
D.n
A、二叉排序树中,每个结点的关键字都大于等于其左子树中所有结点关键字,都小于其右子树中所有结点关键字
B、二叉排序树中,每个结点的关键字都小于等于其左子树中所有结点关键字,都大于其右子树中所有结点关键字
C、二叉排序树中,每个结点的关键字都小于等于其左右孩子关键字
D、二叉排序树中,每个结点的关键字大于等于其左孩子关键字,都小于其右孩子关键字
A.2,252,401,398,330,344,397,363
B.924,220,911,244,898,258,362,363
C.925,202,911,240,912,245,363
D.2,399,387,219,266,382,381,278,363
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:
●若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;
●若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
typedefstructBiTnode{
intkey_value;/*结点的键值,为非负整数*/
structBiTnode*left,*right;/*结点的左、右子树指针*/
}*BSTree;
函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。
【函数】
BSTreefind_key(BSTreeroot,intkey)
{
if((1))
returnNULL;
else
if(key==root->key_value)
return(2);
elseif(keykey_value)
return(3);
else
return(4);
}
【问题1】
请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。
【问题2】
若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于(5).
【说明】
函数DeleteNode (Bitree *r, int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查找树结点的类型定义为:
typedef struct Tnode{
int data; /*结点的键值*/
struct Tnode *Lchild, *Rchild; /*指向左、右子树的指针*/
}*Bitree:
在二叉查找树上删除一个结点时,要考虑3种情况:
①若待删除的结点p是叶子结点,则直接删除该结点;
②若待删除的结点p只有一个子结点,则将这个子结点与待删除结点的父结点直接连接,然后删除结点p;
③若待删除的结点p有两个子结点,则在其左子树上,用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值,然后删除结点s,结点s必属于上述①、②情况之一。
【函数】
int DeleteNode (Bitree *r,int e) {
Bitree p=*r,pp,s,c;
while ((1) ){ /*从树根结点出发查找键值为e的结点*/
pp=p;
if(e<p->data) p=p->Lchild;
else p=p->Rchild;
}
if(!P) return-1; /*查找失败*/
if(p->Lchild && p->Rchild) {/*处理情况③*/
s=(2);pp=p
while (3) {pp=s;s=s->Rchild;}
p->data=s->data; p=s;
}
/*处理情况①、②*/
if ((4) ) c=p->Lchild;
else c=p->Rchild;
if(p==*r) *r=c;
else if ((5) ) pp->Lchild=c;
else pp->Rchild=c;
free (p);
return 0;
}
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!