首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
[函数] 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
98
问题
[函数]
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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题1和问题2,将解答填入答题纸的对应栏内。【说明】某航空公司的会员卡分为普卡、银卡、金卡和白金卡4个级别,会员每次搭乘该航空公司航班均可能获得积分,积分规则如表2-1所示。此外,银卡及以上级别会员有额外积分奖励,奖励规则如表
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某连锁酒店集团实行积分奖励计划,会员每次入住集团旗下酒店均可以获得一定积分,积分由欢迎积分加消费积分构成。其中欢迎积分跟酒店等级有关,具体标准如表2-1所示;消费积分跟每次入住消费金额
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。某汽车维修公司的工时计算模块每天定时根据系统登记的维修信息统计维修工的工时工资。维修工分为学徒、普通维修工和高级维修工三种,三种维修工有不同的时薪标准。图4一1是该模块的类图,图中属性和操作前的“+”
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(33),与该DFA等价的正规式是(34)。(其中,ε表示空字符)①3857②1.2E+5③-123.④.
数据存储在磁盘上的排列方式会影响I/O服务的总时间。假设每磁道划分成10个物理块,每块存放1个逻辑记录。逻辑记录R1,R2,…,R10存放在同一个磁道上,记录的安排顺序如下表所示:假定磁盘的旋转速度为20ms/周,磁头当前处在R1的开始处。若系统顺序处
对于业务流清晰的系统可以利用(57)贯穿整个测试用例设计过程,在用例中综合使用各种测试方法,对于参数配置类的软件,要用(58)选择较少的组合方式达到最佳效果,如果程序的功能说明中含有输入条件的组合情况,则一开始就可以选用(59)和判定表驱动法。
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(30)设计模式能够有效达到该目的:该系统中的某子模块需要为其他模块捉供访问不同数据库系统(如 Oracle、SQL Server和DB2 UDB等)的功能,这些数
函数调用时,基本的参数传递方式有传值与传地址两种,(20)。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(27)
随机试题
是社会生产力中最活跃的、决定性的因素。()
Ispentthewholedayrepairingthecar.Theworkwas______easy.
下面关于律师事务所的行为符合法律规定的是:()
不允许出现裂缝的预应力混凝土构件进行结构性能检验时,下列内容无须进行检验的是()。
六西格玛管理工作程序DMAIC,其中D表示()。
物业的承接查验是指物业管理企业对()的物业共用部位、共用设施设备进行承接查验。
下列选项中,不符合《中华人民共和国婚姻法》规定的是()。
刘女士在餐厅就餐时,左脸不幸被火锅烫伤。刘女士向餐厅索赔无果,遂提起民事诉讼。除要求餐厅赔偿治疗费外,她还主张精神损害赔偿。关于本案,下列说法正确的是()。(2014法单8)
MIB对象标识符分级树根未命名,但是有3个直接后裔,分别由ISO、(1)及(2)进行管理。分级树中关于MIB-Ⅱ节点下包括10个功能组,共171个对象。在这些功能组中是一个联系各种接口的特殊节点,与接口组相配合,提供与子网类型有关的专用信息的功能组是(3)
Whethertryingtolivewiththedepressingspectacleofdroughtorbattlingrampagingfloodsorsufferingwithadebilitatingdi
最新回复
(
0
)