首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-01-16
61
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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://www.kaotiyun.com/show/llRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
概述罗马共和国早期平民反贵族斗争的原因、过程和意义。
简述布匿战争的过程。
论述秦国商鞅变法的内容、过程以及重要意义。
秦统一过程中,最先和最后灭掉的国家是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
简述按照恩格斯的划分方法人类的起源与进化。
美国首次提出争夺世界霸权的纲领性文件是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
随机试题
职业理想
高血压脑出血的患者手术主要是为了
男性,60岁。慢性咳嗽、咳痰伴喘息10余年,症状加重1周入院。不吸氧时PaO28.6kPa(65mmHg)、PaCO28kPa(60mmHg)。其低氧血症是由于
学生李某因在上课时嬉戏打闹,被班主任打手10~30下,班主任的这种做法()。
下列选项中关于科学技术的理解,错误的是()。
关于“科学发展观”内涵,表述不正确的是()。
乾嘉有三大考史名著,不在其列的是()
【欧阳修】北京师范大学2002年中国史学史真题
Onesummerdaymyfathersentmetobuywireforourfarm.At16,Iliked【76】betterthandrivingourtruck,【77】thistimeIwasn
Whichofthefollowingsentencesexpressesafact?(2013)
最新回复
(
0
)