首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
92
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
选项
答案
在二叉排序树上删除结点,首先要查找该结点。查找成功后,若该结点无左子树,则可直接将其右子树的根结点接到其双亲结点上;若该结点有左子树,则将其左子树中按中序遍历的最后一个结点代替该结点,从而不增加树的高度。 void Delete(BSrIIree 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->rehild; } 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/z3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
尚书一职,秦置于宫禁;西汉沿置,为皇帝收发文书,传达记录诏命章奏;东汉置尚书台,“出纳王命,赋政四海,权尊势重”,成为朝廷的政务中心。这一过程反映了()
论述屋大维的元首政制的统治特点。
在下列四本部书中有可能记载“甘薯所在,局面便有半年之粮,民间渐次广种”一语的只能是()。
论述秦国商鞅变法的内容、过程以及重要意义。
新中国院系调整主要是学习()。
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
康熙五十九年(1720)指定()组织“公行”(“十三行”)专营对外贸易。凡外商税项的征收、货物的交易,以及外商生活的管理等,均归“行商”负责。
两个进程P、Q都需要三个资源1,2,3,系统中有资源1、2、3各一个,如果P请求资源的顺序是1、2、3,Q请求资源的顺序任意,共有3!=6种排列,其中共有()个排列可能导致死锁。
随机试题
Hardly_____thepeoplerantowardit.
下列哪项不符合肾炎性水肿的特点?
监理工程师的计量权力本质上是对计量结果的()。
某水利工程项目进展到第10周后,对前9周的工作进行了统计检查,有关统计情况见下表。问题:将上表复制到答题纸上,在表中计算前9周每项工作(即A、B、C、D各项工作项)的BCWP。
下列各项中,属于波特价值链分析的支持活动的有()。
根据我国《会计法》的规定,外来原始凭证的金额有错误时,应当采取的正确做法是()。
在Word的“页面设置”对话框中可以设置每个文档中的页数。()
A、 B、 C、 D、 C每幅图都是由两个图形构成的,且后一幅图中都含有前一幅图中的一个图形,所以选C选项。
根据我国现行宪法规定,有修改宪法提议权的是()
Itisalwaysalittlesadtosaygoodbyetoalong-timefriendyouareleavingforever,a【C1】______youhavespentmanyhourswit
最新回复
(
0
)