首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-01-16
71
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
选项
答案
在二叉排序树上删除结点,首先要查找该结点。查找成功后,若该结点无左子树,则可直接将其右子树的根结点接到其双亲结点上;若该结点有左子树,则将其左子树中按中序遍历的最后一个结点代替该结点,从而不增加树的高度。 void Delete(BSTree bst,keytype X){ //在二叉排序树bst上,删除其关键字为X的结点 BSTree f,P=bst: while(P&&p一>key!=X) //查找值为X的结点 if(p一>key>X){f=P;p=p->lehild;} else{f=p;P=p一>rehild;} if(P==null){prinff(”无关键字为x的结点\n”);exit(0):} if(p->lchild==null){ //被删结点无左子树 if(f一>lchild==P)f一>lchild=P一>rchild;//将被删结点的右子树接到其双亲上 else f一>rchild=p一>rchild; } else{q=p;s=p->lchild; //被删结点有左子树 while(s->rchild!=null) //查左子树中最右下的结点(中序最后结点) {q=s;s=s->rchild;} p->key=s->key; //结点值用其左子树最右下的结点的值代替 if(q==p)p一>lchild=s一>lchild; //被删结点左子树的根结点无右子女 else q->rchild=s->lchild: //s是被删结点左子树中序序列最后一个结点 free(s); } }
解析
转载请注明原文地址:https://kaotiyun.com/show/llRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
关于1957年的整风运动,下列不属于其内容的是()。
论述罗马共和国早期对外征服的过程和历史意义。
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
下列叙述不正确的是()。
下列历史事件发生的先后顺序是()。①“铁幕”演说②马歇尔计划③北大西洋公约
洋务派创办军事工业的方式是()。
1984年,《中共中央关于经济体制改革的决定》中强调,商品经济的充分发展是社会经济发展不可逾越的阶段,市场调节的辅助性作用不可缺少,并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
不需要抢占的进程调度算法是()。
随机试题
关于应用呼气末正压通气治疗ARDS疾病的原理错误的是
王某、赵某于2007年1月7日共同抢劫个体户李某,在抢劫中,持匕首刺中李某的腹部,致李某失血过多而死亡。该案经公安机关侦查终结后,移送人民检察院审查起诉,人民检察院以抢劫罪将二人起诉到某市中级人民法院。请根据上述情况,回答以下问题。在本案中,如果王某未
疗程超过2个月的感染为伤口直接污染造成的感染为
某工程项目施工过程中,施工单位的项目经理违反建设工程安全生产管理规章制度,强令工人违章进行施工作业,导致重大人员伤亡事故。该项目经理的行为构成()。
医务社会工作者倡导工作的直接内容包括哪些?()
【2014年山东淄博.判断】学校课程不等同于校本课程,而是国家课程、地方课程与校本课程的综合体。()
世界上三大地震带是()。
公安行政复议是公民、法人或者其他组织认为公安机关的抽象或具体行政行为侵犯其合法权益,依法提出申请,由受理的公安机关对该行为进行审查和决定的活动。()
下列标准中,使用单模光纤的是()。
下列关于IEEE802.11三种协议的描述中,错误的是()。
最新回复
(
0
)