首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
90
问题
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
根据设计思想,采用C、C++或Java语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: bool VerifySquenceOfBST(int squence[], int length) { //判断非法输入数组 if(squence==NULL||length<=0) return falSe; //将数组的最后一个值赋值给根结点的值 int root=squence[length一1]; //在二叉排序树中左子树的结点值小于根结点的值 int i=0; for(;i<length-1;i++) { if(squence[i]>root) break; } //在二叉排序树中右子树的结点值大于根结点的值 int j=i; for(;j<length—1;j++) { if(squence[j]<root) return falSe; } //判断左子树是不是二叉排序树 bool left=true; if(i>0) left=verifySquenceofBST(squence,i); //判断右予树是不是二叉排序树 bool right=true; if(i<length-1) right=verifySquenceOfBST(squence+i,length-i-1); return(left &&right); }
解析
转载请注明原文地址:https://kaotiyun.com/show/Klxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
我国第一部系统的史学理论著作是()。
“冷战”局面的形成是由于()①美国试图称霸世界②苏联政治军事力量增强③欧亚社会主义阵营形成④美苏展开核军备竞赛
“文化大革命”发动的两个纲领性文件是()。
下列战国时期的城市中,同为诸侯国都城和冶铁中心的是()。
唐朝时,从中国传到大食的手工技术是()
建立帝国财政收支总账和元首金库,直接控制和调节全国财政收支的是()。
重庆谈判的焦点问题是()
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭重创
联共(布)“十五大”以后,新经济政策被逐步取消,根本上是由于()。
试述中国共产党诞生的历史条件和意义。
随机试题
Comparisonandcontrastareoftenused______inadvertisements.
方某,男,42岁。痢下赤白脓血,腹痛隐隐,心中烦热,咽干口燥,午后潮热,体倦乏力,舌红苔少,脉细数。辨证( )。
A、诱发心绞痛B、白细胞减少C、甲状腺功能减退D、血管神经性水肿E、肝功能不良放射性碘的主要不良反应是
地基基础丁程质量验收时,应提供()等技术文件和记录。
如图,直线l经过第二、三、四象限,l的解析式是y=(m一2)x+n,则m的取值范围在数轴上表示为()
花间词派的鼻祖是()。
一些公务人员认为,多干事多出错,少干事少出错,不干事不出错。对此,你怎么看?
丈夫和妻子讨论孩子上哪所小学为好。丈夫称:根据当地教育局最新的教学质量评估报告,青山小学教学质量不高。妻子却认为:此项报告未必客观准确,因为撰写报告的人中有来自绿小小学的人员,而绿小小学在青山小学附近,两所学校有生源竞争的利害关系,因此青山小学的教学质量其
A、B、C、D、A
A、Hobbiesandsports.B、Timeandenergy.C、Pleasureandrelaxation.D、Skillsandpartners.BGoodwin女士提到,要达到“玩乐”的境界需要投入时间与精力(aco
最新回复
(
0
)