首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
64
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
1928年2月召开的国民党二届四中全会,规定()为国民政府军政最高机关。
从1939年春天起,国共双方军队在驻防结合部的摩擦冲突不断升级,不是这一时期惨案的是()
以城市为重点的整个经济体制改革的中心环节是()。
曹操统一北方的关键战役是()。
在下列我国建国之后的外交活动中,能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
西汉时期,张骞第一次出使西域的主要目的是()
下列对凡尔赛和约中有关德国疆界问题的表述,正确是()。
“瓜步之战”发生在下列哪两个政权之间?()
世界古代历史上,对东西方文化交流、传播作出突出贡献的是()
随机试题
一个单周期处理器,各主要功能单元的操作时间为:指令存储器和数据存储器为0.3ns,ALU为0.2ns,寄存器文件为0.1ns,则该CPU的时钟周期最少应该是()。
劳动保障行政部门对违反劳动保障法律行为的调查时间一般为()
引起主动脉瓣关闭不全的最常见原因是
中性粒细胞与淋巴细胞比例两次相等的年龄是()。
流行性脑脊髓膜炎脑脊液典型生化改变为
某企业集团财务主管王某到某税务师事务所进行以下咨询,请根据王某提供的资料,简要回答下列问题,并说明理由。集团所属某子公司因业务发展需要,分立成三家子公司,分解前,有100万元的欠税,现主管税务机关要求分立后的一家效益好的企业偿还这100万元的税款,请问
某工艺品厂为增值税一般纳税人,2011年12月2日销售给甲企业200套工艺品,每套不含税价格600元。由于部分工艺品存在瑕疵,该工艺品厂给予甲企业15%的销售折让,已开具红字专用发票。为了鼓励甲企业及时付款,该工艺品厂提出2/20,n/30的付款条件,甲企
根据所给信息,2007年日本人均电影消费额约为()。2007年日本进口影片收入占票房总收入的比例与本土影片收入占票房总收入的比例之差为()。
(深圳2012—4)11,14,12,20,13,30,(),44,15,()
系统软件的功能是______。
最新回复
(
0
)