首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
71
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
《道威斯计划》的实施所产生的直接结果是()。
氏族公社形成的条件和基本标志是()。
第二次世界大战期间,苏、美、英三国首脑达成的协议中未能实现的是()。
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
关于德意志宗教改革的说法不正确的是()
第二次世界大战后,国际关系最大的变化是()。
1973年,以美元为中心的资本主义世界货币体系崩溃,反映出()。①国际金融领域内美元地位衰落②美国由债权国变为债务国③资本主义国家实力的对比发生了新的变化④美国的世界经济地位严重动摇
材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特,一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
随机试题
随着技术的进步和客户需求的进一步成熟的推动,当前主流市场的SSLVPN和几年前面市的相比已经发生很大的变化,主要表现在以下哪些方面
SecretsforaHappierYouSomepeoplearenaturallyblessedwithacheerfulcharacter.Theyspreadwarmthandsunshinewhere
甲状腺髓样癌的病理特点是
A.肿瘤较大,内为均质低回声,可有囊性变,CDFI:点状血流信号B.肿瘤较大,内回声不均,强弱不等,CDFI:丰富血流信号C.多单发,仅10%多发或双侧病变,瘤体小,1cm左右D.多发,仅10%单发或单侧病变,瘤体小,1cm左右E.肾上腺区三角形边
女,32岁,刺激性咳嗽,干咳,偶有少量黏稠痰,受寒冷刺激加重,伴气促,每天夜间、清晨均有剧咳而影响睡眠,用过青霉素、头孢菌素和多种祛痰止咳剂,疗效不满意。查体:双肺散在干性罗音,心脏正常。胸片示:心肺无异常,血白细胞12×10/L。
下列有关终身寿险和定期寿险的论述不正确的是( )。
金融期货交易的是合约。下列( )不属于交易所统一规定的范畴。
单位要组织工作成果宣传展示。需要邀请上级领导和媒体参加,领导让你负责组织此次活动。你会做哪些准备工作?
StevelandMorrisisahouseholdnameinAmerica.AskStevelandMorrisandhe’lltellyouthatblindnessisnotnecessarilydisab
Specializationcanbeseenasaresponsetotheproblemofanincreasingaccumulationofscientificknowledge.Bysplittingupt
最新回复
(
0
)