首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
84
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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
学硕统考专业
相关试题推荐
中华民国军政府是由下列哪个军阀成立的?()
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
永元四年(公元92年),汉和帝用宦官()掌握的一部分禁军,消灭了窦氏势力。郑众从此参与预政事,并受封为侯,这是宦官用权和封侯的开始。
斯大林时期的经济体制最本质的特点是()。
骑士团是罗马教皇推行反宗教改革的工具,其中在波罗的海南岸发挥重要作用的骑士团是()。
试述清朝在巩固统一多民族国家方面所做的种种努力。
下列哪一项不是毛泽东在抗日战争期间的著作?()
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述,不正确的是()
经六朝时期的发展,南方形成了三个农业发达地区即()。
某计算机系统字长为32位,包含2个选择通道和1个字节多路通道,每个选择通道上连接了2台磁盘机和2台磁带机,字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下:磁盘机:800KB/s磁带机:200KB/s
随机试题
患者,男,42岁。车祸外伤1天,左眼视力减低。为除外左侧视神经管骨折,应首选的影像学检查是
皮水治宜选用
早期子宫内膜癌首选的治疗方式是
处方超过三日后
下列关于地面水环境现状点污染源调查原则的有关表述,不正确的是()。
中国公民凭护照或其他有效证件出入境,()。
在通胀问题尚未完全解决的情况下,面对发达国家的主权债务危机,新兴经济体又不得不再次放松经济政策。这种内热外冷的_______导致新兴经济体既要促进经济增长,又要防止通胀_______。依次填入画横线处最恰当的一项是()。
假若城市的教育资源能够在不同学校之间公平分配,那么就不会出现重点学校与普通学校的区别,也不会有一些老师因教育资源的过度聚集而“暴富”。假若教育资源在地域之间得到公平分配,边远地区的山村学校能获得更多的投入,那么,乡村教育就不会如此艰难。这段文字主要谈论
意大利文艺复兴雕刻家多纳泰罗的代表作是()。
()的艺名是“麒麟童”,20世纪20年代已有名,最擅长做功,称“做派老生”。
最新回复
(
0
)