首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
111
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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一>lchild;} else{f=p;p=p一>rchild;} if(p==null){printf(“无关键字为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->lehild; //被删结点有左子树 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/6VCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
现代人种出现于人类发展过程中的哪一个时期?()
魏晋南北朝时期,社会经济特点与前一历史阶段的明显不同之处是()。
试论魏孝文帝改革的内容及其意义。
下列不是春秋时代齐国管仲改革的内容的是()。
下列哪一项不是毛泽东在抗日战争期间的著作?()
20世纪五六十年代经济高速增长时期,西欧经济增长最快的国家是()。
日本三个月亡华计划破产的标志是()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
某计算机系统字长为32位,包含2个选择通道和1个字节多路通道,每个选择通道上连接了2台磁盘机和2台磁带机,字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下:磁盘机:800KB/s磁带机:200KB/s
随机试题
乳糖是一种双糖,具有还原性。
下列树种与无患子为同一科的是
心室肌细胞的有效不应期特别长(200~300ms),其原因主要为
国家药品标准没有规定的中药饮片炮制规范,必须按照哪个管理部门制定的炮制规范炮制
男性,78岁,因腹泻5天,昏睡4小时来急诊。既往高血压病史35年,无糖尿病史。查体:血压90/50mmHg,意识朦胧,检查时手足乱动,配合欠佳,皮肤弹性差,心率106次/分,呼吸22次/分,两肺未闻及干、湿啰音。腹软,肝脾未扪及,双下肢胫前轻度可凹性水肿,
“备案号”栏应填写()。“运费”栏应填写()。
甲、乙、丙、丁共同投资设立了A有限合伙企业(以下简称A企业)。合伙协议仅约定:甲、乙为普通合伙人,分别出资10万元;丙、丁为有限合伙人,分别出资15万元;由甲执行合伙企业事务,对外代表A企业。A企业存续期间,发生以下事项:(1)2月,合伙人丁自营同A企业
0,1∕3,1∕3,7∕12,5∕7,()
2006年,甲(男,籍贯X省)经人介绍认识了乙(女,籍贯Y省),两人随后发展为恋人关系。2008年3月,二人登记结婚,两人在Z直辖市租了一套房屋开始了夫妻生活。但婚后,甲与乙因琐事时常发生矛盾,导致两人感情出现危机,相互之间缺乏信任,甲也开始怀疑乙有外遇,
从所给四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
最新回复
(
0
)