首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
[函数] int DeleteNode(Bitree *r,int e){ Bitree p=* r,pp,s,c; while((1)){/ * 从树根结点出发查找键值为e的结点 * /
[函数] int DeleteNode(Bitree *r,int e){ Bitree p=* r,pp,s,c; while((1)){/ * 从树根结点出发查找键值为e的结点 * /
admin
2005-03-15
100
问题
[函数]
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->dara=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&&(*p).data!=e (2)p->Lchild或(*P).Lchild (3)s->Rchild或(*s).Rchild (4)p->Lchild或(*p).Lchild (5)p==pp->Lchild或p==(*PP).Lchild
解析
本程序的功能是删除二叉查找树的一个结点。二叉查找树又称二叉排序树(binary sort tree)。一棵二叉查找树或者是一棵空树,应满足以下递归条件:
①查找树的左、右子树各是一棵查找树。
②若查找树的左子树非空,则其左子树上的各结点值均小于根结点的值。
③若查找树的右子树非空,则其右子树上的各结点值均大于根结点的值。
例如,图4-8就是一棵二叉查找树。
题目中对怎样删除结点做了比较详细的说明。
第一种情况是删除叶子结点。叶子结点可以直接删除,这点很好理解,因为叶子结点删除后并不会打乱查找树的顺序,也就是说把图4-8中的“20”结点删除,剩下的还是一棵查找树。
第二种情况是删除只有1个子结点的结点,只需把其子结点代替父结点即可,也就是说若要删除图4-8中的“56”结点,只需把“51”移至“56”位置即可,若“51”下有子树,子树结构不变。
第三种情况要复杂一点,要用到二叉查找树的一些性质,就是结点右子树的所有结点都大于根结点,左子树所有结点都小于根结点。所以,当删除有左右子树的结点时,要在左子树找最大的结点来替换被删结点。也就是说若要删除图4-8中的“89”结点,首先要把“56”搬到“89”的位置,然后用第二种情况规则,把“51”调整到原来56的位置。
以下具体分析程序。
第一句是变量的声明以及赋初值,p指向二叉查找树的根。接下来是一个循环,从注释部分可以知道,此循环的功能是查找键值为e的结点。循环内有判断条件,当e<p-> data时,进入左子树查找,否则到右子树中查找。很明显没有关于找到结点的处理代码,也就是说循环内部只处理了没找到结点的情况,所以循环条件应是当找到键值为e的结点时退出循环。同时应注意一个隐含的限制条件,就是当p=NULL时,表示已经查找完毕,也不用进入循环了。所以(1)空应填p && p->data !=e。
接下来的if程序段是处理第③种情况的。由循环中的“s=s->Rchild;”可以看出,s用在要删结点的左子树中查找键值最大的结点。所以s的初值应是要删除结点的左子结点。所以,(2)空应填p->Lchild。
结合前面提到的对第③条规则的描述以及二叉查找树的规则可知,要找的结点s应是左子树最右的结点,即右子结点为NULL的结点。所以(3)空应填S->Rchild。
接着对①、②处理。这里并没有把①、②处理分开进行,而是合在一起进行处理。这里引入了一个中间变量c,用c来存储用于替换p的结点。
现在分析怎样的条件可以使这2种情况合在一起。因为当要删除的结点为叶子结点时,p->Lchild与p->Rchild都为NULL;当要删除的结点有1个子结点时,如果有左子结点,则p->Rchild为NULL;如果有右子结点,则p->Lchild为NULL。所以当 p->Lchild不为NULL时,说明是第二种情况,p结点含左子结点,c=p->Lchild。当 p->Lchild为NULL时,说明有2种可能:第一,p->Rchild也为NULL,则p是叶子结点;第二,p->Rchild不为NULL,则P是有右子结点的结点。但这2种情况都可以用c=p->Rchild,因为当p是叶子结点的时候用NULL代替p的位置即可,所以(4)空应填p->Lchild。在程序中很多地方都用到了变量pp。pp一直指向的是p结点的前一个结点,即p的父结点,所以(5)空的作用是判断p是其父结点的左子结点还是右子结点,即(5)空应填pp->Lchild=p。
转载请注明原文地址:https://kaotiyun.com/show/VyDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某飞行器供油阀控制软件通过控制左右两边的油箱BL、BR向左右发动机EL、ER供油,既要保证飞行器的安全飞行,又要保证飞行器的平衡,该软件主要完成的功能如下:(1)无故障情况下
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某飞行器供油阀控制软件通过控制左右两边的油箱BL、BR向左右发动机EL、ER供油,既要保证飞行器的安全飞行,又要保证飞行器的平衡,该软件主要完成的功能如下:(1)无故障情况下
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某公司欲开发一款二手车物流系统,以有效提升物流成交效率。该系统的主要功能是:(1)订单管理:帮买顾问看到有买车线索后,会打电话询问买家是不是需要物流,若需要,帮买顾问就将这个线索发起为订单,
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某航空公司进行促销活动,会员在指定日期范围内搭乘航班将获得一定奖励,奖励分为4个档次,由乘机次数和点数共同决定,如表2-1所示。其中点数跟票面价格和购票渠道有关,规则如表2-2所示。航空公
阅读下列C程序,回答问题,将解答填入答题纸的对应栏内。【C程序】intisbinary(constvoid*buf,constsizetbuf—fen){sizetsuspiciousbytes=0;sizettotal—by
两个公司希望通过Internet进行安全通信,保证从信息源到目的地之间的数据传输以密文形式出现,而且公司不希望由于在传输节点使用特殊的安全单元而增加开支,最合适的加密方式是(10),使用的会话密钥算法应该是(11)。
在GB/T 17544中,软件包质量要求包括三部分,即产品描述要求、(53)、程序和数据要求。
下列测试工具中,使用(68)执行自动化负载压力测试,使用(69)执行代码静态结构分析,使用(70)执行网络测试。
某供应商数据库中的供应关系为SPJ(供应商号,零件号,工担号,数量),如下命令查询某工程至少用了3家供应商(包含3家)供应的零件的平均数量,并按工程号的降序排列。SELECT工程号,(14)FROMSPJGROUPBY工程号(15)
以下各项中,(51)属于需求说明书的评测内容。①系统定义的目标是否与用户的要求一致②设计的约束条件或限制条件是否符合实际③是否考虑过软件需求的其他方案④软件的行为与它必须处理的信息、必须完成的功能是否一致
随机试题
典型房扑的心房率为
静脉注射毛花苷丙,24小时总量为
房地产抵押是抵押人用其合法的房地产以()的方式向抵押权人提供债务履行担保的行为。
人民法院对第二审案件的审理,在下列表述中,正确的有()。
下列属于对账的主要内容有()
2015年1月,甲公司与乙公司签订劳务派遣协议,派遣刘某到乙公司从事临时性工作。2015年5月,临时性工作结束,两公司未再给刘某安排工作,也未再向其支付任何报酬。2015年7月,刘某得知自2015年1月被派遣以来,两公司均未为其缴纳社会保险费,遂提出解除劳
白细胞与机体保护、防御等功能有关。下列哪一项不是白细胞存在的位置?()
血浆包括各种矿物质、糖类、脂类、蛋白质、激素和维生素等。在上述各种物质巾,造成血液颜色为红色的是:
当炫耀式旅游成了目的,扎堆往知名景点挤,也就在意料之中。其实旅游作为一种现代的生活方式,可以有多样化的功能。如果是为了教育,可以带孩子去看看名山大川、古城遗迹,帮助他们了解国家的历史和文化传统;如果是为了休闲放松。可以去海边、深山、或者就近选择市郊的农家小
分析下列短语的结构层次和结构关系。许多朋友送来的礼物
最新回复
(
0
)