首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
admin
2017-04-28
111
问题
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:首先,使用后序遍历得到的序列的最后一个结点一定是根结点的值。而根结点前面的整数序列可分为两部分:第一部分是左子树结点的值,它们都比根结点的值小;第二部分是右子树结点的值,它们都比根结点的值大。 以数组{5,7,6,9,1 1,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/1XRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1901一1939年间美国历届政府在国内经济活动中职能作用的演变。
一战从欧洲的战争变成全球范围的战争是在()。
美国主张建立国际联盟的主要目的是()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
在1875年宪法中关于法国立法权的叙述,不正确的是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
随机试题
某焊工在坠落高度基准面10m高处进行焊接与切割作业,其高处作业的级别为()。
多数氨基酸有D一和L一两种不同构型,构型的改变涉及共价键的破裂。()
下列属于第二级预防措施的是
背景资料:某集团公司项目部承担某段铁路工程施工,其中一部分为邻近干线营业线增二线,另一部分为双绕新线。主体工程包括石方路堑拓宽、小桥顶进、涵洞接长、新建高桥与隧道、深路堑、高填方及一般路基工程;附属工程包括道口接长及路基防护等。施工期间既有线正常
疏浚工程中浅埂长度为()m时,应进行返工处理。
期货公司在中国证监会不同派出机构辖区变更住所的,应当符合下列( )条件。
A公司欠B公司60万元到期货款无力偿还。B公司经过调查后得知下列情况:C公司与A公司之间存在买卖合同,A公司已经付款,但C公司未按期交货;A公司与D公司之间存在大型机器设备买卖合同,D公司分期付款,在付清全部货款之前A公司保留该机器设备的所有权,现D公司已
某军医转业至一家地方医院,在一定期间内取得下列收入,其中按照我国个人所得税法规定应当缴纳个人所得税的项目有()。
“脚踏黄河水倒流,搬来泰山做枕头,决心苦战十五年,赶上英国不发愁。”这首新民歌创作的时代背景是“大跃进”时期。()
A、Workonareport.B、Pickhersonfromschool.C、Meetthemaninhisoffice.D、Preparedinnerforherson.A由女士所说的Mysonwillb
最新回复
(
0
)