分别根据前中序遍历和后中序遍历来推二叉树的结构

原文地址为：分别根据前中序遍历和后中序遍历来推二叉树的结构

1、理论分析：

数据结构的基础知识中重要的一点就是能否根据两种不同遍历序列的组合（有三种：先序+中序，先序+后序，中序+后序），唯一的确定一棵二叉树。然后就是根据二叉树的不同遍历序列（先序、中序、后序），重构二叉树。显然，这三种组合并不是都能唯一确定二叉树的，其中先序+后序就不能唯一确定一棵二叉树。这里我就不证明了。举个反例：

反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。

2、构造思路：

（1）根据先序遍历序列和中序遍历序列构建二叉树：
先序：ABCDEFG

中序：CBEDFAG

step1、先序遍历的第一个结点总是根结点。如上图中的二叉树，根结点为A，也是先序遍历的第一个值。先序遍历时父亲结点总是在孩子结点之前遍历。

step2、可以观察到在中序遍历中，A是第5个值（从0开始算起）。由于中序遍历顺序为：左子树，根结点，右子树。所以A左边的{CBEDF} 这四个结点属于左子树，而根结点A右边的{G}属于右子树。

step3、可以从上面的结论很轻松的得到递归式。在构建了根结点A后，我们可以根据中序遍历{CBEDF} 和{G}分别构建它的左子树和右子树。我们同时需要相应的先序遍历结果用于发现规律。我们可以由先序遍历知道左右子树的先序遍历分别是{CBEDF}和{G}。左右子树也分别为二叉树，由此可以递归来解决问题。

补充进我之前写的二叉树类中（class BinTree）

int Creat_VLR_LVR(T VLR[],T LVR[],int len)
	{
		return Creat_VLR_LVR(root,VLR,VLR+len-1,LVR,LVR+len-1);
	}

//VLR：根左右---------------前序遍历	//LVR：左根右---------------中序遍历	int Creat_VLR_LVR(BinTreeNode<T> *&p,T *VLRh,T *VLRt,T *LVRh,T *LVRt)//////////////////////////////////////////////////////////////////////	{		T *valuepre = VLRh;//先取出前序遍历的第一个值来作为根节点		T *valuein = LVRh;   //去中序数组的指针		p = new BinTreeNode<T>((*valuepre));		if(*VLRh == *VLRt||*LVRh == *LVRt)		{			return OK;		}		if(*valuepre == '\0'&&*valuein == '\0')		{			return OK;		}		while((*valuein) != '\0'&& (*valuein) != *valuepre)			++valuein;		int leftlen = valuein - LVRh;		T *leftVLR = VLRh + leftlen;		if(leftlen > 0)		{			Creat_VLR_LVR(p->left,VLRh+1,VLRt,LVRh,valuein-1);		}		if(leftlen < VLRt-VLRh)		{			Creat_VLR_LVR(p->right,leftVLR+1,VLRt,valuein+1,LVRt);		}		return OK;	}

（2）根后序遍历序列和中序遍历序列构建二叉树：
后序：CEFDBGA

中序：CBEDFAG

step1、后序遍历的最后一个结点总是“根结点”。如上图中的二叉树，根结点为A，也是后序遍历的最后一个值。

step2、在中序遍历中找到“根节点”，但是这里要先创建右子树，因为后序遍历后面的是右子树的根节点，（这里唯一跟前序遍历不一样的是后序遍历是从后往前一个一个退的）。从中序遍历中我们可以看到{G}是A的右子树，所以先创建。

step3、后序遍历再往前退，到B，那么B是A的左子树......

根据以上的结论，通过递归好实现的。

	int Creat_LRV_LVR(T LRV[],T LVR[],int len)
	{
		return Creat_LRV_LVR(root,LRV,LRV+len-1,LVR,LVR+len-1);
	}

	//LRV：左右根---------------后序遍历	//LVR：左根右---------------中序遍历	int Creat_LRV_LVR(BinTreeNode<T> *&p,T *LRVh,T *LRVt,T *LVRh,T *LVRt)	{		T *valuepost = LRVt;		T *valuein = LVRh;		p = new BinTreeNode<T>((*valuepost));		if(*LRVh == *LRVt||*LVRh == *LVRt)			return OK;		if(*valuein == '\0')			return OK;		while((*valuein) != '\0'&& (*valuein) != *valuepost)			++valuein;		int rightlen = LVRt-valuein; //中序遍历右子树的长度		T *rightLRV = LRVt - rightlen;//后序遍历		if(rightlen > 0)		{			Creat_LRV_LVR(p->right,LRVh,LRVt-1,valuein+1,LVRt);//调试的时候要注意看好这里的参数		}		if(rightlen < LRVt-LRVh)		{			Creat_LRV_LVR(p->left,LRVh,LRVt-rightlen-1,LVRh,valuein-1);//调试的时候要注意看好这里的参数		}		return OK;	}

转载请注明本文地址：分别根据前中序遍历和后中序遍历来推二叉树的结构