根据先序序列和中序序列构造二叉树

阅读本文之前希望读者可以先掌握如何根据先序序列和中序序列手动画出二叉树。
所用二叉树数据结构如下：

typedef struct TreeNode{
	char data;
	TreeNode *lchild,*rchild;
} TreeNode,*Tree;

该方法声明如下

Tree createTree(char *pre,int l1,int r1,char *in,int l2,int r2);

接下来先介绍每一个参数用途

• char *pre ：数组给出的先序序列
• char *in ：数组给出的中序序列
• int l1：左子树的先序序列起始位置
• int l2：右子树的先序序列起始位置
• int r1：左子树先序序列的结束位置
• int r2：右子树的先序序列的结束位置

接下来画图解释这六个参数

简而言之，pre，in为两个序列，l1,r1为pre数组的边界符，l2,r2为in数组的边界符
以下给出我对于这个算法的大体实现思路
我们画图具体分析以下，首先，我拿到之后，肯定知道先序序列第一个节点就是根节点，我们可以在中序队列中遍历找到根节点的位置，如下图所示

黄色为根节点，我用i去指向中序队列中的根节点，此时i左边的元素均为左子树上的元素，i右边的元素均为右子树上的元素。
我们可以使用i-l2来计算出左子树的元素个数，使用r2-i来计算出右子树的元素个数，分别记作Llen和Rlen
此时如果Llen小于等于0，说明左子树没有元素，我可以直接让左子树为空，Rlen小于等于0，说明右子树没有元素，我可以直接让右子树元素为空。
左子树和右子树为空的情况我们讨论完了，接下来考虑左右子树不为空的情况，如果左子树不为空，那么左子树的中序序列就是图中蓝色的部分，下标范围为[l2,i-1]，而左子树的先序序列可以看到图中先序序列的蓝色部分，也就是[l1+1,l1+Llen]，我们将其作为参数递归调用自身，就可以递归创建左子树。
右子树则是图中绿色的部分，右子树的中序序列为[i+1,r2]，先序序列为[l1+Llen+1,r1]，我们将其作为参数调用自身就可以实现递归创建右子树。
接下来给出具体实现：

#include <iostream>
using namespace std;
typedef struct TreeNode{
	char data;
	TreeNode *lchild,*rchild;
} TreeNode,*Tree;
void initNode(TreeNode *t){//初始化节点
	t -> lchild = NULL;
	t -> rchild = NULL;
}
TreeNode *createNode(char d){//创建一个节点
	TreeNode *p = new TreeNode;
	initNode(p);
	p -> data = d;
	return p;
}
Tree createTree(char *pre,int l1,int r1,char *in,int l2,int r2){
	//创建根节点
	char rootData = pre[l1];//先序遍历第一个节点必为根节点，取出根节点数据
	TreeNode *root = createNode(rootData);//创建根节点
	//找到根节点在中序遍历中的位置
	int i = l2;//记录根节点在中序遍历中的位置
	while(in[i] != rootData){
		i++;
	}
    //此时i指向中序序列中的根节点
	int Llen = i-l2;//计算左子树元素个数
	int Rlen = r2-i;//计算右子树元素个数
	//先序序列：左子树范围为[l1+1,l1+Llen]  右子树范围为[l1+Llen+1,r1]
	if(Llen <= 0){//如果左子树元素个数小于等于0
		root -> lchild = NULL;//左子树为空
	}else{
		//递归创建左子树
		root -> lchild = createTree(pre,l1+1,l1+Llen,in,l2,i-1);
	}
	if(Rlen <= 0){//如果右子树元素个数小于等于0
		root -> rchild = NULL;//右子树为空
	}else{
		//递归创建右子树
		root -> rchild = createTree(pre,l1+Llen+1,r1,in,i+1,r2);
	}
	return root;
}
//中序遍历
void inorder(Tree t){
	if(t){//如果t不为空
		inorder(t -> lchild);//左孩子
		cout << t -> data;
		inorder(t -> rchild);//右孩子
	}
}
//先序遍历
void preorder(Tree t){
	if(t){//如果t不为空
		cout << t -> data;
		preorder(t -> lchild);//左孩子
		preorder(t -> rchild);//右孩子
	}
}
int main(void){
	char pre[] = "DAEFBCHGI";
	char in[] = "EAFDHCBGI";
	Tree t = createTree(pre,0,8,in,0,8);
	inorder(t);
	cout << endl;
	preorder(t);
	return 0;
}