首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
admin
2017-11-20
72
问题
输入一整数数组{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[1ength-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; } //判断左子树是不是二叉排序树 booi left=true; if(i>0) left=verifySquenceOfBST(squence,i); //判断右子树是不是二叉排序树 bool right=true; if(i<length-i) right=verifySquenceOfBST(squence+i,length-i-1); return(1eft&&right); }
解析
转载请注明原文地址:https://kaotiyun.com/show/ujRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列选项中不是严复的著作的是()
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
改革开放以来,乡镇企业的异军突起,其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
全国高校院系调整的具体时间是()。
试分析淝水之战前后南北政局的特点及其变化。
判断英国工业革命基本完成的主要依据是()
曾被日本维新派人士视为“枕中鸿宝”,对日本明治维新产生重要影响的著作是()。
罗斯福新政的中心措施是对()的调整。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
Lifewithoutbooksisincomplete.Booksinfluencethedepthandbreadthoflife.Theymeetthenatural【B1】______forfreedom,for
I’vemadean______foryoutoseethedoctorat5’oclock.
关于心电图临床诊断价值的表述,不正确的是
均价的制定参照比较楼盘时的比较因素有()。
下列选项中,属于高效减水剂的是()。
根据规定,企业职工伤亡事故统计实行以()为主的制度。
1949年7月,中央决定在华北社会部和华北公安部的基础上组建中央军委公安部。( )
据统计,从1978年到2003年,中央下发的关于农业和农村工作的文件共计56个,党的十六大以来,我们党坚持把解决好“三农”问题作为全党工作的重中之重,从2004年开始连续下发4个“一号文件”,大力推进社会主义新农村建设,加快农业和农村发展,促进农民增收。特
房地产业作为国民经济的基础产业和主导产业,其发展历程不是一帆风顺的。我国在20世纪50年代中期到20世纪80年代初,房地产市场是不存在的。在这期间土地资源和房屋资源的配置不通过市场,而直接由政府的计划指令配置,公开的房地产市场基本被取消。因此,从20世纪8
孔子(Confucius)的学生樊迟问什么是“仁”,孔子回答说:“爱人”。这是孔子对“仁”,的最重要的解释。“爱人”,是一种普遍的爱。孔子又强调爱人作为一种普遍的道德原则,必须由爱自己的父母开始。孔子不相信一个不爱自己父母的人能去爱普天下的人。孔子说:
最新回复
(
0
)