首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
[函数] 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
93
问题
[函数]
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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。【说明】某软件的积分计算模块每天定时根据用户发布的文章数、文章阅读数来统计用户所获取的积分,用户分为普通用户和专家用户,两类用户具有不同的积分系数。图4-1是该模块的类图,图中属性和
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某公司欲开发一套基于Web的房屋中介系统,以有效管理房源和客户,提升成交效率。该系统的主要功能是:(1)房源管理。员工或客户对客户拟出售/出租的意向房进行登记和管理。(2)客户管理。员工对
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某连锁酒店集团实行积分奖励计划,会员每次入住集团旗下酒店均可以获得一定积分,积分由欢迎积分加消费积分构成。其中欢迎积分跟酒店等级有关,具体标准如表2-1所示;消费积分跟每次入住消费金额
某评测机构A承接了公司B开发的ERP软件的测试工作,负责该项目的软件评测师甲,为了提高自己在ERP方面的知识,向A机构的负责人提出要到开发ERP软件的公司D做兼职开发工作的请求。当测试工作正在进行时,B公司为了申报某科技奖项,希望A机构能先出具一个证明其软
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(33),与该DFA等价的正规式是(34)。(其中,ε表示空字符)①3857②1.2E+5③-123.④.
对于业务流清晰的系统可以利用(57)贯穿整个测试用例设计过程,在用例中综合使用各种测试方法,对于参数配置类的软件,要用(58)选择较少的组合方式达到最佳效果,如果程序的功能说明中含有输入条件的组合情况,则一开始就可以选用(59)和判定表驱动法。
相对于DES算法而言,RSA算法的(7),因此,RSA(8)。
在UNIX操作系统中,把输入/输出设备看作是(23)。
对于关键字序列(10,34,37,51,14,25,56,22,3),用线性探查法解决冲突构造哈希表,哈希函数为H(key)=key%11,关键字25存入的哈希地址编号为________________。
随机试题
传统的集合运算包括______、______、______,用来实现插入、删除、修改等数据操作。
关于工程师对施工进度的监督的描述错误的是( )。
背景某施工单位承担了华东地区一机场水泥混凝土道面面层的施工任务。该单位在施工组织设计中反映的项目内容如下:机具、人员到位;支模;机具、人员配置;混合料摊铺;原材料检验;配合比设计;混合料拌和;原材料进场;模板制作;混合料运输;清扫道面;切缝;养护;拆模;
价值函数中的多重账户同时存在收益与损失的情况下的期望,可以分为()。Ⅰ.复合收益Ⅱ.复合损失Ⅲ.混合收益Ⅳ.混合损失
2007年9月1日,某企业将持有的面值为10000元、到期日为2007年9月16日的银行承兑汇票到银行贴现.假定月贴现利率为0.2%,则银行实付贴现金额为()元。
如果某有限合伙企业的合伙协议没有约定,该有限合伙企业的下列做法不违反法律规定的有()。
“剞花如荔,切丝如发,片薄如纸”是对()菜刀工的赞誉。
Whentakingatest,weneedto__________oursemanticmemories,thesumofouracquiredknowledge.
Sinceits(invent)______,thetelephonehasbecomeoneofthemostimportanttelecommunicationinstrumentsintheworld.
CHINADAILY(《中国日报》)是中国最有权威的英语报纸,为国内外读者提供最新的政治、经济、文化及教育方面的信息。《中国日报》有12版,并不定期地出版特别增刊。该报发行至全国所有省份和主要城市,以及世界上150多个国家和地区。海外读者订阅资费
最新回复
(
0
)