首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
40
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
【波兹南事件】北京大学2003年欧美近现代史真题;华中师范大学2015年世界史基础真题
唐朝对外关系呈现出前所未有的盛况,其原因不包括()
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
阅读下列材料,回答问题:材料一:列宁说:“我们在夺取政权时便知道,不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
概述公元前8—前6世纪希腊海外殖民的背景、范围及影响。
判断英国工业革命基本完成的主要依据是()
下列不属于十一届三中全会过后对各方面社会关系的调整的是()
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
随机试题
叔本华说:“人虽然能够做他所想做的,但不能要他所想要的。”爱因斯坦从中得到的主要启发是()
检验批划分的主要依据是()。
低温容器是指设计温度等于或低于()℃的容器。
采用设备经营租赁的方案,年销售收入1000万元,年经营成本600万元,年租赁费用70万元,与销售相关的税金30万元(每年),所得税率33%,则设备租赁的年净现金流量为()万元。
下列有关消费税的叙述中不正确的是()。
能稳定公司控制权的长期筹资方式包括()。
()缺乏可引起坏血病。
根据2018年国务院政府工作报告,下列有关我国在2018年经济社会发展的主要预期目标说法不正确的是()。
根据以下资料,回答116-120题。2007年我国参加最低生活保障人数是2001的()。
已知某信道的信号传输速率为64kb/s,一个载波信号码元有4个有效离散值,则该信道的波特率为()kBaud。
最新回复
(
0
)