首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
67
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
明长城的起止地点是()。
1951年底到1952年春,中国共产党在党政机构工作人员中开展的运动是()。
第一国际成立的时间是()。
明代中后期,苏州、松江、嘉兴、()、杭州五府,堪称江南最繁华的城市。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
商族的远祖可追溯到尧舜时代的契,传说契母简狄吞玄鸟之卵而生契。契便是商人的祖先。以此传说推测,商族是以()为图腾的部落。
中国共产党在敌后战场上开创的第一块根据地是()。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
随机试题
腰痛连腹多因()
房地产开发企业资质等级证书不是企业领取营业执照的必备条件。[2004年考题]()
《中华人民共和国职业病防治法》对用人单位在职业病的管理上的要求有()。
按《UCP600》规定,下列有关海运提单中货物描述的说法正确的有()。
现代幼儿园教师的职业角色有()。
“其身正,不令而行;其身不正,虽令不从。”这句话应用到教师对学生的教育管理中,体现了教育心理学中的哪个学习理论?()
下列继承人中,()是第一顺序继承人。
一射手进行射击,击中目标的概率为p(0<p<1),现在他领到5发子弹,进行射击直到命中目标或子弹用完为止,以X表示他射击实际脱靶的次数,则P{x=1}=__________.
Thispassagechieflydiscusses______.Whenapopulationdoubles,thecountryinvolvedneedstwiceasmuchofeverything,inclu
彼は確信______顔をして私たちに言った。
最新回复
(
0
)