首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
设二叉排序树用二叉链表表示,结点结构为(lchild,data,rchild),其中,data为整形,指针lchild和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列),根指针为root,试写出算法:将该二叉排序树转
admin
2017-04-28
47
问题
设二叉排序树用二叉链表表示,结点结构为(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
学硕统考专业
相关试题推荐
《关于建国以来党的若干历史问题的决议》
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
30年代,美国政府对一系列国际问题执行中立政策,最主要的原因是()。
改革开放以来,乡镇企业的异军突起,其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。 据此回答问题:中共中央将战略决战的方向首先指向()
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。据此回答问题:中共中央将战略决战的方向首先指向的是()
随机试题
紫铜就是()。
A.麻黄连翘赤小豆汤B.己椒苈黄丸合参附汤C.温胆汤合附子泻心汤D.麻杏石甘汤E.五味消毒饮合五皮饮水肿变证之水凌心肺证,治疗宜选
女,55岁。颈肩痛5个月,并向右上肢放射。右上肢肌力下降,手指动作不灵活。椎棘突间有压痛,右手拇指感觉减弱。上肢牵拉试验阳性,压头试验阳性。最可能的颈椎病类型是()
婴儿扶腋下能站立,能喃喃地发出单音节,两手能各握一玩具,并能伸手取物。判断该婴儿的最可能的月龄为
组织结构设计包括( )工作。
A、 B、 C、 D、 D交点个数均为2、4、6。故选D。
根据所给资料,回答问题。2014年,某省全社会研发经费达122.13亿元,研发经费占GDP的比重达0.68%,比2013年下降0.02个百分点。已知“十二五(2011—2015年)”期间该省技术合同成交总额约为798亿元,则2015年该省技术合同
社会主义初级阶段与新民主主义社会因为都存在多种经济成分而有某些相似之处,但却在社会性质上存在着明显差别,其中两者的根本区别在于()
对查询功能的叙述中正确的是______。
A、Hehasquitsmokingforalongtime.B、Hefindsitishardtostopsmoking.C、Hehadlungcanceryearsago.D、Heisonmedicat
最新回复
(
0
)