首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
76
问题
输入一整数数组{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年代后南斯拉夫的发展变化。
简述苏联和南斯拉夫之间的冲突。
下列关于湘军的叙述中不正确的是()。
1951年底到1952年春,中国共产党在党政机构工作人员中开展运动的内容是()。
隋在统一全国的过程中,平定江南是一个重要的部分,帮助完成岭南一带平定的是()
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:该指令系统最多可有多少条指令?该计算机最多有
随机试题
在PC机中,音响通过声卡插在主板的()中。
苹果酸一天冬氨酸穿梭的意义
5分钟Apgar评分低于多少时,神经系统受损的可能性较大
妊娠期阑尾位置随孕周增长的变化特点是
下列哪个内分泌腺的激素分泌不足时,引起呆小症
下列选项中,不属于就业保护方面的政策的是()
施工现场根据危险部位的性质不同,需要分别设置禁止标志、警告标志、指令标志、()等安全标志,夜间留设红灯示警。应根据工程部位和现场设施的变化,及时调整安全标志牌设置。
注册会计师了解被审计单位所处法律与监管环境时,了解的内容包括()。
(2014年真题)甲路过某饭馆时见万某酩酊大醉,便冒充万某的朋友上前将其扶走,到一偏僻的地方后,将万某随身携带的价值5000元的财物全部取走。甲的行为构成
JohnwastheonlysonofaveryrichAmericanbusinessman(商人).Usuallyhewastakentoschoolbythedriverinhisfather’sbeau
最新回复
(
0
)