首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
89
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
一战从欧洲的战争变成全球范围的战争是在()。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
《道威斯计划》的实施所产生的直接结果是()。
1925年10月签订《洛迦诺公约》后,法国外长白里安认为:“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。
试析第三次科学技术革命对人类社会和历史进程的影响。
解放军渡江战役中横渡长江的东西两个攻击点是()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
随机试题
一位总统候选人在竞选辩论中对他的对手说:“挣钱的办法有成千上万种,但只有一种是诚实的。”对手问:“哪一种?”他回答:“正好是您不知道的那一种。”他通过这些话讽刺了对手什么?()
贫血性梗死常发生于
窜痛多属( )。脱肛多属( )。
合同之债的法律适用同时涉及其他方面的法律适用,综合涉及意思自治原则。根据我国有关法律规定,关于涉外民事关系的法律适用,下列哪个领域采用当事人意思自治原则?()
在以下价值指标中,一般能通过“数量×单价”的方法计算出来的是( )。
在上海证券交易所上市交易的某只股票,2008年末的每股税后利润为0.20元,市场利率为2.5%。请根据以上资料回答下列问题:该只股票的静态价格为()元。
王某年满16周岁,在县城经营一家汽车修理店,经营状况良好,王某属于()。
闻一多在其理论文章《诗的格律》中提出诗歌的“三美”主张,下列不属于“三美”的是()。
你是一名社保局工作人员,在做农村基层政策宣传时,有人站起来大声说社保是骗人的,政策没准儿哪天就变,引起了现场的混乱,请问你怎么办?
Scientistswillbeabletofreezedyingpeopleandrevivethemyearslaterwhenacurefortheirdiseasehasbeenfoundopening
最新回复
(
0
)