首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
29
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
下列会议中,讨论有关对日本法西斯问题的有()。①开罗会议②德黑兰会议③雅尔塔会议④波茨坦会议
《三家村札记》是由()三位作家共同完成的。
前期的新文化运动不能给灾难深重的中国指明真正的小路,主要是由于()。
古希腊是西方文明的发源地,古希腊雅典的民主政治则开启了西方民主制度的先河。下列关于雅典民主政治的说法,符合史实的有()。①民主政治时期的雅典没有国王②公民大会是雅典国家的最高决策机构③伯里克利时期,雅典民主政治达到了顶峰④包
1991年,南斯拉夫联邦解体,分裂为新国家的数目为()。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
16世纪英国国王推行宗教改革的根本目的是()
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
1942年太平洋战争爆发后,日本先后夺取了焦作、开滦等煤矿,华北沦陷区每年向日本输送的原煤达800万吨。这说明日本在沦陷区进行经济掠夺的直接目的是()。
随机试题
马克思主义认为,民族解放运动的前途有______、______。
对于流窜犯的最长拘留时间是多少天?( )
某县公安局刑警队接到群众报案,在某一水库的水面上发现一具漂浮的尸体。刑警队马上派人赶到现场勘验、检查,以收集证据。根据规定,公安人员收集的证据能够将案件事实证明到何等程度时,公安机关就应当对此案立案侦查?( )
法国是美食之国,非常讲究酒水与菜肴的搭配,以下正确的选项是()。
我国于()年正式颁布《幼儿园工作规程》。
中国传统文化中,对孕妇及产后妇女提出了诸多禁忌,如忌风、忌水、忌口等等,如今这类禁忌与时俱进。又加了一条“忌辐射”。那银光闪闪的防辐射服,已经成为中国孕妇的“标配”。最近有专家却称.防辐射服没必要穿,其根本就不能起到防辐射的作用。下列各项如果为真.哪项能够
公车上书
【2008-47】作为教师,不一定要有明确的教育目的,但必须要有明确的教学目标。
平均利润率形成的过程,同时就是()
Whydidn’tpeoplebegintouseunmannedvehiclesinunderseaexplorationuntilrecently?Itisbecauseofthe______.Why
最新回复
(
0
)