首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
38
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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
学硕统考专业
相关试题推荐
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
东欧剧变的根本原因是()。
下列关于20世纪历史的叙述,全部错误的是()。①朝鲜建国的时间早于中国②1948年3月,英国、法网、比利时、荷兰、卢森堡5国缔结了《合作和集体防御条约》即《五国和约》③1950年,周恩来到达莫斯科,中苏缔结了《中苏互不侵犯条约》,标志着社会主义阵
斯大林时期的经济体制最本质的特点是()。
下列对第三次科技革命推动了国际经济格局调整的叙述,不正确的是()。
提出电磁感应定律的是物理学家()。
东汉末期的农民起义出现的新特点是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
在协议数据单元中,控制信息所不包括的内容是()。
随机试题
现在欧洲有据可查的最早的环境法律是__________。
植物光合作用利用的太阳光谱的主要范围在()
扭伤早期局部血肿错误的处置是
此时进行X线检查首选的片位是如X线片示,移位牙根完全进入上颌窦,此时最佳处理方法是
导游员怎样调节游客的审美行为?
以下选项中属于米香型酒的特点的是()。
在边防沙漠地带,巡逻车每天行驶200千米,每辆巡逻车可载供行驶14天的汽油,现有5辆巡逻车,同时从驻地A出发,完成任务后再沿原路返回驻地。为了让其中三辆尽可能向更远的距离巡逻(然后再一起返回),甲、乙两车行至途中B处后,仅留足自己返回驻地所需的汽油,将其余
下列观点属于马克思主义哲学“社会形态”理论范畴的是()。
材料1招来灾难的猫第一次世界大战期间,德法两国军队在一块开阔地带对峙。某次交战之前,德军一名参谋长天天拿着望远镜观察法军阵地上的情况。一天早上,在法军前沿边地后方的一个坟地上,突然发现一只猫,以后一连4天,这只猫在早上八九点钟总要出来安
ShouldAKidBeGuidedtoTellaWhiteLie?It’smyfamily’straditiontoexchangegirlsonChristmasEve.Beforewedidso,
最新回复
(
0
)