首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
admin
2017-04-28
57
问题
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:首先,使用后序遍历得到的序列的最后一个结点一定是根结点的值。而根结点前面的整数序列可分为两部分:第一部分是左子树结点的值,它们都比根结点的值小;第二部分是右子树结点的值,它们都比根结点的值大。 以数组{5,7,6,9,1 1,10,8)为例,后序遍历结果的最后一个数字8就是根结点的值。在这个数组中,前3个数字5、7和6都比8小,是值为8的根结点的左子树特点;后3个数字9、11和10都比8大,是值为8的根结点的右子树结点。接下来需要用同样的方法确定与数组每一部分对应的子树结构。很明显,这是一个递归的过程。对于整数序列5、7和6,最后一个数字6是左子树的根结点的值。数字5比6小,是值为6的结点的左子结点,而7则是它的右子结点。同样,在序列9、11和10中,最后一个数字10是右子树的根结点的值,数字9比10小,是值为10的结点的左子结点,而11则是它的右子结点。 再举一个反例。例如整数数组{8,1,6,5},后序遍历的最后一个数是根结点,因此根结点的值是5。由于第一个数字8大于5,因此可以肯定此二叉排序树的根结点上没有左子树,数字8、1和6都是右子树结点的值。但发现在右子树中有一个结点的值是1,比根结点的值5小,这就违背了二叉排序树的定义。因此,不存在一棵二叉排序树,它的后序遍历的结果是8、1、 6、 5。 以上分析足以看出规律所在。接下来写代码吧!
解析
转载请注明原文地址:https://jikaoti.com/ti/qKfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
鸦片战争前中国同英国相比在政治、经济和军事上存在着哪些差距?到19世纪60年代,外来因素使中国社会出现了哪些变化?变化中进步的主流是什么?
毛泽东在《论持久战》中指出,中国抗日战争取得最后胜利最为关键的阶段是()。
1988年起,苏联民族矛盾激化,民族分离运动加剧,第二次较大规模的民族冲突是()。
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
永元四年(公元92年),汉和帝用宦官()掌握的一部分禁军,消灭了窦氏势力。郑众从此参预政事,并受封为侯,这是宦官用权和封侯的开始。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
东印度公司
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。说明你所设计算法的时间复杂度与空间复杂度。
随机试题
以下哪个药物含有α-羟基酮结构,与碱性酒石酸铜作用生成氧化亚铜橙红色沉淀
对每一个质量特性或问题,逐层深入排查可能原因的工程量统计方法是()。
股东是公司财产的所有人,享有种种权利,可以对公司的财产直接支配处理。()
下列有关流动性监管核心指标的计算公式,正确的是()。
甲公司是上海一家集团企业,其核心业务为批发外国高级品牌的休闲服及内衣。其他业务包括代理世界各地不同品牌的化妆品、手表和鞋。最近,甲公司购入了在国内拥有五家玩具连锁分店的乙公司,并与丙公司签订战略联盟协议参与餐饮业务。为配合甲公司的总体战略实施,甲公司可以选
下面各组成语中,加下划线的意义四个都不相同的一组是:
甲、乙两人就“人的有意识的活动是否都是有目的的”这一论题展开辩论。甲认为,人有意识的活动都是有目的的,乙持相反的观点。为证明自己观点的正确性,乙说:“我现在就可以有意识却无目的地举起我的手。”乙的证明犯了下述哪项错误?
A、 B、 C、 D、 B
要求当鼠标在图片框Picturel中移动时,立即在图片中显示鼠标的位置坐标。下面能正确实现上述功能的事件过程是()。
计算机网络是一个()。
最新回复
(
0
)