学步园

先来复习一下二叉树，最近在看刘汝佳写的算法艺术与信息学竞赛的学习指导

里面在讲二叉树的时候这样说道

分别用3个数组模拟指针，并对二叉树进行前序，中序和后序遍历

//对于一个节点i
//有Value[i],Right[i],Left[i]3个数组
//分别表示该节点的值，左儿子节点，右儿子节点
//那么三种遍历的DFS可以这样写：
void PreOrder(int root)
{
	if(root){
		Print(Value[i]);
		PreOrder(Left[i]);
		PreOrder(Right[i]);
	}
} 

void InOrder(int root)
{
	if(root){
		PreOrder(Left[i]);
		Print(Value[i]);
		PreOrder(Right[i]);
	}
} 

void PostOrder(int root)
{
	if(root){
		PreOrder(Left[i]);
		PreOrder(Right[i]);
		Print(Value[i]);
	}
} 

下面要实现一个已知前序和中序遍历，恢复一棵二叉树的操作

比如对于这样一棵二叉树，前序遍历依次为：ABDECF   中序遍历为：DBEAFC

/*
假定两个序列分别保存在数组Pre[i]与In[i]中
我们分别用Pl,Pr标记前序遍历的起止下标，用Il,Ir标记中序遍历的起止下标 
由前序遍历的性质可以知道Pre[Pl]即为二叉树的根
于是，我们在In[i]中找到根的位置，并标记为p
由中序遍历的性质可以知道，
在In[i]中，对于i<p的节点，都在左子树中，i>p的节点都在右子树中
我们将Pre[Pl](即In[p])放入树中，并递归的建左右子树（这里用到分治的思想） 

此时可以把Pre,In数组分别看成由三部分组成
对于Pre:根   +   左子树  +   右子树
        Pl          q              Pr
对于In:左子树  +  根  +   右子树
        Il        p            Ir
要实现递归操作，还必须知道前序遍历中，表示左子树的最后一个元素的坐标q
可以由中序遍历的坐标转换得到,q=p-Il+Pl

此时所有坐标都已经出现，源代码如下
*/
void BuildTree(int Pl,int Pr,int Il,int Ir,int Root)
{
	if(Pl>Pr){
		Root=0;
		return;
	}
	int p,q;
	p=Find(Pre[Pl]);
	q=Pl+p-Il;
	
	Root=++NodeCount;    //NodeCount为节点序号 
	BuildTree(Pl+1,q,Il,p-1,Left[Root]);
	BuildTree(q+1,Pr,p+1,Ir,Right[Root]);
}