首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
86
问题
输入一整数数组{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://kaotiyun.com/show/1XRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述《拉巴洛条约》签订的背景、条约的主要内容及其意义。
下列对第三次科技革命推动了国际经济格局调整的叙述,不正确的是()。
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
1947年,苏联一些农村的干部和群众,为了调动广大群众生产积极性,在管理制度方面进行改革,其主要措施是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
联共(布)“十五大”规定在农村的根本任务的实质是()。
明清两朝已经是中国封建社会的晚期,同时也出现了许多新的社会现象,最明显的是()。
阅读以下史料,并回答问题:初,范阳祖逖,少有大志,与刘琨俱为司州主簿,同寝,中夜闻鸡鸣,蹴琨觉,曰:“此非恶声也!”因起舞。及渡江,左丞相睿以为军谘祭酒。逖居京口,纠合骁健,言于睿曰:“晋室之乱,非上无道而下怨叛也,由宗室争权,自相鱼肉,遂使戎狄乘隙,毒
中国共产党主张和平解决西安事变的主要目的是()。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
随机试题
适合荧光分析法测定的无机离子()。
由四层腹膜构成的结构是()
A.触摸大动脉搏动B.测量血压C.人工呼吸及心脏按压D.非同步电除颤E.同步电复律判断心脏骤停最简单的方法是
A.it’snotyouB.I’mcallingabouttheonebedroominLincolnParkC.priceshavereallygoneupthepastcoupleofyearsA:
神圣同盟开始分裂的标志是()。
Thousandsofpeople______fromGreeceeveryyeartoworkinWestGermany.
Afterhertimeinhospital,Jenny’sparentsareafraidshehas______inherlessons.
WhichofthefollowingisNOTacompoundword?
(1)RemembertheStoneAgedaysofresearchbackinelementaryschoolandmiddleschool?Wewouldspendcountlesshoursdigesting
Whatdoesthemanmean?
最新回复
(
0
)