根据中序遍历和后序遍历重建二叉树

二叉树的重建

二叉树的重建方法：

一、根据前序加中序遍历重建二叉树

构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。

二、根据中序加后序遍历重建二叉树

构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。

三、前序加后序

前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。

下面是一棵二叉树：

前序遍历:1 2 4 3 5 7 6 
中序遍历:2 4 1 5 7 3 6
后序遍历:4 2 7 5 6 3 1

前序+中序重建二叉树

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	int data;
	struct node *lchild,*rchild;
}bitree;

void rebuild(int *prelist,int *inlist,int n,bitree **t)
{
	if(!prelist || !inlist || n<=0 )		//空树 
		return;
	int i;

	//找到根结点在中序遍历中的位置 
	for(i = 0; i < n; i++)
	{
		if(inlist[i] == prelist[0])			
			break;					 
	} 

	if(i>=n)
		return;

	//初始化根结点 
	*t = (bitree*)malloc(sizeof(bitree));
	if(!t)
		return;
	(*t)->lchild = (*t)->rchild = NULL;
	(*t)->data = prelist[0];

	//重建左子树
	rebuild(prelist+1,inlist,i,&(*t)->lchild); 
	//重建右子树 
	rebuild(prelist+i+1,inlist+i+1,n-i-1,&(*t)->rchild);
}

void postOrderTraverse(bitree *t)
{	//	后序遍历 
	if(t)
	{
		postOrderTraverse(t->lchild);
		postOrderTraverse(t->rchild);
		printf("%d ",t->data);
	}
}

int main()
{
	int pre[] = {1,2,4,3,5,7,6};
	int in[] = {2,4,1,5,7,3,6};

	bitree *t = NULL;
	rebuild(pre,in,7,&t); 
	postOrderTraverse(t);

	return 0;
} 

中序+后序重建二叉树：

void rebuild(int *inlist,int *postlist,int n,bitree **t)
{
	if(!inlist || !postlist || n<=0 )		//空树 
		return;
	int i;

	//找到根结点在中序遍历中的位置 
	for(i = 0; i < n; i++)
	{
		if(inlist[i] == postlist[n-1])			
			break;					 
	} 

	if(i>=n)
		return;

	//初始化根结点 
	*t = (bitree*)malloc(sizeof(bitree));
	if(!t)
		return;
	(*t)->lchild = (*t)->rchild = NULL;
	(*t)->data = postlist[n-1];


	//重建左子树	
	rebuild(inlist,postlist,i,&(*t)->lchild); 				
	//重建右子树 
	rebuild(inlist+i+1,postlist+i,n-i-1,&(*t)->rchild);			//post+i 
}