首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
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/7lxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简要概括基督教的演变。
下面条约没有涉及德国的赔款问题的是()。
《凡尔赛和约》中,战胜国以何种方式处置德国的全部海外殖民地?()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
日本在《二十一条》中提出:“中国沿海岛屿不得租于他国。”其真实目的是()。
下列对凡尔赛和约中有关德国疆界问题的表述,正确是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭重创
明末清初,著名学者()抗清失败,前往日本讲学,传播中国文化。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
随机试题
完全预期理论认为远期利率等于短期利率的预期,市场收益率曲线是水平的。( )
BSC协议中的肯定确认(ACK)的监控报文占多少字节?多少比特?
ImustgothereearlierJohnhassuggestedthatI_____anhourbeforethediscussionbegins.
下列关于HCO3-在近端小管重吸收的描述,正确的是
阿米卡星属于哪种结构类型的抗生素
A.小便点滴不通,或量极少而短赤灼热,小腹胀满,口苦口黏,舌质红,苔黄腻,脉沉数B.小便不畅,或点滴不通,咽干,烦渴欲饮,呼吸急促,舌苔薄黄,脉数C.小腹坠胀,时欲小便而不得出,或量少而不爽利,精神疲乏,食欲不振,气短语声低细。舌质淡,苔薄,脉象沉弱
()是独立中介理财机构理财发展方向。
王娟的丈夫是一家公司的经理,因与公司的秘书产生了感情,提出与王娟离婚。离婚后的王娟感觉自己的生活失去了意义,每天把自己关在家中,情绪低落,不愿与家人沟通,喜欢自言自语,有时会大笑,笑完后又大哭。家人感觉王娟的精神出现了问题,找到社区工作者小雷寻求帮助。小雷
张闻天
A、ThestoriesofHarryPotterarecriticizedinsomeothercitiesinU.SexceptNewMexiconB、YoungpeoplearefascinatedwithH
最新回复
(
0
)