首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
84
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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一>lchild;} else{f=P;P=p一>rchild;} if(P==null){printf(”无关键字为x的结点\n”);exit(0);} if(p一>lchild==null){ //被删结点无左子树 if(f一>lchild==P)f一>lehild=P一>rchild;//将被删结点的右子树接到其双亲上 else f一>rchild=p一>rehild; } else{q=P;s=p一>lehild; //被删结点有左子树 while(S->rehild!=null) //查左子树中最右下的结点(中序最后结点) {q=s;s=s一>rehild;} P一>key=s一>key; //结点值用其左子树最右下的结点的值代替 if(q==P)P一>lchild=s一>lchild; //被删结点左子树的根结点无右子女 else q一>rchild=s一>lchild; //s是被删结点左子树中序序列最后一个结点 free(s); } }
解析
转载请注明原文地址:https://kaotiyun.com/show/I3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
有研究者提出,1850年以后的34年中,流人中国的白银是之前34年的两倍。出现这一现象的原因是()
清廷实行厘金制度的时间是()。
资产阶级改良道路行不通,资产阶级共和国方案夭折,其共同原因在于()。①中国封建势力的强大②帝国主义列强的直接破坏③资产阶级的软弱妥协④没有充分地发动人民群众
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
ICMP在TCP/IP协议集中属于()。
举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作:S.value--;If(S.value<0){AddthisprocesstoS.L;Block();
随机试题
Ifyouareworriedaboutthingsandareunderalotofstressatworkorschool,thenyouareprobablynotsleepingwell.Worry
能出现肺动脉瓣区第二心音减弱的是
具有泻下、软坚、清热功效的药物是
患儿,男,1岁。3天前发热38.5℃。热退后出现口腔溃疡,哭闹,拒食,流涎。检查见口腔黏膜片状充血,有数十个溃疡,有的互相融合。疮破溃后形成痂壳,最可能的诊断是
联合体协议书的主要内容包括()。
根据《水运工程岩土勘察规范》,当砂土的不均匀系数Cu和曲率系数Cu满足下列()项的条件时,可判定为级配良好的砂土。
专项计划设立失败后,管理人应当自发行期结束之日起()内,向投资者退还认购资金,并加算银行同期活期存款利息。
甲公司为一家从事服装生产和销售的国有控股主板上市公司。根据财政部和中国证监会有关主板上市公司分类分批实施企业内部控制规范体系的通知,甲公司从2012年起,围绕内部控制五要素全面启动内部控制体系建设。2012年有关工作要点如下:(1)关于内部环境。董事
网络犯罪,是指在网络空间内以计算机网络为犯罪工具或攻击对象的危害社会的行为。它具有犯罪现场和空间的虚拟性,犯罪行为的隐蔽性和犯罪手段的智能性等特点。下列行为中不属于网络犯罪的是()。
阴阳合同
最新回复
(
0
)