首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
admin
2014-04-17
88
问题
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
根据设计思想,采用C、C++或Java语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: bool VerifySquenceOfBST(int squence[], int length) { //判断非法输入数组 if(squence==NULL||length<=0) return falSe; //将数组的最后一个值赋值给根结点的值 int root=squence[length一1]; //在二叉排序树中左子树的结点值小于根结点的值 int i=0; for(;i<length-1;i++) { if(squence[i]>root) break; } //在二叉排序树中右子树的结点值大于根结点的值 int j=i; for(;j<length—1;j++) { if(squence[j]<root) return falSe; } //判断左子树是不是二叉排序树 bool left=true; if(i>0) left=verifySquenceofBST(squence,i); //判断右予树是不是二叉排序树 bool right=true; if(i<length-1) right=verifySquenceOfBST(squence+i,length-i-1); return(left &&right); }
解析
转载请注明原文地址:https://kaotiyun.com/show/Klxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
元封六年(前105),西汉以宗室女细君与乌孙王和亲。细君死后,又以宗室女()和亲,巩固了汉与乌孙的关系,使乌孙成为牵制匈奴的重要力量。
20世纪初,革命派与改良派论战的中心问题是()。
在下列我国建国之后的外交活动中,能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊
下列著作不属于被后世称为清代汉学的“不祧祖先”之人的作品的是()
苏俄实施新经济政策的根本目的是()。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
西南军阀跟随孙中山拥护护法运动的目的是()。
评析郑和下西洋的历史条件和意义。
格拉古兄弟改革的内容和结果是什么?
某微机的寻址范围为64KB,其存储器选择器信号为M,接有8片8KB的存储器,试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据,以4000H起始地址的存
随机试题
矛盾律对思维形式的要求包括两个方面:(1)()。(2)()。
引起下肢静脉曲张的主要原因有
欣欣美容医院在为青年女演员欢欢实施隆鼻手术过程中,因未严格消毒导致欢欢面部感染,经治愈后面部仍留下较大疤痕。欢欢因此诉诸法院,要求欣欣医院赔偿医疗费并主张精神损害赔偿。该案受理后不久,欢欢因心脏病急性发作猝死。网络名人洋洋在其博客上杜撰欢欢吸毒过量致死。下
项目后评价的全过程回顾和总结一般按()阶段进行。
火灾报警控制器在检测时,实际安装数量在6~10台者,抽验()台。
()情况下,借款人的营运能力较好。
流动资金贷款展期期限累计不得超过原贷款期限;固定资产贷款展期中,中期贷款(3~5年期)展期期限不得超过原贷款期限的一半,长期贷款(5年以上)展期期限不得超过3年,可以多次展期。()
科学发展观第一要义是()。
人在遇到危险的时候会爆发出比平时更大的力量和产生更敏捷的反应.此时其体内激素水平明显提高的是:
数据库设计中反映用户对数据要求的模式是( )。
最新回复
(
0
)