首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
61
问题
输入一整数数组{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/rjRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
西汉初年,西域共有36国,其中以()人口最多。
明中叶后,商业资本比较活跃,活动于全国范围的商人和商帮中最为著名的是()。
1973年,以美元为中心的资本主义世界货币体系崩溃,反映出()。①国际金融领域内美元地位衰落②美国由债权国变为债务国③资本主义国家实力的对比发生了新的变化④美国的世界经济地位严重动摇
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
中古时代实行索贡巡行赋税征收方式的国家是()。
秦始皇焚书时未被列入焚书范围的是()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
记载了用竿标日测影以求日高的方法,并认识了勾股定理的算书是()。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
随机试题
滑动轴承的摩擦状态大多数情况下处于()。
都是联绵词的一组是()
A.alotofmoneyB.expresspublicfeelingonlocalissuesC.morningD.localpeopleE.nationalissuesF.localissuesMany
冠状动脉CTA在临床应用广泛,关于冠状动脉CTA。冠状动脉CTA的适应证错误的是
商业银行贷给同一借款人的贷款金额不得超过银行资本金额的( )。
基金托管人应当履行的职责包括()等。
在收容教养期间,对被收容教养的未成年人实行( )方针。
根据所给材料,回答下面问题
建设生态文明,必须保护生态环境。保护生态环境的根本之策是
Inthepastdecade,newscientificdevelopmentsincommunicationshavechangedthewaymanypeoplegatherinformationaboutpoli
最新回复
(
0
)