由遍历序列恢复二叉树

各种计算机考试中，几乎都有这样的问题，给定二叉树先序、中序、后序、层次遍历的其中两种遍历序列，要求我们来恢复这棵二叉树。以先序、中序序列为例，由先序遍历的特点可知，先序序列的第一个元素R一定是二叉树的根结点，在中序序列中找到该结点，则此结点的左侧m个结点就是二叉树的左子树，右侧n个结点便是二叉树的右子树。先序序列中根结点后的m个结点为左子树，剩下n个结点为右子树。分别针对左右子树递归地寻找其根结点及其左右子树，便可恢复原二叉树。对于从中序、后序等其他遍历序列恢复二叉树的方法，大致雷同。写了段代码，实现从先序、中序遍历序列恢复二叉树：

/*
 * pre存放先序序列，
 * in存放中序序列，
 * n为结点个数，
 * 返回二叉树根指针
 */
BTree CreateBT(Type * pre, Type * in, int n)
{
	if(n <= 0)
		return NULL;
	BTree bt = new BTNode;
	Type * p;
	int k;
	bt->data = *pre;
	for(p = in; p < in + n; ++p)
		if(*pre == *p)
			break;
	k = p - in;
	bt->lchild = CreateBT(pre+1, in, k);
	bt->rchild = CreateBT(pre+k+1, p+1, n-k-1);
        return bt;	
}