对于二叉树，在此我不做过多讲解，如有不懂，请参照一下链接点击打开链接

1、在此二叉树的定义：

structBinaryTreeNode{BinaryTreeNode<T>*_Left;BinaryTreeNode<T>*_Right;T_data;public:BinaryTreeNode(constT&x):_Left(NULL),_Right(NULL),_data(x){}};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;public:BinaryTree():_root(NULL){}}


2、由前序遍历和中序遍历重建二叉树

思想：
1、二叉树前序遍历中，第一个元素总是根节点的值，
2、中序遍历，左子树的结点的值位于根节点值得左边，
3、右子树的节点的值位于根节点值得右边。
4、如果前序遍历为空或中序遍历为空或结点个数小于等于0，返回NULL；
5、创建根节点，前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点位置
6、分别得知左子树和右子树的前序和中序遍 历序列，重建左右子树。


递归形式实现：

Node*RebuildBinaryTree(T*PrevOrder,T*InOrder,intnum){if(PrevOrder==NULL||InOrder==NULL||num<=0){returnNULL;}Node*root=newNode(PrevOrder[0]);//前序遍历的第一个数据就是根节点数据//中序遍历，根节点左为左子树，右为右子树introotposition=-1;for(inti=0;i<num;i++){if(InOrder[i]==root->_data){rootposition=i;}}if(rootposition==-1)returnNULL;//重建左子树(根节点)递归intLeftNum=rootposition;int*PrevOrderLeft=PrevOrder+1;//前序第二个即为根节点的左子树int*InOrderLeft=InOrder;//中序第一个即为其左子树。root->_Left=RebuildBinaryTree(PrevOrderLeft,InOrderLeft,LeftNum);//重建右子树(根节点)递归intRightNum=num-LeftNum-1;int*PrevOrderRight=PrevOrder+1+LeftNum;int*InOrderRight=InOrder+LeftNum+1;root->_Right=RebuildBinaryTree(PrevOrderRight,InOrderRight,RightNum);returnroot;}