二叉树序列构建

根据二叉树的前序,中序与后序序列构建二叉树

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct node /*二叉树结构定义*/
{
    char data;
    struct node *lchild,*rchild;
}binnode;
typedef binnode *bintree;

bintree  CreateBinTreebyPreIn(char *pre,char *in,int n){
    bintree t;
    int k;
    char *p,r;
    if(n<=0){
        return NULL;
    }
    r=*pre;
    t=(bintree)malloc(sizeof(binnode));
    t->data=r;
    for(p=in;p<in+n;p++)
        if(*p==r) break;
    k=p-in;
    t->lchild=CreateBinTreebyPreIn(pre+1,in,k);
    t->rchild=CreateBinTreebyPreIn(pre+k+1,p+1,n-1-k);
    return t;
}
bintree  CreateBinTreebyPostIn(char *in,char *post,int n){
           bintree t;
           int k;
           char r,*p;
           if(n<=0){
            return NULL;
           }
           r=*(post+n-1);
           t=(bintree)malloc(sizeof(binnode));
           t->data=r;
           for(p=in;p<in+n;p++){    //在in中查找根节点
            if(*p==r) break;
           }
           k=p-in;//k为根节点在in中的位置
           t->lchild=CreateBinTreebyPostIn(in,post,k);
           t->rchild=CreateBinTreebyPostIn(p+1,post+k,n-k-1);
           return t;
}/*由中序序列in和后序序列post构造二叉树，并返回树根结点指针，如果树为空返回NULL        */

void DispBinTree(bintree t){
    if (t!=NULL)
    {
        printf("%c",t->data);
        if (t->lchild || t->rchild)
        {
            printf("(");
            DispBinTree(t->lchild);
            if (t->rchild) printf(",");
            DispBinTree(t->rchild);
             printf(")");
        }
    }
}/* 以括号表示法输出二叉树*/

int main()
{   bintree T;
    char pre[MaxSize],in[MaxSize],post[MaxSize];
    int n;

    scanf("%d",&n);getchar();
    scanf("%s",pre);
    scanf("%s",in);
    scanf("%s",post);
    T=CreateBinTreebyPreIn(pre,in,n);
    printf("\nthe result is:");
    if (T==NULL)
        printf("\nnull");
    else
        DispBinTree(T);
    T=CreateBinTreebyPostIn(in,post,n);
    printf("\nthe result is:");
    if (T==NULL)
        printf("\nnull");
    else
        DispBinTree(T);
    return 0;
}