首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C函数和函数说明,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode (Bitree *r, int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返
阅读下列C函数和函数说明,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode (Bitree *r, int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返
admin
2010-01-15
25
问题
阅读下列C函数和函数说明,将应填入(n)处的字句写在对应栏内。
【说明】
函数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;
}
选项
答案
(1)p &&p->data!=e;或p!=NULL&&p->data!=e或p&&(*p).data!=e (2)p->Lchild或(*p).Lchild (3)p->Rchild或(*p).Rchild (4)p->Lchild或(*p).Lchild (5)pp->Lchid=p或p=(*pp).child
解析
本程序的功能是删除二叉查找树的一个结点。题目中对怎样删除结点有着比较详细的说明。
第1种情况就是删除叶子结点,叶子结点可以直接删除,这一点很好理解,因为叶子结点删除后并不会打乱查找树的顺序。
第2种情况是删除只有一个子结点的结点,只需把其子结点代替父结点即可。若子结点下有子树,子树结构不变。
第3种情况要复杂一点,要用到二叉查找树的一些性质,就是结点右子树的所有结点都大于根结点,左子树所有结点都小于根结点。所以,当删除了有左右子树的结点时,要在左子树找最大的结点,来替换被删结点。
转载请注明原文地址:https://kaotiyun.com/show/w0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在面向对象系统中,对象的属性是()。
“面向对象技术中,类之间共享属性与行为的机制称为()。
对高级语言源程序进行编译时,可发现源程序中的(21)错误。
POP3协议采用(29)模式进行通信,当客户机需要服务时,客户端软件与POP3服务器建立(30)连接。(29)
若某文件系统的目录结构如下图所示,假设用户要访问文件f1.java,且当前工作目录为Program,则该文件的全文件名为(24),其相对路径为(25)。 (25)
某企业生产流水线M共有两位生产者,生产者甲不断地将其工序上加工的半成品放入半成品箱,生产者乙从半成品箱取出继续加工。假设半成品箱可存放n件半成品,采用PV操作实现生产者甲和生产者乙的同步可以设置三个信号量S、S1和S2,其同步模型如下图所示。 信号量
软件工程概念的提出是由于______。A.计算技术的发展B.软件危机的出现C.程序设计方法学的影响D.其他工程科学的影响
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=l;high=n;while(high>low)ifA[low]+A[hig
随机试题
下列属于合并会计内容的有
Thefactoryhasdonegoodhonourtothegovernmentandthepeoplearoundsothatvisitorscometoit______.
肾虚型子宫脱垂最佳选方
目前控制疟疾症状的首选药物是
领导者的主要任务是提供必要的支持以帮助下属达到他们的目标。并确保他们的目标与群体和组织的目标相互配合、协调一致是()的主要观点。
学生的生理负荷可通过脉率来反映,通常测量脉搏的部位是()。
古代阴阳五行说以青龙、白虎、朱雀、玄武四种动物意味神,青龙为()之神。
依次填入下列横线上的词语,恰当的一项是()。东莞市大朗镇行政服务中心已_______网络化运作。目前,如何_______途径和_______服务水平,是需要进一步思考的问题。
我国严格的礼乐制度建立于()。
A、Shewantstohavelunchinthehotel.B、Shewantstoordersomefoodforlunch.C、Shewantstohavebreakfastinherroom.D、S
最新回复
(
0
)