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

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

admin2013-12-31  46
问题 将任意给定的序列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，满足i＜j＜k同时pj＜pk＜pi。 因此，先根序列1，2，…，n和后根序列p1，p2，…pn-1，1能够得到一棵树的充分必要条件是不存在下标i，j，k，满足i＜j＜k同时pj＜pk＜pi。 (2)如(1)所述，不一定能得到一棵树。但是如果所给出的序列合法，就能够得到一棵树，而且得到的树是唯一的。 所谓合法序列是指：先根遍历序列为1，2，…，n，后根遍历序列为p1，p2，…，pn，那么 只有当pn=1时，而且在p1，p2，…，pn-1中不存在这样的i，j，k，满足i＜j＜k同时pj＜pk＜pi。(不要求考生说明什么是合法的) 理由一：一棵树可以转换成一棵没有右子树的二叉树，反之亦然。所以，对于n个结点的树，可以等价地考虑相应的除去根结点(即1)以外的(n-1)个结点的二叉树问题。 在这里2，3，…，n就是相应二叉树的先序遍历序列p1，p2，…，pn-1就是相应二叉树的中序遍历序列——二叉树先序序列为DLR，二叉树中序序列为LDR，因此可以定位二叉树的根，然后定位出二叉树的左右子树并对左右子树做类似的递归处理，故所的二叉树是唯一的。因此相应的树也是唯一的。 理由二：对于合法的序列：先根序列为1，2，…，n，后根序列为p1，p2，…，pn-1，首先可以确定树根为1。其子树形成的森林的先根序列为2，…，n，后根序列为p1，p2，…，pn-1，这些森林被分成m(m≥0)个不相交的集合T1，T2，…，Tm，而且这些集合的每一个又都是树，在先根序列中按照T1，T2，…，Tm的结点顺序出现，在后根序列中也按照T1，T2，…，Tm的结点顺序出现(但是对应的每个集T1中，结点出现的顺序不同)。因此可以找到每棵子树的结点集合，然后进行递归处理，最终只能得到一棵确定的树。
解析
转载请注明原文地址:https://kaotiyun.com/show/uSxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)