//设 T 是一棵具有 n 个节点的二叉树，若给定二叉树 T 的先序序列和中序序列，并假设 T 的先序序列和中序序列分别放在数组 PreOrder[1..n]和 InOrder[1..n ]中，设计一个构造二叉树 T 的链式存储结构的算法。

#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;

#define TElemType int

#define max 1024

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//设 T 的先序序列和中序序列分别放在数组 PreOrder[1..n]和 InOrder[1..n ]中，根据先序遍 历的特点可知，PreOrder[1]为根节点，设中序序列中 InOrder[i]=PreOrder[1]，则在 InOrder[i] 的左面的 InOrder[1..i-1]应为二叉树的左子树，而 InOrder[i+1..n]为根的右子树。相对应的是， 在先序序列中根的左子树应为 PreOrder[2..i]，而右子树为 PreOrder[i+1..n]。而左子树的根为 PreOrder[2]，右子树的根为 PreOrder[i+1]。依次递归，用同样的方法可以确定子树的左子树 和右子树，从而逐步确定整个二叉树

//递归
//              左子树             右子树
//先序      i1+1 -> i1+i-i2       i1+i+1-i2->j1
//后序        i2 -> i-1            i+1 -> j2

//这里因为T在函数内部还会改变，所以需要加个引用（也可以理解为二重指针）
void CreateTree(BiTree &T, TElemType preorder[], int i1, int j1, TElemType inorder[], int i2, int j2){
    int i=i2;   //先建立i，用于后续定位中序序列中的局部根结点位置
    if(i1<=j1){
        T=(BiTree) malloc(sizeof(BiTNode));
        T->data=preorder[i1];   //先序遍历的第一个结点为根结点
//        cout<<"add "<<T<<endl;
        T->lchild=NULL;
        T->rchild=NULL;
        while(inorder[i]!=preorder[i1])
            i++;    //找到根结点在中序遍历中的位置，以此左为左子树，右为右子树
//        cout<<"tag"<<endl;
        CreateTree(T->lchild, preorder, i1+1, i1+i-i2, inorder, i2, i-1);   //遍历左右子树
        CreateTree(T->rchild, preorder, i1+i+1-i2, j1, inorder, i+1, j2);
    }
    else
        T=NULL;
}

int main(){
    int preorder[7]={0,1,2,4,5,3,6};
    int inorder[7]={0,4,2,5,1,6,3};
    BiTree S=(BiTree) malloc(sizeof(BiTNode));
    CreateTree(S, preorder, 1, 6, inorder, 1, 6);
    queue<BiTree> q;
    q.push(S);
    cout<<"以层次遍历访问此树"<<endl;
    while(!q.empty()){
        BiTree t=q.front();
        q.pop();
        cout<<t->data<<endl;
        if(t->lchild!=NULL)
            q.push(t->lchild);
        if(t->rchild)
            q.push(t->rchild);
    }
}