首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
[函数] 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
56
问题
[函数]
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://jikaoti.com/ti/Lli7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题1至问题5,将解答写在答题纸的对应栏内。【说明】图4.1是银行卡应用的部分类图,图中属性和操作前的“+”和“-”分别表示公有成员和私有成员。银行卡Account有两种类型,借记卡SavingAccount和信用卡Credi
阅读下列说明,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某证券交易所为了方便提供证券交易服务,欲开发一个基于Web的证券交易平台。其主要功能包括客户开户,记录查询、存取款、股票交易等。客户信息包括姓名、.Email(必填且唯一)、
阅读下列说明,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某证券交易所为了方便提供证券交易服务,欲开发一个基于Web的证券交易平台。其主要功能包括客户开户,记录查询、存取款、股票交易等。客户信息包括姓名、.Email(必填且唯一)、
阅读下列说明,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某证券交易所为了方便提供证券交易服务,欲开发一个基于Web的证券交易平台。其主要功能包括客户开户,记录查询、存取款、股票交易等。客户信息包括姓名、.Email(必填且唯一)、
阅读下列说明,回答问题,将解答写在答题纸的对应栏内。【说明】某软件的积分计算模块每天定时根据用户发布的文章数、文章阅读数来统计用户所获取的积分,用户分为普通用户和专家用户,两类用户具有不同的积分系数。图4-1是该模块的类图,图中属性和
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某连锁酒店集团实行积分奖励计划,会员每次入住集团旗下酒店均可以获得一定积分,积分由欢迎积分加消费积分构成。其中欢迎积分跟酒店等级有关,具体标准如表2-1所示;消费积分跟每次入住消费金额
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某航空公司进行促销活动,会员在指定日期范围内搭乘航班将获得一定奖励,奖励分为4个档次,由乘机次数和点数共同决定,如表2-1所示。其中点数跟票面价格和购票渠道有关,规则如表2-2所示。航空公
数据存储在磁盘上的排列方式会影响I/O服务的总时间。假设每磁道划分成10个物理块,每块存放1个逻辑记录。逻辑记录R1,R2,…,R10存放在同一个磁道上,记录的安排顺序如下表所示:假定磁盘的旋转速度为20ms/周,磁头当前处在R1的开始处。若系统顺序处
某系统的进程状态转换如下图所示。图中1、2、3和4分别表示引起状态转换时的不同原因。原因4是由于(9);一个进程状态转换会引起另一个进程状态转换的是(10)。
以下各项中,(51)属于需求说明书的评测内容。①系统定义的目标是否与用户的要求一致②设计的约束条件或限制条件是否符合实际③是否考虑过软件需求的其他方案④软件的行为与它必须处理的信息、必须完成的功能是否一致
随机试题
农村学生营养午餐改善计划实施以来,学生的身体素质得到提高。某学校为学生提供的一份午餐包括馒头、素炒黄瓜、苹果。这份午餐搭配中缺少的营养元素是()。
上消化道出血在临床上观察严重程度最关键的指标是()
构成血吸虫病传播必须具备的条件不包括
甲、乙于某日约定,甲将自己心爱的明代官窑以200万元的价格出售给乙,甲当日交付该明代官窑,乙10日后付款,明代官窑所有权自乙付清全部价款时移转给乙,10年内乙不得转售该明代官窑,否则赔偿甲55万元。双方依约履行了交付明代官窑和付款的义务。半年后,乙将明代官
消费品市场不包括()市场。
系统频率上升将使负荷所需要的有功功率()。
说明下列事实的几何意义:(I)函数f(x),g(x)在点x=x0处可导,且f(x0)=g(x0),f’(x0)=g’(x0);(Ⅱ)函数y=f(x)在点x=x0处连续,且有
计算积分+(y一x)dy,其中L:(I)是半径为a,圆心在原点的上半网周,起点A(a,0),终点B(一a,0)(见图9.2);(Ⅱ)x轴上由A(a,0)到B(-a,0)的直线段.
Salt,shellsormetalsarestillusedasmoneyinout-the-waypartsoftheworldtoday.Saltmayseemratherastrange【C1】_
Whileit’seasyenoughtobrushoffafewsleeplessnightswithapotofcoffeeandtheoccasionaldesknap,youmaybedoingmo
最新回复
(
0
)