首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
105
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
简述20世纪50年代后保加利亚、罗马尼亚和阿尔巴尼亚的变化。
《四库全书》编成后,纪昀等又写成()200卷,把每本书的渊源、版本、内容都作了提纲性的介绍,是一部重要的目录学著作。
古埃及中王国时期出现了一个新兴的手工业部门,对世界文明做出了巨大贡献。这一新兴的手工业部门是()。
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》,强调要()。
中华人民共和国恢复了在联合国合法席位的时间是()。
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
古文经学家()为了反对今文经派根据隶定的古书穿凿附会而曲解经文,于是编成一部《说文解字》,共收小篆及其他古文字9353个,逐字注释其形体音义。
三大战役的先后顺序是()
中古时代实行索贡巡行赋税征收方式的国家是()。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
随机试题
AnoldIndianstorysaysthatthegameofchess(国际象棋)wasinventedbySissaBen,PrimeMinisterofKingShirham.Assoonasthe
Ⅱ型呼吸衰竭应给予吸氧的浓J蔓是
63岁妇女出现血性白带,除生殖系统恶性肿瘤外,考虑有哪些疾病可能
怀疑再生障碍性贫血的老年患者行穿刺的最佳部位是
A.大黄B.火麻仁C.京大戟D.巴豆E.芫花治疗寒积便秘,宜用()
某公司从一家跨国公司购进一套生产速溶咖啡的技术资料,因技术力量薄弱,无法生产出合格产品,遂与某科技大学签订技术合同,约定由该公司提供技术开发所需科研经费,付酬10万元,并派5名技校毕业生协助参与开发工作,主要是整理资料,购买器材等,但对开发出的成果如何申请
素质教育是指一种以提高受教育者诸方面素质为目标的教育模式,它重视人的()。
根据以下资料。回答下列题。2011年,我国能源生产总量达到31.8亿吨标准煤,是世界第一大能源生产国。其中,原煤产量35.2亿吨,原油产量稳定在2亿吨,成品油产量2.7亿吨。天然气产量快速增长,达到1031亿立方米。电力装机容量10.6亿千瓦。年
______foreverarethedays______Iwasyoung.
Splittingdinnercheckscancauseasplittingheadache,evenwhenthedinersaremathematicsmajors.Threecomputerscience【B1】_
最新回复
(
0
)