首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
63
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
(北魏孝文帝)“初谋南迁,恐众心恋旧,乃示为大举,因以胁定群情,外谋南伐,其实迁也。1日人怀土,多不所愿,内惮南征,无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。
近代中国派遣第一批留学生是在()。
试述中国共产党诞生的历史条件和意义。
评析郑和下西洋的历史条件和意义。
印加人记载事物使用的方法是()。
进程P0和P1的共享变量定义及其初值为:booleanflag[2]:intturn=0:flag[0]=FALSE;flag[1]=FALSE;若进程P0和P1访问临界资源的类C伪代码实现如下:则并发执行进程P0和P1时产生的情形是____。
随机试题
GB/T27025-2008《检测和校准实验室能力的通用要求》规定:“当需要利用期间核查以保持设备校准状态的可信度时,应按照规定的程序进行。”“校准状态”是指_________校准结果的状态。
下列行为中,符合房地产经纪人销售礼仪的是()。
采用具名团体技术进行决策的优点主要有()。
工商行政管理机关在促进现代企业制度的建立中应起的作用有()。
中国共产党建立“三三制”政权是在()时期。
焦急:焦躁:着急
我国独立自主的和平外交政策的基本含义是()。
帮助求助者解除心理问题的具体内涵指的是()。
已知总体X的概率密度只有两种可能,设H0;f(x)=对X进行一次观测,得样本X1,规定当X1≥时拒绝H0,否则就接受H0,则此检验犯第一、二类错误的概率α和β分别为__________。
______thereislittlewecandotomodifytheweather,wecanatleastknowwhatkindofweathertoexpect.
最新回复
(
0
)