首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-01-16
51
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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->lehild;} else{f=p;P=p一>rehild;} if(P==null){prinff(”无关键字为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->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/llRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
解放军渡江战役中横渡长江的东西两个攻击点是()。
科学技术革命包括三个既有联系又有区别的过程,下列不属于三个过程的是()。
简述希波战争过程及其意义。
秦统一过程中,最先和最后灭掉的国家是()。
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
乾隆时期,明确规定了驻藏大臣的地位与达赖班禅同等,并实行“金瓶掣签”制度的文件是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
假设磁头当前位于第105道,正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35,45,12,68,110,180,170,195,采用SCAN调度(电梯调度)算法得到的磁道访问序列是____。
随机试题
关于运动试验检查前准备工作的描述,正确的是
急性心包炎心包积液时最突出的症状是
对某水体监测表明,5日生化需氧量(BOD5)为16mg/L,氯化物250mg/L,总磷0.09mg/L,总大肠菌群8000个/L,pH8.5,其中超过环境质量标准的是
张某,女,8岁。形体肥胖,倦怠少力,面色少华,食欲不振,睡中遗尿,大便溏薄,常自汗出。舌淡苔薄,脉无力。其主要病机是
热水微温或温水
下列说法中正确的有:
下列计划中,属于控制性进度计划的有()。
根据规定,下列款项中,不得办理托收承付结算的有()。
内幕信息是指在证券交易活动中,涉及上市证券发行人的经营、财务或对该证券的市场价格有重大影响的尚未公开的信息。()
Itisappropriateonananniversaryofthefoundingofauniversitytoremindourselvesofitspurposes.Itisequallyappropria
最新回复
(
0
)