首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
38
问题
输入一整数数组{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://jikaoti.com/ti/wWfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
在巴黎和会上获利最大的两个国家是()。
洋务派创办军事工业的方式是()。
1950年底到1951年,中国共产党在全党范围内开展的运动是()。
根据下列史料,说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆,久为两国人民通商之地。从今日起,改革从前惯例及岁遣船等事,以此次新订条款为标准,办理贸易事务,朝鲜政府开放第五款所载两口岸,准日本人民往来通商,随意在该两地租借地
记载了用竿标日测影以求日高的方法,并认识了勾股定理的算书是()。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
随机试题
患者,男,32岁。反复咳嗽咳脓痰10年,间断咯血,痰量40ml,胸片示两下肺纹理紊乱。错误的措施是
汽车空调系统常用的检漏方法有哪些?
________.
错语是指
治疗军团菌应首选()。
下列关于原始凭证的书写表述有误的是()。
下列各项中,不属于证券公司证券自营业务买卖对象的是()。
根据《中华人民共和国公司法》的相关规定,公司解散后,有限责任公司的清算组由()组成。
全球性生态问题的出现,凸显了地理环境对社会发展的重要作用。下列观点正确的有
【B1】【B10】
最新回复
(
0
)