对于树的两序求型的分析

在树的先序、中序、后序和层次中，中序可以和任意组合完成重建树，其余二二并不能保证重建树的唯一性。

一、已知树的先序和中序

先序为PRe1~pren，中序为in1~inn。先序列中的第一个数为树的根，再由中序的特点可以在找到根结点的情况下分成左树右树，我们对中序查找，假设找到根结点的位置为k,则左树是k-1个，那么我们可以将先序中的2-k和中序中的1-k-1再次按照以上规则找到根结点的左孩子，按照先序k+1~n和中序k+1~n按照规则找到根结点的右孩子。

这样什么时候是个头呢，当先序长度为零时，即preL>preR时，就可以return了。下面用简单的算法实现一下。

const int Max = 40;int n;struct node{	int data;	node *lchild,*rchild;};int pre[Max]={0},in[Max]={0};node* BuildTree(int preL,int preR,int inL,int inR){	if(preL>preR)	{		return NULL;	}	node* root = new node;	root->data=pre[preL];	int k;	for(k=inL;k<=inR;k++)	{		if(in[k]==pre[preL])		{			break;		}	}	int numL=k-inL;	root->lchild=BuildTree(preL+1,preL+numL,inL,inL+numL-1);	root->rchild=BuildTree(preL+numL+1,preR,inL+numL+1,inR);	return root;}二、已知中序和后序，构造树，其实思路和第一个的思路差不多
const int Max = 40;int n;struct node{	int data;	node *lchild,*rchild;};int post[Max]={0},in[Max]={0};node* BuildTree(int postL,int postR,int inL,int inR){	if(postL>postR)	{		return NULL;	}	node* root = new node;	root->data=post[postR];	int k;	for(k=inL;k<=inR;k++)	{		if(in[k]==post[postR])		{			break;		}	}	int numL=k-inL;	root->lchild=BuildTree(postL,postL+numL-1,inL,inL+numL-1);	root->rchild=BuildTree(postL+numL,postR-1,inL+numL+1,inR);	return root;}三、已知前序和后序，求中序
开头讲过，如果你不知道中序，你很难得到树的唯一解，但是可以判断是否唯一，树是否唯一的关键点在与，当你在后序中找到一个点，如果他在前序的现有序列中排在第二个（第一个肯定是根结点），那么它一定不是唯一的，因为你不知道它是根结点的左孩子还是右孩子，因此我们可以通过这个，来确定其是否唯一。然后接下来的问题就是在于递归了，一开始，我们先找到后序中的最后一个点，然后在先序中找到他的位置，他就是我们这次递归的根结点，然后再找后序的倒数第二个点，如果它符合唯一性，那么我们在先序中找到这个点，就可以得到左边有几个结点和右边结点的数量，假设我们是按0~n-1排的，得到的在先序位置为k,那么，左边的数量就是k-preL-1,对于先序，遍历它左孩子的边就是 preL+1,k-1  后序则是postL,postL+k-pre-2.对于右孩子，先序是 k,preL 后序是 postL+k-preL-1,postR-1 .
然后我们可以用一个容器，来存储点，只要保证 先遍左，再存自己，再遍右，就一定会得到中序。
const int Max = 40;int n;struct node{	int data,height;	node *lchild,*rchild;};vector<int> S;int post[Max]={0},pre[Max]={0};int findLocate(int x,int l,int r){	for(int i=l;i<=r;i++)	{		if(pre[i]==x)		{			return i;		}	}	return -1;}int u=1;void SetIn(int preL,int preR,int postL,int postR){	if(preL==preR) //根结点	{		S.push_back(pre[preL]);		return ;	}	if(pre[preL]==post[postR])	{		int k=findLocate(post[postR-1],preL+1,preR);		if(k-preL>1)		{			SetIn(preL+1,k-1,postL,postL+k-2-preL);			S.push_back(post[postR]);			SetIn(k,preR,postL+k-1-preL,postR-1);		}		else 		{			u = 0;			S.push_back(post[postR]);			SetIn(k,preR,postL+k-1-preL,postR-1);		}	}}结束