k
i。 因此,先根序列1,2,……,n和后根序列p1,p2,……pn-1,1能够得到一棵树的充分必要条件是不存在下标i,j,k,满足ijki。 (2)如(1)所述,不一定能得到一棵树。但是如果所给出的序列合法,就能够得到一棵树,而且得到的树是唯一的。 所谓合法序列是指:先根遍历序列为1,2,……,n,后根遍历序列为p1,p2,……pn,那么只有当pn=1时,而且在p1,p2,……pn-1中不存在这样的i,j,k,满足ijki。(不要求考生说明什么是合法的)理由一:一棵树可以转换成一棵没有右子树的二叉树,反之亦然。所以,对于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中,结点出现的顺序不同)。因此可以找到每棵子树的结点集合,然后进行递归处理,最终只能得到一棵确定的树。
i。 (2)如(1)所述,不一定能得到一棵树。但是如果所给出的序列合法,就能够得到一棵树,而且得到的树是唯一的。 所谓合法序列是指:先根遍历序列为1,2,……,n,后根遍历序列为p1,p2,……pn,那么只有当pn=1时,而且在p1,p2,……pn-1中不存在这样的i,j,k,满足ijki。(不要求考生说明什么是合法的)理由一:一棵树可以转换成一棵没有右子树的二叉树,反之亦然。所以,对于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中,结点出现的顺序不同)。因此可以找到每棵子树的结点集合,然后进行递归处理,最终只能得到一棵确定的树。
i。(不要求考生说明什么是合法的)理由一:一棵树可以转换成一棵没有右子树的二叉树,反之亦然。所以,对于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中,结点出现的顺序不同)。因此可以找到每棵子树的结点集合,然后进行递归处理,最终只能得到一棵确定的树。