首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
admin
2017-04-28
76
问题
设二叉排序树用二叉链表表示,结点结构为(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
学硕统考专业
相关试题推荐
战后列强围绕中国问题产生的矛盾及其表现。
在印度独立和巴勒斯坦建国问题上,英国扮演了什么角色?有什么影响?
【《关于正确处理人民内部矛盾的问题》】
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
巴黎和会讨论的中心问题是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
1543年发表解剖学专著《人体结构论》的是()。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
在明朝中叶,农业生产发生了一件非常重要的事件——(),对于当时的食物结构产生了重大的影响
随机试题
原油消泡剂破泡过程机理按顺序可以分为()。
健康
工作分析的出发点是()
A.化生B.增生C.再生D.机化E.钙化骨化性肌炎病灶中形成骨组织,属于
下列属于垂体前叶激素的有
A.心力衰竭控制后,心杂音增强B.心力衰竭控制后,心杂音减弱C.应用硝酸甘油后,心杂音增强D.心尖区收缩期喀喇音及收缩期杂音E.主动脉瓣第二心音亢进,呈金属样音调扩张性心肌病
人乳喂养儿,大便的特点是()牛乳喂养儿,大便的特点是()
枣香醉人上午接到爷爷的电话,说给我酿了一罐醉枣,让我抽空回老家一趟。爷爷每年都会在枣子成熟的季节,亲手挑选出一颗颗饱满、红润的大枣,蘸上白酒,密封在玻璃瓶中。瓶口用稀稀的黄泥土封住。静置两三个月后,待枣香、酒香融为一体,合为一物,才有了
臭氧层:气候变暖
______能够实现对内外存进行统一管理,为用户提供一种宏观上似乎比实际内存容量大得多的存储器。
最新回复
(
0
)