首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-01-16
53
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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
学硕统考专业
相关试题推荐
解放军渡江战役中横渡长江的东西两个攻击点是()。
科学技术革命包括三个既有联系又有区别的过程,下列不属于三个过程的是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
“二战”后,联合国的成立反映了世界人民和平的愿望,下列叙述正确的是()。
美国首次提出争夺世界霸权的纲领性文件是()。
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
假设在一台单处理机上执行如下表所示的进程,且假定这些进程在时刻0以1,2,3,4,5的顺序创建。时间单位为时间片,优先级以数值大者为优。(1)请说明分别使用FCFS、RR(时间片=1)、SPF以及非抢夺式优先级调度算法时,这些进程的执行
某个页式存储管理系统,接收了一个大小一共7页的程序,其依次访问的页为:1、2、3、4、2、1、5、6、2、1、2、3、7。若分配给该程序的内存空间为4页,并一次预装入,请用先进先出(FIFO)调度算法和最近最少用(LRU)凋度算法计算,程序执行时会产牛多少
随机试题
女性,50岁。不规则阴道出血伴下腹胀痛及脓性白带1个月余。妇科检查:阴道内无异常,宫颈光滑,子宫体略大,质软,双附件正常。若此患者确定诊断后行开腹术,术中取腹水找到癌细胞,其处理正确的是
津液中“液”的特点有
A.高血压心脏病B.TIAC.脑血栓形成D.肾功能不全E.高血压脑病视盘水肿见于
治疗伤食型泻的首选方剂是
《执业药师资格制度暂行规定》规定,执业药师注册证有效期满前3个月,持证者须到注册机构办理()
我国个人住房抵押贷款的风险最终主要转移在()身上。
丝绸之路促进了东西方之间的经济文化交流。下列能够反映这种交流的主要史实有()。①中国的凿井、冶铁等技术传到西方②中亚的葡萄、黄瓜、胡萝卜、大蒜等农作物传入中国③罗马的毛织品、玻璃等手工业品和杂技传入中国④印度的佛教传入中国⑤越南的占
1996年的《幼儿园工作规程》明确规定幼儿园的领导体制为()。
已知u=f(2xy,x3+y3),f可微,则=___________.
在PowerPoint2003中,能设置声音的循环播放。
最新回复
(
0
)