首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
37
问题
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:首先,使用后序遍历得到的序列的最后一个结点一定是根结点的值。而根结点前面的整数序列可分为两部分:第一部分是左子树结点的值,它们都比根结点的值小;第二部分是右子树结点的值,它们都比根结点的值大。 以数组(5,7,6,9,11,10,8)为例,后序遍历结果的最后一个数字8就是根结点的值。在这个数组中,前3个数字5、7和6都比8小,是值为8的根结点的左子树特点;后3个数字9、11和10都比8大,是值为8的根结点的右子树结点。接下来需要用同样的方法确定与数组每一部分对应的子树结构。很明显,这是一个递归的过程。对于整数序列5、7和6,最后一个数字6是左子树的根结点的值。数字5比6小,是值为6的结点的左子结点,而7则是它的右子结点。同样,在序列9、11和10中,最后一个数字10是右子树的根结点的值,数字9比10小,是值为10的结点的左子结点,而11则是它的右子结点。 再举一个反例。例如,整数数组{8,1,6,5},后序遍历的最后一个数是根结点,因此根结点的值是5。由于第一个数字8大于5,冈此可以肯定此二叉排序树的根结点上没有左子树,数字8、1和6都是右子树结点的值。但发现在右子树中有一个结点的值是1,比根结点的值5小,这就违背了二叉排序树的定义。因此,不存在一棵二叉排序树,它的后序遍历的结果是8、1、6、5。
解析
转载请注明原文地址:https://kaotiyun.com/show/7lxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
体格拉特.帕拉沙尔三世改革的主要内容及其结果。
周王室的两大官僚系统是()。
唐朝时,从中国传到大食的手工技术是()
下列选项中,不是由晁错提出的是()
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
近代中国派遣第一批留学生是在()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
随机试题
管理控制最终是通过()的行动来验证的。
A.上斜肌B.下斜肌C.外直肌D.眼轮匝肌E.瞳孔开大肌动眼神经支配的肌肉是
A、山药B、黄芪C、当归D、鹿茸E、阿胶平补气阴,为治气虚或气阴两虚之佳品的药物是
在利率、现值相同的情况下,若计息期数n=l,则复利终值和单利终值的数量关系是()。
下列项目中,属于费用要素内容的有()。
下列因素中会导致一国货币升值的是()。
卫生部党组书记张茅日前在全国卫生工作会议上指出,2012年要把()作为卫生工作的重要管理目标,合理确定费用增长控制指标,并建立考核机制。
甲、乙两名篮球运动员投篮的命中率分别为0.8和0.75。令每人各投一球,则甲命中且乙未命中的概率为:
Theblind,overweightpatientinthewheelchairhasterriblepaininherbackandburningpaininherlegs.Nowhershoulderhas
Forthispart,youareallowed30minutestowriteashortessayentitledMoreAttentionShouldBePaidtoLeft-BehindChildren.
最新回复
(
0
)