夕拾算法进阶篇：23)中序和前序|后序|层次重建二叉树

假设已知先序序列为PRe₁,pre₂..pre_n，中序序列为in₁,in₂..in_n，如下图所示，由先序序列的性质可知u，先序序列的第一个元素pre₁是当前二叉树的根结点。再有中序序列的性质可知，当前二叉树的根结点将中序序列划分为左子树和右子树。因此只要在中序序列中找到某个结点in_k，使得in_k==pre₁，这样就找到了根结点。易只左子树的结点个数numLeft=k-1，从而左子树先序序列的区间就是[2,k]，左子树的中序序列区间就是[1,k-1]；右子树的先序序列区间[k+1,n]，右子树的中序序列区间[k+1,n]。

就一般性来说，如果递归过程中当前先序序列的区间为[preL,preR]，中序序列的区间为[inL,inR]。那么左子树的结点个数numLeft=k-inL。这样左子树的先序序列的区间就是[preL+1,preL+numLeft]，左子树的中序序列区间是[inL,k-1]；右子树的先序序列区间是[preL+numLeft+1,preR]，右子树的中序序列区间是[k+1,inR]。具体区间 可以参看下图。

每一次递归都可以获得对应子树的根结点，那么递归的边界在哪呢？很明显只要先序序列的长度小于等于0时，二叉树就不存在了。

比如给出的二叉树如下图所示：

先序遍历：4 1 3 2 6 5 7

中序遍历：1 2 3 4 5 6 7

后序遍历：2 3 1 5 7 6 4

层次遍历：4 1 6 3 5 7 2

先序&中序

定义结构如下：

const int M=100; //最大的节点数 int pre[M],in[M],post[M],lay[M],;//前、中、后、层次遍历的序列 下标从1开始 int map[M];//保存层次遍历序列的元素下标(元素过大,可以使用STL-map替换) struct Node{	int data;	Node *lchild ,*rchild;}; 
根据上面的分析，下面给出由先序和中序构建一棵二叉树的代码：
Node* create(int preL,int preR,int inL,int inR){  //初始create(1,n,1,n)	if(preL>preR){//递归边界 		return NULL;	}	Node* root=new Node();	root->data=pre[preL];//保存当前root的值 	int k; //root在中序的下标 	for(k=inL;k<=inR;k++){		if(in[k]==pre[preL]){//在中序查找root 			break;		} 	}	int numLeft=k-inL;//获得左子树结点数目	//递归构建左子树 	root->lchild=create(preL+1,preL+numLeft,inL,k-1); 	//递归构建右子树 	root->rchild=create(preL+numLeft+1,preR,k+1,inR); 	return root; }
后序&中序
由后序和中序构建二叉树。由后序遍历的性质可知，最后一个元素为根结点，而中序序列的区间没有改变，只需要修改上面代码的先序部分即可，修改后的代码如下：
Node* createByPostInOrder(int postL,int postR,int inL,int inR){	if(postL>postR){//递归边界 		return NULL;	}	Node* root=new Node();	root->data=post[postR];//保存当前root的值 	int k; //root在中序的下标 	for(k=inL;k<=inR;k++){		if(in[k]==post[postR]){//在中序查找root 			break;		} 	}	int numLeft=k-inL;//获得左子树结点数目	//递归构建左子树 修改了后序的区间部分	root->lchild=createByPostInOrder(postL,postL+numLeft-1,inL,k-1); 	//递归构建右子树 	root->rchild=createByPostInOrder(postL+numLeft,postR-1,k+1,inR); 	return root; }
层次&中序
由层次遍历的性质可知，在递归的过程中无法根据中序的根节点划分出层次的左右子树，但是层次遍历保证了序列中最靠前的元素一定是当前的根结点。因此可以使用一个map保存层次遍历元素的下标，若元素较小，可以直接使用数组保存。
for(int i=1;i<=n;i++){	cin>>lay[i];	map[lay[i]]=i; //保存map }每次根据当前的根结点划分中序序列后，在子序列中找到在层次遍历序列中最靠前的元素即为root，实现代码如下：
Node* create(int inL,int inR){	if(inL>inR){//递归边界 		return NULL;	}	Node* root=new Node();	int k=inL; //root在中序的下标 	for(int i=inL+1;i<=inR;i++){		if(map[k]>map[i]){//在当前中序序列查找其在层次遍历中最靠前的元素 			k=i;     //最靠前的即是root 		} 	}	root->data=in[k];	int numLeft=k-inL;//获得左子树结点数目	//递归构建左子树 	root->lchild=create(inL,k-1); 	//递归构建右子树 	root->rchild=create(k+1,inR); 	return root; }