首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
101
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
1901一1939年间美国历届政府在国内经济活动中职能作用的演变。
简述苏联和南斯拉夫之间的冲突。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特,一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。
1947年英国通过《蒙巴顿方案》,随后印度和巴基斯坦独立,形成印巴分治局面,在克里米尔地区冲突埋下隐患,《蒙巴顿方案》中印巴分治的依据
循环队列用数组A[0..m~1]存放其元素值,已知其头尾指针分别为front和rear,则当前元素个数为()。
随机试题
在“商品—货币—商品”的流通过程中,“商品—货币”阶段的变化是“商品的惊险的跳跃”。这个跳跃如果不成功,摔坏的不是商品,而是商品所有者。这说明()。
社会主义初级阶段是从上世纪中叶我国社会主义改造基本完成、进入社会主义社会,到本世纪中叶基本实现社会主义现代化。()
()初凝时间不早于45min,终凝时间不迟于10h。
关于加筋土挡土墙施工要求的表述中,正确的有()。
任何填开发票的单位和个人必须在发生经营业务并确认营业收入时,才能开具发票,如果未发生经营业务则( )。
2004年A取得的股息红利性质收入应纳个人所得税()万元。2004年B取得的股息红利性质收入应纳个人所得税()万元。
以下向境外支付外汇的情形,需要向税务机关备案的有()。
1903年,美国心理学家______编著出版的《教育心理学》,是西方第一部以“教育心理学”命名的专著,由此确立了教育心理学的独立体系。
设f(x)在区间(一∞,+∞)上连续且满足则在(一∞,+∞)上,当x≠0时,f(x)()
若按功能划分,软件测试的方法通常分为【】测试方法和黑盒测试方法。
最新回复
(
0
)