首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
75
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
1939年8月23日,苏德双方签订了()和《秘密附属议定书》,划定了双方在东欧的势力范围。这一条约使德国得以进攻波兰,使第二次世界大战终于爆发。
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
在西欧列强海外殖民扩张进程中,各国之间相互争夺海上霸权。18世纪末,英国在争霸中取得胜利的根本原因在于()
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
太平天国作为几千年来农民运动的高峰,所遇到的历次农民运动中不曾有过的新情况是(
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
随机试题
Trainingastronauts______notaneasything.
Theladysaidshewouldbuyagiftforherdaughterwiththe______.
Morethanfortythousandreaderstoldusthattheylookedforinclosefriendships,whattheyexpected【C1】______friends,whatth
治疗肺炎球菌性肺炎首选的药物为
慢性肾炎患者水肿明显,尿蛋白(++++),肾功能检查正常。其饮食宜
林甲起诉后能否申请法院责令杂志社停止本期的发行?依据何在?若林乙对赔礼道歉的判决内容申请强制执行,法院对本案义务人可采取哪些措施?
申请人对行政机关作出的具体行政行为不服,依法申请行政复议,而复议机关无正当理由拒绝受理或不予答复的,申请人可通过何种途径寻求法律救济?( )
在财产损失保险中,由于( )造成的直接损失,保险人不负责赔偿。
下列程序段运行的结果为publicclassTest{staticvoidprint(Strings,inti){System.out.println("String:"+s+",int:"+i);
Thecentralproblemofeconomicsistosatisfythepeople’sandnation’swants.Theproblemwearefacedwithisthatour(1),
最新回复
(
0
)