首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
82
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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
学硕统考专业
相关试题推荐
中国古代的经济、文化中心本来在北方,后来移到了南方。请结合史实对这一转移过程进行述评。
19世纪末中国维新变法思想的基本内容是什么?与18世纪法国启蒙思想相比,两者在促进社会变革的作用上有何不同?为什么?
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
在五四运动中,站在最前列,起了先锋作用的是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
据史记《商君传》商鞅变法,“为田开阡陌封疆,而赋税平”其目的
第二次世界大战后,资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力
全国高校院系调整的具体时间是()。
1980年1月,邓小平在《目前的形势和任务》提出的中国人民长期奋斗的三件大事是()。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
随机试题
某地区年初人口2100万,年末人口2150万,年内死亡人口110万,计算人口死亡率指标的正确算式是()
取一期愈合的是()。
根据《中华人民共和国土地增值税暂行条例》的规定,纳税人转让房地产所取得的收入包括()。
一个项目的成果性目标必须是()。
某被评估企业截至评估基准日,经核实后的应收账款余额为1460000元,该企业前5年的应收账款累计余额7200000元,处理坏账累计额610000元,按坏账比例法确定该企业应收账款的评估值最接近于()元。
德育过程是从教育者、受教育者________和德育方法四个互相牵制的要素构成。
在漫长的中国封建社会里,学校教育得到了进一步发展,其具体的类型有()
【2011.江西】数学学习中形成的认真审题的态度及其审题的方法会影响到化学、物理等学习的审题态度和方法,这种学习迁移叫作()。
目前各种城域网建设方案的共同点是在结构上采用三层模式,这三层是:核心交换层、业务汇聚层与_______。
Itissaidthatthenumberofthepeoplewhodiedonhighwayshasexceededthe______sincetheAmericanRevolutionaryWar.
最新回复
(
0
)