前序序列和后续序列确定⼆叉树
⼆叉树：已知前序与后序建树
那么我们换⼀种思考⽅式，我们先来看看先序与后序序列的排布规律。以下⾯这棵树来举例：
其先序序列为： 1 2 3 4 6 7 5
后序序列为：2 6 7 4 5 3 1
⾸先我们要知道：
先序序列遍历顺序是：根结点-左⼦树-右⼦树
先序中序后序遍历二叉树
后序序列遍历顺序是：左⼦树-右⼦树-根结点
很明显，我们可以看出结点在先、后序列中的排布有以下这些特征：
【1】、在先序序列中，根结点在⼦树中的结点前⾯，在后序序列中，根结点在⼦树中的结点后⾯。
【2】、以任⼀节点为根结点时，其⼦树在先序后序序列中排布都是先左⼦树后右⼦树，⽽根结点排在最后。
那么，反过来思考，已知这个先序与后序序列所确定的树是唯⼀的吗？进⼀步推⼴：怎么通过先序与后序序列判断是否存在唯⼀的树呢？
现在，我们来⼀步步分析已知先序与后序的建树过程：
①、根据特征【1】可知：根结点为先序序列第⼀个节点以及后序序列最后⼀个结点，因此根结点为1。
②、先序序列中第⼆个结点为2，其在后序序列中的位置是第⼀个，那么根据特征【2】我们可以知道结点2是没有⼦树的，⽽且结点2要么在根结点的左⼦树，要么在右⼦树。假设结点2在右⼦树，那么由特征【2】可知根结点1没有左⼦树，⽽且先序序列中结点2后⾯的结点全部为结点2的⼦树上的结点。再看后序序列，由特征【2】可知，结点2后⾯的结点不可能是其⼦树上的结点。因此，假设显然与已知⽭盾。这样，我们⼜知道结点2是结点1的左孩⼦，且结点2没有⼦结点。
③、先序序列第三个位置上的结点为3，该结点在后序序列中排倒数第⼆个。由②可知，结点3必然是根结点1的右孩⼦。 
④、先序序列第四个位置上的结点为4，该结点在后序序列中排第四个。因为结点4在先序序列中排在结点3后⾯，⼜因为结点3是根结点1的右孩⼦，所以结点4只可能在结点3的⼦树上。结点3的⼦树可能出现的情况是：只有左⼦树，只有右⼦树，左右⼦树都有。因为在后序序列中，结点4左边是结点6、7，右
边是结点5。所以结点5并不在结点4的⼦树上，所以结点3既存在左⼦树⼜存在右⼦树。这样的话，出现在结点3后⾯的第⼀个结点必然为结点3的左⼦树，所以结点4是结点3的左孩⼦，且由特征【2】可知，结点6、7在以结点4为根结点的⼦树，上，结点5是结点3的右孩⼦。 
⑤再看结点6，其在先序序列中排在第五位，在后序序列中排在第⼆位。同理，结点4的⼦树可能出现的情况是：只有左⼦树，只有右⼦树，左右⼦树都有。假设，接4只有左⼦树，那么结点6必然为结点4的左孩⼦，结点7必然为结点6的孩⼦，⽽根据特征【2】，因为结点7在后序序列中排在结点6后⾯，因此结论与假设⽭盾。同样可以排除只有右⼦树的情况。那么我们可以得到：结点4既有左⼦树⼜有右⼦树，由特征【2】可知结点6为结点4的左孩⼦，结点7为结点4的右孩⼦。
⾄此，我们已经分析了⼀遍如何通过⼆叉树的先、后序序列建⽴⼀个⼆叉树，但是由这个例⼦中的先、后序序列确定的树是唯⼀的。现在我们再从分析过程中提炼⼀些排列特征出来：
【3】在后序序列中，若⼀个结点的左侧没有在先序序列中排在该结点后⾯的结点（如结点2，在先序序列中排在其后⾯的结点有3 4 6 7 5 但在后序序列中结点2前⾯没有这些结点），那么这个结点必然没有孩⼦。 
再来看看这样⼀个例⼦：
先序序列：1 2 3 4
后序序列：2 4 3 1
我们再来建⽴⼀棵满⾜上述条件的树：
通过上⼀个例⼦，我们可以很快得到结点1为根结点，结点2为结点1的左孩⼦，结点3为结点1的右孩⼦，但是我们发现：结点4既可以是结点3的左孩⼦，⼜可以是右孩⼦。我们可以看到，之所以结点4的位置⽆法确定，是因为结点3只有⼀个⼦节点，⽽这个⼦节点既可以是左孩⼦，⼜可以是右孩⼦。
⾄此，我们可以得到确定⼀个结点位置是否唯⼀的⽅法：检测其⽗节点是否只有⼀个⼦节点。
因此可以得到特征：
【4】在后序序列中，若⼀个结点的左边只有⼀个在该结点的先序序列前⾯未出现过的结点（如结点3左边只有4没有在先序序列中的结点3前⾯出现过），那么说明树不唯⼀，树的个数与出现这种情况相关(2^n)。
利⽤这个⽅法，我们来计算⼀下下⾯这些例⼦可以确定多少种树：
先序序列：1 2 3 4 5 6
后序序列：3 2 5 6 4 1
先序序列：1 2 4 5 6 3
后序序列：4 2 3 6 5 1
先序序列：1 3 4 5 6 2 7
后序序列：5 4 3 2 7 6 1
答案分别为：2，8，1
树形可以为： 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
int n;
int pre[maxn],post[maxn],pos[maxn];
bool isunique = true;// 判断是否唯⼀
struct node{
int data;
node *lchild,*rchild;
};
void inorder(node *&root,int prel,int prer,int postl,int postr){
if(prel == prer){
root = new node;
root->data = pre[prel];
root->lchild = root->rchild = NULL;
return;
}else if(prel>prer || postl>postr){
return;
}
if(pre[prel] == post[postr]){
root = new node;
root->data = pre[prel];
root->lchild = root->rchild = NULL;
int numchild = pos[pre[prel]] - postl; // 统计以该结点为根结点时的左⼦树结点个数
if(numchild == 1){
isunique = false;
}
int postloc = pos[pre[prel+1]];
int numleft = postloc-postl;
inorder(root->lchild,prel+1,prel+numleft+1,postl,postl+numleft);
inorder(root->rchild,prel+numleft+2,prer,postl+numleft+1,postr-1);
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&pre[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&post[i]);
pos[post[i]] = i;
}
node *root = NULL;
inorder(root,0,n-1,0,n-1);
return0;
}
简要说⼀下对这个算法的思路，
1.⾸先将前序和后序遍历序列存到⼀个数组中，同时将后序序列中每个结点前⾯结点的个数也保存在⼀个pos数组中。
2.取前序的第⼀个结点和后序的最后⼀个结点⽐较，若相等，则这个结点是树或者⼦树的根节点。
3.取前序区间中的第⼀个结点A，求出后序序列中A左边结点的个数childnum，由后序遍历的特征可以知道这numchild个结点都是A的⼦孙结点。
4.取前序区间中的第⼀个结点的下⼀个结点B，到后序序列中这个结点B的位置，并通过pre数组求出这个结点左边的结点个数numleft，由后序遍历的特征可以知道这numleft个结点都是B的⼦孙结点。
5.从新划分递归区间，即前序序列的开始、结尾位置和后续遍历的开始结尾位置。
  左⼦树的区间划分：
    前序开始位置等于本层递归中前序序列的初始位置prel+1，结束位置等于本层递归中前序序列的初始位置prel+1+numleft;
    后序开始位置等于本层递归中后序序列的初始位置postl，结束位置等于本层递归中后序序列的初始位置postl+numlleft.
  右⼦树的区间划分：
    前序开始位置等于本层递归中前序序列的初始位置prel+2+numleft，结束位置等于本层递归中前序序列的初始位置prer;
    后序开始位置等于本层递归中后序序列的初始位置postl+numleft+1，结束位置等于本层递归中后序序列的初始位置postr-1.
6.开始新的递归，递归出⼝是prel>prer或者postl>postr.
说明⼀下：
1、调⽤inorder()函数得到root便获取到了建成的树，其中位置不确定的结点都被认为是左结点。
2、若想统计不同的树形个数，可以对以下语句进⾏修改：
将:
bool isunique = true;
...
if(numchild == 1){
isunique = false;
}
改为:
int isunique = 0;
...
if(numchild == 1){
isunique++;
}
此时树形个数为2^isunique个，想⼀想为什么是2为底数？
PAT上有类似的题⽬:
PAT Advancedlevel 1119 Pre- and Post-order Traversals

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。