首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
admin
2017-11-20
68
问题
输入一整数数组{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[1ength-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; } //判断左子树是不是二叉排序树 booi left=true; if(i>0) left=verifySquenceOfBST(squence,i); //判断右子树是不是二叉排序树 bool right=true; if(i<length-i) right=verifySquenceOfBST(squence+i,length-i-1); return(1eft&&right); }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/ujRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
夏王朝建立后,将其领土划分为九州,派九牧进行治理,在九州范围内根据土地的肥沃程度缴纳贡赋,称为()。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
冶铁技术中的“淬火法”在()已开始应用,大大提高了铁器的坚韧和锋利程度。
《道威斯计划》的实施所产生的直接结果是()。
下列()不是挺进大别山的主力。
下列关于《凡尔赛和约》的说法,全部错误的是()。①《凡尔赛和约》中不许德国设防区是莱茵河西岸50公里以内区域②《凡尔赛和约》中,战胜国处置德国的全部海外殖民地的方式是“托管制”③和约有关德国疆界问题,把原属波兰的领上基本上归还波兰④
试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
制瓷业是光彩夺目的一个手工业部门,北宋的制瓷业的重心在黄河流域和中原地区。回答问题:北宋的四大名窑是()
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
关于法条关系,下列哪一选项是正确的(不考虑数额)?()(2016/2/11)
__________在北京创立了我国第一家会计师事务所,标志着我国注册会计师制度正式诞生()
________________,大庇天下寒士俱欢颜,风雨不动安如山。(杜甫《茅屋为秋风所破歌》)
背景:某办公楼工程,地下1层,地上12层,总建筑面积26800m2,筏板基础,框架剪力墙结构。建设单位与其施工总承包单位签订了施工总承包合同。按照合同约定,施工总承包单位将装饰装修工程分包给了符合资质条件的专业分包单位。合同履行过程中,发生了下
招标控制价的编制依据有()。
会计职业道德宣传教育主要包括的形式有()。
甲公司为一家制造企业,适用的增值税税率为16%,商品销售全部符合收入确认条件,销售成本月末一次结转,M产品的单位成本为80元。2016年7月该公司发生下列业务。(1)1日,向乙公司销售M产品8000件,开具的增值税专用发票上注明的价款为80万元
十进制数32转换成二进制整数是()。
Itwastheworsttragedyin【C1】______history,sixtimesmoredeadlythantheTitanic.WhentheGermancruiseshipWilhelmGu
[A]benefits[B]different[C]eventually[D]instruments[E]moving[F]multiple[G]unsalaried[H]number[I]paid[J]
最新回复
(
0
)