#include<iostream>
#include<math.h>
using namespace std;
class BitTree
{
    char *data;
    BitTree *lchild, *rchild;
    void preorder(BitTree *&T);   //先序遍历调用函数
    void inorder(BitTree *&T);    //中序遍历调用函数
    void postorder(BitTree *&T);   //后序遍历调用函数
public:
    void CreateBitTree(BitTree *&T);//二叉树创建函数

    void PreOrder(BitTree *&T)   //先序遍历
    {
        cout<<"先序遍历输出序列如下："<<endl;
        preorder(T);
        cout<<endl;
    }
    void InOrder(BitTree *&T)    //中序遍历
    {
        cout<<"中序遍历输出序列如下："<<endl;
        inorder(T);
        cout<<endl;
    }
    void PostOrder(BitTree *&T)//后序遍历
    {
        cout<<"后序遍历输出序列如下："<<endl;
        postorder(T);
        cout<<endl;
    }
    void CrtBt(BitTree *&T,char **&pre,char **&ino,int pe,int is,int n,int length);//利用先序中序序列重构二叉树
};

void BitTree::CreateBitTree(BitTree *&T)//二叉树创建函数定义
{
    char *ch=new char(10);
    cout<<"请输入当前节点字符:"<<endl;
    cin>>ch;
    if(*ch==‘#‘)        //定义如果输入为‘#’时表示没有该节点
        T=NULL;
    else
    {
        if(!(T=new BitTree))
        {
            cout<<"overflow"<<endl;
            return;
        }
        T->data=new char(strlen(ch)+1);
        strcpy(T->data,ch);
        cout<<"初始化 "<<T->data<<"的左节点:";
        CreateBitTree(T->lchild);      //构建T节点的左子树
        cout<<"初始化 "<<T->data<<"的右节点:";
        CreateBitTree(T->rchild);      //构建T节点的右子树
    }
}
void BitTree::preorder(BitTree *&T)//先序遍历
{
    if(T!=NULL)            //当前节点存在的话先输出当前节点的内容，在遍历其左右子树节点
    {
        cout<<T->data<<"    ";
        preorder(T->lchild);
        preorder(T->rchild);
    }
}
void BitTree::inorder(BitTree *&T)//中序遍历
{
    if(T!=NULL)          //当前节点存在，先遍历其左子树节点，然后输出当前节点内容，再遍历右子树节点
    {
       
        inorder(T->lchild);
        cout<<T->data<<"    ";
        inorder(T->rchild);
    }
}
void BitTree::postorder(BitTree *&T)//后序遍历
{
    if(T!=NULL)          //当前节点存在，先遍历其左子树节点，然后输出当前节点内容，再遍历右子树节点
    {
       
        postorder(T->lchild);
        postorder(T->rchild);
        cout<<T->data<<"    ";

    }
}
int search(char *ino[],char *ps,int n)//字符查询函数，查找ino字符串中是否有与ps一致
{
    int point=0;
    while(strcmp(*(ino+point),ps)!=0&&point<n)
    {
        point++;
    }
    if(point<n)
        return point;
    else
        return -1;

}

void BitTree::CrtBt(BitTree *&T,char **&pre,char **&ino,int ps,int is,int n,int length)
{
    /*已知pre[ps+n-1]是该二叉树的先序序列，
    ino[is+n-1]是二叉树的中序序列
    本算法由此两个序列重构二叉树
    核心思想：利用先序序列确定树根，然后用中序序列划分左右子树，
    并在左右子树不断重复以上步骤，知道所有序列都分配完
    */
    if(n==0)
        T=NULL;
    else
    {
        int k=search(ino,*(pre+ps),length);  //查询先序的某个节点在中序序列的位置
        if(k==-1) T=NULL;
        else
        {
            if(!(T=new BitTree))
            {
                cout<<"overflow"<<endl;
                return;
            }
            T->data=new char(strlen(*(pre+ps))+1);
            strcpy(T->data,*(pre+ps));
            if(k==is)
                T->lchild=NULL;
            else
                CrtBt(T->lchild,pre,ino,ps+1,is,k-is,length);//构建左子树
            if(k==is+n-1)
                T->rchild=NULL;
            else
                CrtBt(T->rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1,length);//构建右子树
        }
    }
}
void main()
{
    int n=7;
    char **pre;
    char **ino;
    pre=new char*[7];
    ino=new char*[7];
    cout<<"input pre"<<endl;
    for(int i=0;i<n;i++)
    {
        pre[i]=new char(1);
        cin>>pre[i];
    }
    cout<<"input ino"<<endl;
    for(int i=0;i<n;i++)
    {
        ino[i]=new char(1);
        cin>>ino[i];
    }
    BitTree *T;
    T->CrtBt(T,pre,ino,0,0,n,n);
    T->PostOrder(T);
    T->PreOrder(T);
    T->InOrder(T);
}