首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
82
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
宁夏回族自治区的设立时间是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
()时,为补充兵力,开拓财源,“料民于太原”(今山西西南部)。料民就是清查民数,以便于征兵,结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
在“冷战”形成的过程中,影响苏联领导人对美政策变化的关键性事件是()。
简述按照恩格斯的划分方法人类的起源与进化。
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
下列对第三次科技革命推动了国际经济格局调整的叙述,不正确的是()。
以下()协议完成了从网卡到IP地址的映射。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
随机试题
A.尿镜检红细胞满视野B.尿镜检白细胞满视野C.尿外观正常,镜检可见各种管型D.尿外观酱油色,隐血试验(+)E.尿外观深黄色,含大量胆红素阵发性睡眠性血红蛋白尿【】
一成年雌性动物出现断断续续发情,使整个发情期延长,配种不能受胎。最可能的诊断结论是()。
()是通过相互沟通、调整、联合等方法,使项目涉及的各方配合得当、协同一致,以便顺利实现项目目标。
下列关于企业核心竞争力分析的表述中,正确的有()。
背景资料:某工程包括三个结构形式与建造规模完全一样的单体建筑,施工过程中共五个施工过程组成,分别为:土方开挖、基础施工、地上结构、二次砌筑、装饰装修。根据施工工艺要求,地上结构施工完毕后,需等待两周后才能进行二次砌筑。施工过程中发生了如下事件:事件一
关于管理人或者债务人依照破产法规定解除双方均未履行完毕的合同,下列说法错误的是()。
我国法律禁止未成年人作为购房人购买房屋。()
关于社会化,下面说法正确的是()。
毛泽东基本形成关于中国工业化思想的著作是()
How’sTimnow?
最新回复
(
0
)