首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
admin
2017-11-20
74
问题
输入一整数数组{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/rjRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
全国高校院系调整的具体时间是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
下列对第三次科技革命推动了国际经济格局调整的叙述,不正确的是()。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
制瓷业是光彩夺目的一个手工业部门,北宋的制瓷业的重心在黄河流域和中原地区。回答问题:()创于唐,盛于北宋,以白瓷著名,为宋代印花白瓷的精品
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
随机试题
根据威尔逊在其最后一部著作《美国的宪法政府》中的果断预言,将日益成为大众政治灵感的贮藏所的是
简述单位犯罪自首的认定。
患者,女,17岁,患"支气管哮喘"10余年。症见咳嗽气喘,喉中痰鸣,痰多色黄而稠黏,心胸烦热,胸闷气急,头痛恶寒,发热口微渴,舌苔黄三、B1型题(标准配伍题)腻,脉滑数者。治宜选用
如下图所示消防车登高操作场地与消防车通道连通,且场地靠建筑外墙一侧的边缘距离建筑外墙为()m。
从无形资产归类的角度讲,计算机软件属于()无形资产。
社会问题是指社会中发生的被多数人认为是不合需要或不能容忍的事件或情况,而需要运用社会群体的力量加以解决的问题。下列情况中,成为社会问题的是()。①甲型流感在今年秋冬季的大面积爆发问题②城市某社区业主与物管的纠
现有甲、乙两个水平相当的技术工人需进行三次技术比赛,规定三局两胜者为胜方。若甲在第一次比赛中获胜,则乙最终取胜的可能性有多大?
社会主义文化建设的基本内容包括思想道德建设和()。
-Doyouhavemypassport,Janet?-Yes,Ihave______righthere,inthelocker.
下列程序段的执行结果为______。DimA(10,10)Fori=2To4Forj=4To5A(i,j)-i*jNextjNextiPrintA(2,5)+A(3,4)+A(4
最新回复
(
0
)