任意给定1,2…….,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2…….,n)的一个排列p1,p2…….pn为这棵树的后根遍历序列。 (1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树?如果能够,请简述理由(不要求形式化证明)

admin2013-07-12  42

问题 任意给定1,2…….,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2…….,n)的一个排列p1,p2…….pn为这棵树的后根遍历序列。
(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就是相应的二叉树的先序遍历序列,p1,p2,……pn-1就是相应二叉树的中序遍历序列。对于n个结点的树,可以等价地考虑相应的n-1个结点的二叉树问题。该问题转换为: 指定2,3,……,n这n-1个数为一棵二叉树先序遍历序列;同时p1,p2,……pn-1(其中p1,p2,……pn-1为2,3,……,n这n-1个数值的一个排列)为这棵树的二叉树中序遍历序列。是否都可以得到一棵二叉树? 可以证明:对于一棵先序遍历序列为1,2,……,n的二叉树,在中序遍历时其被涉及到的顺序也就是进入运行栈的顺序就是1,2,……,n,其中中序遍历顺序,则是一种可能的出栈顺序。有可能从初始输入序列1,2,……,n,利用一个栈得到输出序列p1,p2,……pn(p1,p2,……pn是1,2,……,n的一种排列)的充分必要条件是:不存在这样的i,j,k,满足i1,p2,……pn-1,1能够得到一棵树的充分必要条件是不存在下标i,j,k,满足i1,p2,……pn,那么只有当pn=1时,而且在p1,p2,……pn-1中不存在这样的i,j,k,满足iki。(不要求考生说明什么是合法的) 理由一:一棵树可以转换成一棵没有右子树的二叉树,反之亦然。所以,对于n个结点的树,可以等价地考虑相应的除去根结点(即1)以外的(n-1)个结点的二叉树问题。 在这里2,3,……,n就是相应二叉树的先序遍历序列,p1,p2,……pn-1就是相应二叉树的中序遍历序列——二叉树先序序列为DLR,二叉树中序序列为LDR,因此可以定位二叉树的根,然后定位出二叉树的左右子树并对左右子树做类似的递归处理,故所的二叉树是唯一的。因此相应的树也是唯一的。 理由二:对于合法的序列:先根序列为1,2,……,n,后根序列为p1,p2,……pn-1,1,首先可以确定树根为1。其子树形成的森林的先根序列为2,??…?,n,后根序列为p1,p2,……pn-1,这些森林被分成m(m≥0)个不相交的集合T1,T2,……Tm,而且这些集合的每一个又都是树,在先根序列中按照T1,T2,……Tm的结点顺序出现,在后根序列中也按照T1,T2,……Tm的结点顺序出现(但是对应的每个集Ti中,结点出现的顺序不同)。因此可以找到每棵子树的结点集合,然后进行递归处理,最终只能得到一棵确定的树。

解析 本题主要考查树的遍历,以及树的遍历与所对应的二叉树的遍历的关系。
转载请注明原文地址:https://kaotiyun.com/show/quxi777K
0

最新回复(0)