首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
121
问题
输入一整数数组{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://www.kaotiyun.com/show/1XRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述第二国际建立的社会历史条件。
在半殖民地半封建社会条件下,由于经济地位决定了在政治上带有两重性的阶级是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
阅读下列材料,并回答问题:当时帝国地跨欧亚非三洲。地中海成为它的内湖。境内农业、手工业和商业发展起来,海路畅通无阻,陆路纵横交错、四通八达,促进了贸易发展,也有利于信息传递和军队调防。帝国同北欧、印度、中国都有贸易往来,中国的丝绸也传到帝国。原来较落后的
把变量引进数学。使解析几何成为数学发展史上转折点的科学家是()。
晚清时期清帝年号的正确排序是
以下()协议完成了从网卡到IP地址的映射。
操作数地址存放在寄存器的寻址方式叫()。
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
随机试题
A.单纯扩散B.经载体易化扩散C.经通道易化扩散D.原发性主动转运E.继发性主动转运肌膜兴奋时终池释放Ca2+属于
有机磷迟发性神经炎主要表现为
外感热病极期,邪热深入营血的舌象是( )。
下列水溶液中pH最大的是()。
198×年×月初,某工程局某公司机械加工队,承接某电站部分塔吊安装工程;由武某某负责具体安装指挥。198×年×月×日上午,10号塔吊的前后臂和配重块以及主要部件已基本安装完毕。塔吊回转以上部分未与塔身连接,靠爬身套架支撑,塔吊处于顶升准备状态。为安装平台围
发行公债的最初目的是为了()。
要讨论中华诗歌的传承与发展,就必须回答什么是中华诗歌的精神,然后还要回答,这种精神有没有拓展和变化的问题。 我们从现有标本看到的,是从《诗经》到汉魏时期的古风、乐府这样一些带有先民原初思维特质的歌咏;看到的是唐宋以来的诗体自觉及形式
若被保险人的家庭成员或者其组成人员故意制造保险事故造成保险标的损失,那么保险人()代位请求赔偿的权利。
关于法治与民主的联系,下列说法正确的有()。
Travelingismoreimportantthanreadingbooksinordertounderstandthepeopleandtheworld.Doyouagreeordisagreewithth
最新回复
(
0
)