首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
admin
2014-04-17
43
问题
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:首先,使用后序遍历得到的序列的最后一个结点一定是根结点的值。而根结点前面的整数序列可分为两部分:第一部分是左子树结点的值,它们都比根结点的值小;第二部分是右子树结点的值,它们都比根结点的值大。 以数组(5,7,6,9,11,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://kaotiyun.com/show/7lxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
元封六年(前105),西汉以宗室女细君与乌孙王和亲。细君死后,又以宗室女()和亲,巩固了汉与乌孙的关系,使乌孙成为牵制匈奴的重要力量。
八路军建立的第一个敌后抗日民主根据地是()。
下列不属于维也纳会议召开的目的的是()。
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
第一国际成立的时间是()。
党锢事件发生后,清议的浪潮更为高涨,度辽将军()没有被当做名士列入党锢,甚至自陈与党人的关系,请求连坐。
下列科技文化成就,产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为带书。④马钧发明翻车
《道威斯计划》的实施所产生的直接结果是()。
明末清初,著名学者()抗清失败,前往日本讲学,传播中国文化。
随机试题
()动态分析主要是针对油藏投入生产后,油藏内部诸因素都在发生变化——油气储量的变化、地层压力的变化、驱油能力的变化、油气水分布状况的变化等情况,进行研究、分析,找出引起这些变化的原因和影响生产问题所在,进而提出调整挖潜生产潜力、预测今后的发展趋势。
1953年6月,毛泽东在中央政治局会议上正式提出了过渡时期的总路线和总任务。过渡时期总路线的主体是()
男性,68岁。确诊慢性阻塞性肺病近10年,因呼吸困难一直需要家人护理和照顾起居。晨起大便时突然气急显著加重,伴胸痛,送来急诊。体检重点应是
期货交易所依法或依交易规则强行平仓发生的费用()。
商品流通企业销售费用不多的,可以将其并人“管理费用”科目核算。()
2011年江苏省农林牧渔业增加值(现价)突破3000亿元大关,比上年增长4.0%;粮食生产实现“八连增”,以占全国3.8%的耕地生产了5.9%的粮食,亩产达415公斤,创历史新高;农村居民人均纯收入首次突破万元大关,达10805元,比上年增加1687元
A我也不知道,正想查词典呢,查完我告诉你。B可能要下雨,我们坐出租车回去吧。C关老师要说一下明天考试的事情。D这主要是因为那儿的学习环境比较好。E我的眼镜用了很久了,想换个新的。同学们注意一下,运动会结束以后,请大家先回教室。()
WayneManorParkingLotClosingTheWayneManorparkinglotwillbeclosedtoallcarsasofTuesday,March31.Ifyouparkint
Thereisnodoubt______heisagoodemployee.
Directions:Inthissection,youwillhearapassagethreetimes.Whenthepassageisreadforthefirsttime,youshouldlisten
最新回复
(
0
)