首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
admin
2019-08-01
112
问题
二叉排序树采用二叉链表存储。写一个算法,删除结点值是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->lchild=p->rchild;//将被删结点的右子树接到其双亲上 else f->rchild=p->rchild; } else{q=p;s=p->lehild; //被删结点有左子树 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/6VCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
太平天国作为几千年来农民运动的高峰,所遇到的历次农民运动中不曾有过的新情况是(
下列法律文件中,规定内阁对君主负责的是()。
商代青铜器的制作技术很高,尤其是礼器的制作,造型美观,纹饰精巧,是水平极高的工艺品,其中主流的花纹是()。
论述世界反法西斯联盟形成的过程。
概述第二帝国时期法国经济发展的特点。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。据此回答问题:中共中央将战略决战的方向首先指向的是()
曾经来华留学,并在日本大化改新中发挥重要作用的是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
随机试题
关于直线职权管理者的说法正确的是()。
轴屋面檐部共需多少根挑檐木?
拆迁永久性测量标志或者使永久性测量标志失去效能的,依法应当经()批准。
合同债权转让的通知在(。)的情况下可以撤销。
账务处理系统的账套参数主要有()。
在直角坐标平面中,已知点P1(1,2),P2(2,22),P3(3,23),…,Pn(n,2n),其中n是正整数,对平面上任-点A0,记A1为A0关于点P1的对称点,A2为A1关于点P2的对称点,…,An为An-1关于点Pn的对称点.求向量的坐标;
青铜壶是春秋战国时期重要的生活器皿,当时铸造壶器可以采用下列哪项先进技术?()
温度计:气温
(2009年真题)下列法律概念中,属于客体概念的是
Mikehadalready(lie)______downwhenhecamein.
最新回复
(
0
)