首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
admin
2017-04-28
60
问题
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。
给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转变为递减有序的二叉排序树(前序遍历得递减有序序列),返回根指针;
选项
答案
对于如图3—16a所示的子树,假设根节点P的左子树和右子树都已经经过调整而达到题目的要求,rm结点为右子树前序遍历的最后一个结点,由于P的左子树ltree的元素都小于右子树rtree的任意元素,所以图3—16a右边所示的树是满足题目要求的。类似地,在没有左子树(右子树)的情况下,按方案图3—16b(或图3—16c)调整该树得到的结果是满足要求的。我们可以按递归的方式,对于不同的情况,用图3 —16a、b、c所示三种规则对树进行调整。 [*] 代码如下:Node* reverseTree{Node *p,Node *m){ Node *1, *r, *lm, *rm; if{p—>rchild! =NULL)r=reverseTree (p—>rchild,rm); //递归处理右子树 if(p—>lchild! =NULL)l=reverseTree (p—>lchild,lm); //递归处理左子树 Node *q= (Node *)malloc(sizeof (Node)); //申请并初始化新结点q q—>data=p—>data; q—>lchild=q—>rchild=NULL; m=q; if <r!=NULL) //若递归返回之后右子树不空 { if(1!=NULL) rm—>lchild=1, //若递归返回之后左子树不空 rm— >rchild=q; //结点q作为右孩子 return r; //返回调整后的树 } if(1!=NULL) //若递归返回之后左子树不空 { lm—>lchild=q; //结点q作为左孩子 return 1; //返回调整后的树 } return q;}
解析
转载请注明原文地址:https://kaotiyun.com/show/3PRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
苏台德问题
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
下列选项中,对东汉度田问题的描述中,不正确的是()
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
鸦片战争中,林则徐被革职查办反映的问题是()。
克里特文明的文字类型是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
1543年发表解剖学专著《人体结构论》的是()。
在明朝中叶,农业生产发生了一件非常重要的事件——(),对于当时的食物结构产生了重大的影响
随机试题
ABC三相交流母线的相色分别为()。
资料一公牛自1995年创立之初,迅速找到自身定位,立志“制造永不坏的插座”,产品推出之后,使得消费者感受到前所未有的使用体验,公牛集团自此开始秉持科技化、现代化的生产模式。1997年,公牛在行业内第一个获得国家长城认证,从此奠定了行业内好品质的品
Itwasclever______attheanswerintwominutes.
诊断尿路结石首选的X线检查方法是
小茴香的功效是()。
高某诉张某合同纠纷案,终审高某败诉。高某向检察院反映,其在一审中提交了偷录双方谈判过程的录音带,其中有张某承认货物存在严重质量问题的陈述,足以推翻原判,但法院从未组织质证。对此,检察院提起抗诉。关于再审程序中证据的表述,下列哪些选项是正确的?(2013年卷
下列各项中,不适宜进行招标的项目是()。
要保护网络个人信息安全,法律是最好的“利剑”。一些人之所以铤而走险,除了丰厚的利润诱惑,还因为游走在模糊地带,自恃可以不受法律的制约。鉴于此,唯有以法律的准绳对网络个人信息保护画出“红线”,将盗用贩卖网络个人信息定性到违法犯罪的高度,才能有效整合各方面执法
佩刀;刀鞘
设函数f(x),g(x)在区间[a,b]上连续,且f(x)单调增加,0≤g(x)≤1,证明:(Ⅰ)0≤∫axg(t)dt≤x-a,x∈[a,b];f(x)dx≤∫abf(x)g(x)dx。
最新回复
(
0
)