首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
[函数] 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
90
问题
[函数]
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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列C程序,回答问题1至问题3,将解答填入答题纸的对应栏内。【C程序】请针对上述C程序给出满足100%DC(判定覆盖)所需的逻辑条件。
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。【说明】某软件的积分计算模块每天定时根据用户发布的文章数、文章阅读数来统计用户所获取的积分,用户分为普通用户和专家用户,两类用户具有不同的积分系数。图4-1是该模块的类图,图中属性和
阅读下列C程序,回答问题,将解答填入答题纸的对应栏内。【C程序】staticvoidpermute_args(intpanonopt_start,intpanonopt_end,intopt_end,intncycle){
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】在某嵌入式智能服务机器人的软件设计中,为了更好地记录机器人的个体信息和机器人的工作信息,为智能服务机器人设计了信息数据库。数据库主要完成收集智能服务机器人反馈信息的作用,记录所有机器人的所有工
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(33),与该DFA等价的正规式是(34)。(其中,ε表示空字符)①3857②1.2E+5③-123.④.
在一个单CPU的计算机系统中,有两台外部设备R1、R2和三个进程P1、P2、P3。系统采用可剥夺式优先级的进程调度方案,且所有进程可以并行使用I/O设备,三个进程的优先级、使用设备的先后顺序和占用设备时间如下表所示:假设操作系统的开销忽略不计,三个进程
在系统转换的过程中,旧系统和新系统并行工作一段时间,再由新系统代替旧系统的策略称为(20);在新系统全部正式运行前,一部分一部分地代替旧系统的策略称为(21)。
以下选项中,可以用于Internet信息服务器远程管理的是(63)。
软件开发人员可以用(18)软件编写和修改程序。
加密和解密是明文和密文之间的可逆转换,______不属于加密算法。A.RSAB.SHAC.DESD.AES
随机试题
患者胸部外伤2小时。查体:脉搏120次/min,血压12/8kPa,右胸可触到骨擦感和皮下气肿,叩诊鼓音,呼吸音消失,急救处理是
猪传染性胸膜肺炎的特征病变是肺炎和()。
王某,女,43岁,因哮喘大发作而急诊入院。护士在入院时的初步护理中下列哪项做法不妥
关于法庭调查顺序,正确的是()。(1)告知证人的权利义务,证人作证,宣读未到庭的证人证言;(2)当事人陈述;(3)宣读勘验笔录;(4)出示书证、物证和视听资料;(5)宣读鉴定意见。
某工程施工中出现重大安全事故,建设主管部门对有关单位可作出除()以外的行政处罚。
当事人双方既约定违约金,又约定定金的合同,一方当事人违约时,对违约行为的赔偿处理原则是()。
某学生在体操技能训练中表现:整体动作趋于协调连贯,多余动作有所减少,视觉控制逐渐让位于动觉控制,但动作技能尚未迭到自动化,该生的体操技能处于()。
我们俩谈不,吵了好几次架。
TheEuropeanonlinefashionbusinessisfierce.Justaskbackersofone-timehighflierslikeboo.com,theurbansportswearretai
Ofthetwosisters,Sarais(young)________one,andsheisalsotheonewholovestobequiet.
最新回复
(
0
)