首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
50
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
20世纪五六十年代经济高速增长时期,西欧经济增长最快的国家是()。
有研究者提出,1850年以后的34年中,流人中国的白银是之前34年的两倍。出现这一现象的原因是()
简述第二次世界大战中各主要战场战略性转折的时间及其代表性战役。
在下列四本部书中有可能记载“甘薯所在,局面便有半年之粮,民间渐次广种”一语的只能是()。
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
设有m个连续单元供一个栈与队列使用,且栈与队列的实际占用单元数事先不知道,但是要求在任何时刻它们占用的单元数量不超过m,试写出上述栈与队列的插入算法。
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统处于不安全状态;
随机试题
超过有效期的药品是所标明的适应证或者功能主治超出规定范围的药品是
我国三家政策性银行成立的时间是()
中国走和平发展道路的自信和自觉,来源于()
输卵管妊娠需与哪些疾病鉴别
儿童白血病在儿童肿瘤中发病占
毛果芸香碱对眼睛的作用为
股份转让公司的股份必须按照有关规定重新确认、登记和托管后方可进行股份转让,这些工作由()负责办理。
小张与小李签订一份古董手表的买卖合同,约定小张先支付货款,三日后小李交付古董手表。小张按时交款,小李却迟迟不交付手表。小张几次三番要求小李交付手表,并给予10日宽限期。小李仍然无动于衷,小张决定解除合同。小张解除合同属于()。
材料(大意):赵潇是武大电子信息学院光信息科学与技术专业研究生,然而,就在他踌躇满志准备硕博连读时,母亲不幸患癌症晚期。每月两万元的化疗费用,基本上都是从亲戚那里借来的,如今,他已欠下数万元债务,而接下来的治疗费用也还没有着落。眼见着母亲的身体日
资本的技术构成是指()。
最新回复
(
0
)