首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
admin
2017-04-28
40
问题
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
根据设计思想,采用C、C++或Java语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: int rdfs (ADJLIST g,int vi) { int i,count, yes; yes=0; count=1; stack s; for(int i=0; i<n; i++)visited[i] =0;//初始化访问标记数组 push (vi,s) ; visited [vi]=i; //初始化 while ( ! empty (s) &&yes—=0) { int w=top (s) ; p=g[w],firstarc; while(p !=NULL&&visited[p—>adj data]) { p=p—>next; if (p==NULL) pop (s); else { w=p—>adjdata; visited [w]=1; count++; push (w, s) ; } } } if(count==n)//n为该有向图中的结点数 yes=1; return yes; break; } //在二叉排序树中右子树的结点值大于根结点的值 int j=i; for(;j<length—1;j++) { if (sequence[j]<root) return false; } //判断左子树是不是二叉排序树 bool left=true; if (i>0) left=verifySquenceOfBST((squence,i), //判断右子树是不是二叉排序树 bool right=true; if (i<length—1} right=verifySquenceofBSlf squence+i,length—i—1); return (left&&right), }
解析
转载请注明原文地址:https://kaotiyun.com/show/2XRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
巴黎和会召开的时间是()。
1543年发表解剖学专著《人体结构论》的是()。
玛雅人的金字塔主要功能是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
随机试题
发生筋膜间隙综合征的主要原因是
治疗脑水肿的首选药是
甲为某合伙企业的合伙人,在企业经营期间,甲因车祸丧生,甲的合法继承人乙年方工5岁,该合伙企业的合伙协议中约定合伙人死亡经合伙人一致同意的由其继承人继承合伙人资格。依我国合伙企业法规定,以下各项中不正确的有()。
甲公司2013年至2018年发生以下交易或事项:2013年12月31日购入一栋办公楼,实际取得成本为6000万元。该办公楼预计使用年限为20年,预计净残值为零,采用年限平均法计提折旧。因公司迁址,2016年6月30日甲公司与乙公司签订租赁协议。该协议约
计算机网络的目标是实现()。
我们虽是同班同学,但______并不熟悉。
Themostprolificwriterisnotnecessarilythebest.
FiveCommonMistakesinConversationandTheirSolutionsI.NotlisteningA.Problem:mostpeopledon’tlisten—waiteagerlyf
Englishhasbeensuccessfullypromoted,andhasbeeneagerlyadoptedinthegloballinguisticmarketplace.Onesymptomoftheim
A.hardlyB.chemistryC.virtuallyD.counterpartsE.testedF.geometryG.comfort
最新回复
(
0
)