首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
将任意给定的序列1,2,…,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2,…,n)的一个排列p1,p2…pn为这棵树的后根遍历序列。 (1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树?如果能够,请简述理由(不要求形式化证
将任意给定的序列1,2,…,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2,…,n)的一个排列p1,p2…pn为这棵树的后根遍历序列。 (1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树?如果能够,请简述理由(不要求形式化证
admin
2013-12-31
60
问题
将任意给定的序列1,2,…,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2,…,n)的一个排列p
1
,p
2
…p
n
为这棵树的后根遍历序列。
(1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树?如果能够,请简述理由(不要求形式化证明)。如果不能,请给出一个简单反例。
(2)如果能得到树,所得到的树是否唯一?如果能够,请简述理由(不要求形式化证明)。如果不能,请给出一个简单反例。
选项
答案
(1)不一定能得到一棵树。 反例(给出任何一个正确的反例即可): 反例1:对于先根遍历序列{1,2,3,4},后根遍历序列{1,3,2,4}这种情况,就无法得到一棵树。 反例2:对于先根遍历序列{1,2,3,4},后根遍历序列(4,2,3,1}这种情况,也不能得到一棵树。 理由(题目并不要求说明理由,如果说清了理由而没有给出反例,也可以得分): 理由一:若一棵树的先根遍历序列为{1,2,3,4},则1必为树根,该树的后根遍历序列中“1"一定在最后,故根据最后数字不为“1”的后根序列与先根序列{1,2,3,4)就无法得到一棵树。 理由二:一棵树可以转换成一棵没有右子树的二叉树,反之亦然。所以,对于n个结点的树,可以等价地考虑相应的除去根结点(即1)以外的(n-1)个结点的二叉树问题。在这里2,3,…,n就是相应的二叉树的先序遍历序列p
1
,p
2
,…p
n-1
就是相应二叉树的中序遍历序列。对于n个结点的树,可以等价地考虑相应的n-1个结点的二叉树问题。该问题转换为:指定2,3,…,n这n-1个数为一棵二叉树先序遍历序列;同时p
1
,p
2
,…p
n-1
(其中p
1
,p
2
,…p
n-1
,为2,3,…,n这n-1个数值的一个排列)为这棵树的二叉树中序遍历序列。是否都可以得到一棵二叉树? 可以证明:对于一棵先序遍历序列为1,2,…,n的二叉树,在中序遍历时其被涉及的顺序也就是进入运行栈的顺序就是1,2,…,n,其中中序遍历顺序,则是一种可能的出栈顺序。有可能从初始输入序列1,2,…,n,利用一个栈得到输出序列p
1
,p
2
,…p
n
(p
1
,p
2
,…p
n
是1,2,…,n的一种排列)的充分必要条件是:不存在这样的i,j,k,满足i<j<k同时p
j
<p
k
<p
i
。 因此,先根序列1,2,…,n和后根序列p
1
,p
2
,…p
n-1
,1能够得到一棵树的充分必要条件是不存在下标i,j,k,满足i<j<k同时p
j
<p
k
<p
i
。 (2)如(1)所述,不一定能得到一棵树。但是如果所给出的序列合法,就能够得到一棵树,而且得到的树是唯一的。 所谓合法序列是指:先根遍历序列为1,2,…,n,后根遍历序列为p
1
,p
2
,…,p
n
,那么 只有当p
n
=1时,而且在p
1
,p
2
,…,p
n-1
中不存在这样的i,j,k,满足i<j<k同时p
j
<p
k
<p
i
。(不要求考生说明什么是合法的) 理由一:一棵树可以转换成一棵没有右子树的二叉树,反之亦然。所以,对于n个结点的树,可以等价地考虑相应的除去根结点(即1)以外的(n-1)个结点的二叉树问题。 在这里2,3,…,n就是相应二叉树的先序遍历序列p
1
,p
2
,…,p
n-1
就是相应二叉树的中序遍历序列——二叉树先序序列为DLR,二叉树中序序列为LDR,因此可以定位二叉树的根,然后定位出二叉树的左右子树并对左右子树做类似的递归处理,故所的二叉树是唯一的。因此相应的树也是唯一的。 理由二:对于合法的序列:先根序列为1,2,…,n,后根序列为p
1
,p
2
,…,p
n-1
,首先可以确定树根为1。其子树形成的森林的先根序列为2,…,n,后根序列为p
1
,p
2
,…,p
n-1
,这些森林被分成m(m≥0)个不相交的集合T
1
,T
2
,…,T
m
,而且这些集合的每一个又都是树,在先根序列中按照T
1
,T
2
,…,T
m
的结点顺序出现,在后根序列中也按照T
1
,T
2
,…,T
m
的结点顺序出现(但是对应的每个集T
1
中,结点出现的顺序不同)。因此可以找到每棵子树的结点集合,然后进行递归处理,最终只能得到一棵确定的树。
解析
转载请注明原文地址:https://kaotiyun.com/show/uSxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
1941年初成立的一个具有代表性的中间性政党是()。
1848年2月,马克思、恩格斯为国际无产阶级组织——共产主义者同盟起草的纲领()在伦敦发表。
1965年美国总统经济报告中宣布:“一个不受衰退威胁的繁荣时期,使我们能够防止经济活动下降的时期到来了,我们相信衰退是不可避免的……国家的措施基本上不能够在衰退开始之前予以防止。”下列能够证明报告观点错误的是()
第二次世界大战后,世界形势变化的最大特点是()。
下列对春秋时期各国称霸的顺序描述错误的选项是()
关于垄断组织的积极作用,不正确的说法是()。
布雷顿森林体系是如何建立的,包括哪些内容?
简述清代秘密立储制的操作并作出评价。
阅读以下史料,结合相关背景知识,分析古巴比伦社会的等级制度和奴隶制度。《汉谟拉比法典》(节录)第七条自由民从自由民之子或自由民之奴隶手中买得或为之保管银或金。或奴隶,或女奴,或牛,或羊,或驴,或不论任何物,而无证人及契约者,是为窃贼,
随机试题
()的目的是通过排除观察结果中带有矛盾性的因素来获取实验对象之间的真实因果关系。
患者,女,32岁。因慢性宫颈炎,白带增多,定期复查时医生为其行宫颈活体组织检查,病理诊断为宫颈息肉,其病理变化为
与药事有关的说法正确的是
税务机关是指发票的主管机关。()
适宜于管理层人员的培训与开发方法是()。
A、 B、 C、 D、 B本题是个典型的九宫格图形推理题目,考查点最有可能为角的数量,这样我们从横排来看,三个元素所包含的所有的角加起来的和为12,第二行也是此规律,那么第三行很明显也就可以推知也应该是12个
垄断条件下的的竞争同自由竞争相比,具有的新特点有
对长度为n的线性表排序,在最坏情况下,比较次数是nlog2n的排序方法是()。
Whethertheextensionofconsciousnessisa"goodthing"forhumanbeingsisaquestionthat______ofawidesolution.
Takingonaleadershiproleforthefirsttimeistough.Thereisalwayspressureonyoutodotherightthings,andtobeseen
最新回复
(
0
)