首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
41
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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://jikaoti.com/ti/eDGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简论唐代开元盛世局面形成的原因。
论述西欧十字军东侵的历史原因及后果。
清廷实行厘金制度的时间是()。
针对“海内新定,同姓寡少”的特点,西汉统治者采取了下列哪一项措施?()
下列对第三次科技革命推动了国际经济格局调整的叙述,不正确的是()。
1980-1987年撒哈拉以南非洲人均国民生产总值增长率为-2.9%。大部分国家经济急剧下滑,非洲的80年代被称“为失去发展的十年”。出现这现象关键原因在于这些国家
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
设有m个连续单元供一个栈与队列使用,且栈与队列的实际占用单元数事先不知道,但是要求在任何时刻它们占用的单元数量不超过m,试写出上述栈与队列的插入算法。
随机试题
初三学生雷鸣因抢劫判处有期徒刑。根据《中华人民共和国义务教育法》,其服刑期间接受义务教育所需经费应由()。
简述集权制和分权制的优缺点。
阿司匹林中毒时可采取的措施是
A.清热燥湿B.清热燥湿,泻火解毒C.清热燥湿,泻火除蒸,解毒疗疮D.清热燥湿,泻火解毒,利尿E.清热燥湿,泻肝胆火龙胆草具有的功效是
社区构成的要素有
个人教育贷款签约和发放中的风险包括()。
风险预警程序是()。①风险处置;②后评价;③信用信息的收集和传递;④风险分析。
根据《未成年人保护法》规定,国家保障未成年人的()和其他合法权益不受侵害。
某地方性法规规定,企业终止与职工的劳动合同的,必须给予相应的经济补偿。某企业认为该规定与《中华人民共和国劳动法》相抵触,可以维护自身权益的途径是()。
在教育的本质问题上,杨贤江认为教育是()。
最新回复
(
0
)