首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
94
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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
学硕统考专业
相关试题推荐
论述第三次科技革命产生的原因、表现和影响。
东欧剧变的根本原因是()。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
太平天国作为几千年来农民运动的高峰,所遇到的历次农民运动中不曾有过的新情况是(
中国第一个资产阶级革命团体兴中会建立的时间是()。
古埃及第24朝法老波克利斯进行改革,宣布废除奴隶制,债权人只能索取债务人的财产作抵偿,而不能占有债务人的人身,因为财产属于个人,而公民人身属于国家,国家需要他们服役。该改革旨在
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统处于不安全状态;
随机试题
胃肠道的恶性肿瘤经血道首先转移到()
在PowerPoint2010中,选中用作超链接的对象,按________键即可出现“插入超链接”对话框。
A、宣肺化痰,利咽,排脓B、清热化痰,润肺止咳C、清热化痰,开郁散结D、清热化痰,宽胸散结E、清热化痰,除烦止呕竹茹的功效是()
在黏土心墙施工中,可采用()等施工方法。
根据《水利工程质量事故处理暂行规定》(水利部令第9号),事故部位处理完毕后,必须按照管理权限经过()后,方可投入使用或进入下一阶段施工。
成本控制的例外管理原则中,例外情况的常用判定要点主要有()。
《中小学教师职业道德规范》(2008年)对教师“为人师表”提出的具体要求不包括()
Manystudentsfindtheexperienceofattendinguniversitylecturestobeaconfusingandfrustratingexperience.Thelecturerspe
在诊断光纤故障的仪表中,设备()可在光纤的一端就测得光纤的损耗。
Thoughitwasgettingdark,______stillwentonworking.
最新回复
(
0
)