#include<stdio.h>
#include<malloc.h>

typedef  struct trees
{
   char data;
   struct trees *lchild,*rchild;
}Binode, *bitree;

bitree bitree_precreat(bitree root,int pre_start,int pre_end,int mid_start,int mid_end,char *pre,char *mid)   //根据先序和中序建立一个二叉树的函数
{
     int i=0,lefttree_num, righttree_num;
     root=(bitree)malloc(sizeof(Binode));     
     root->data=pre[pre_start];  
     while(root->data!=mid[i])
     {
          i++;
     }
     i--;
     lefttree_num=i-mid_start;  //左子树中结点的个数
     printf("%d ",i);
     printf("%d ",lefttree_num);   //以下输出的几行只是想试验一下求的左右子树数字对不对。
     printf("%d ", mid_end);
     printf("%d ",mid_end-i);
     righttree_num=mid_end-i;                    //右子树中结点的个数
     printf("%d", righttree_num);
     printf("\n");
     if(lefttree_num>0)
     {                                           //左子树的个数   
         root->lchild=bitree_precreat(root->lchild,pre_start+1,pre_start+lefttree_num,mid_start,mid_start+lefttree_num-1,pre,mid);
     }
     else      
     {root->lchild=NULL;}
     if(righttree_num>0)
     {
         root->rchild=bitree_precreat(root->rchild,pre_end-righttree_num+1,pre_end,mid_end-righttree_num+1,mid_end,pre,mid);
     }
     else
     {root->rchild=NULL;}
     return root;
}

void  bitree_lastpostvisit(bitree root)    //后续遍历函数
{
  if(root!=NULL)
  {   
      bitree_lastpostvisit(root->lchild);
      bitree_lastpostvisit(root->rchild);
      printf("%c ",root->data);
  }
}     

void main()
{     
      int i=0,j,pre_start,pre_end,mid_start,mid_end;
      Binode p;
      bitree root;
      char a,pre[100],mid[100];
      root=&p;
      printf("请输入一个前列,结束时请按'#'号键：\n");  //输入一个按前序排列的序列！
      scanf("%c",&a);
      for(i=0;a!='#';i++)
      {   
          pre[i]=a;
          scanf("%c",&a);
      }
      //for(j=0;j<i;j++)
      //{
          //printf("%c ",pre[j]);
      //}
      pre_start=0,pre_end=i-2;     //设置pre的初始值,初始值是数组坐标，即数字-1
      printf("\n");
      printf("请输入一个中序,结束时请按'#'号键：\n");  //输入一个按中序排列的序列！
      scanf("%c",&a);
      for(i=0;a!='#';i++)
      {   
          mid[i]=a;
          scanf("%c",&a);
      }
      //for(j=0;j<i;j++)
      //{
          //printf("%c ",mid[j]);
      //}
      mid_start=0; mid_end=i-2;   //设置mid的初始值，初始值是数组坐标，即数字-1
      printf("%d",mid_end);
      printf("\n");
      root=bitree_precreat(root,pre_start,pre_end,mid_start,mid_end,pre,mid);     //根据先序和后续创建一个二叉树！
      bitree_lastpostvisit(root);
     
}