首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
110
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
论述中国封建社会中后期赋税制度变迁的主要内容。
1934年9月苏联加入国联,对此说法错误的一项是()。
夏王朝建立后,将其领土划分为九州,派九牧进行治理,在九州范围内根据土地的肥沃程度缴纳贡赋,称为()。
西欧早期资产阶级反封建斗争以反天主教会的方式进行,主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起
在1875年宪法中关于法国立法权的叙述,不正确的是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
美国主张建立国际联盟的主要目的是()。
阅读下列材料,并回答问题:当时帝国地跨欧亚非三洲。地中海成为它的内湖。境内农业、手工业和商业发展起来,海路畅通无阻,陆路纵横交错、四通八达,促进了贸易发展,也有利于信息传递和军队调防。帝国同北欧、印度、中国都有贸易往来,中国的丝绸也传到帝国。原来较落后的
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
隋朝大运河中哪一段河道的地理位置最接近于春秋时期即已开通过的运河()?
随机试题
直接反映了公司的营运能力的是存货的质量和__________。
A.局限B.向颈部传导C.向左液下传导D.向心尖部传导E.向胸骨下端传导二尖瓣狭窄的杂音()
逆证候性质而治的治法是
甲公司与乙银行有长期的业务往来,2000年双方订立一个借款合同,乙方借给甲方10万元,于10月10日交付,甲方1年后还清。乙方要求甲方提供担保,甲遂请丙公司为该笔贷款提供保证担保。后来由于丙公司经营不善,乙公司有些担心其所担保的债权,遂与甲商议,乙银行再借
下列工程项目目标控制的方法中,( )是动态分析方法。
下列有关印花税的处理,正确的有( )。
①科学进步的简单模式是提出理论,并从中推导出假设,然后假设接受各种技术或方法的检验。如果假设通过了检验,该理论就得到了某种程度的确证;如果假设被实验证伪,这个理论就得做出某种程度的改变,或者被一个新理论所取代。②科学中有很多理论已经被充分证实并被
虚假安全:指在高度紧张状态下大脑处于极度兴奋中,反而不容易出问题;而在接近成功状态下精神越来越放松,顿时有了安全感,然而恰恰是这一瞬间的放松,酿成大祸。下列属于虚假安全的是()。
声卡的组成很简单,它主要由一块声频处理芯片,一块音频综合芯片和一块放大器电路组成。波形声音输入计算机时,信号的取样与量化是由【 】完成的。
Thetraditionalpaintingsare(exhibited)onthesecondfloor.
最新回复
(
0
)