问题 问答题

将任意给定的序列1,2,…,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2,…,n)的一个排列p1,p2,…pn为这棵树的后根遍历序列。

根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树如果能够,请简述理由(不要求形式化证明)。如果不能,请给出一个简单反例。

答案

参考答案:不一定能得到一棵树。
反例(给出任何一个正确的反例即可):
反例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,。

单项选择题
单项选择题