앞 순서 시퀀스 + 중간 순서 시퀀스 또는 중간 순서 시퀀스 + 후 순서 시퀀스 에 따라 이 진 트 리 를 복원 합 니 다.

#include 
#include 

typedef struct BTNode{//      
    char data;
    struct BTNode *lchild,*rchild;
}BTNod;


BTNode *createBT(char pre[],int l1,int r1,char in[],int l2,int r2){//   +        
    BTNode *s;//         
    int i;
    if(l1>r1){
        return NULL;
    }else{
        s=(BTNode *)malloc(sizeof(BTNode));//         
        s->lchild=NULL;//          
        s->rchild=NULL;
        for(i=l2;i<=r2;i++){
            if(in[i]==pre[l1]){//            
                break;
            }
        }
        s->data=in[i];//              
        s->lchild=createBT(pre,l1+1,l1-l2+i,in,l2,i-1);//      ,           
        s->rchild=createBT(pre,l1-l2+i+1,r1,in,i+1,r2);//           
    }
}

BTNode *createBT2(char post[],int l1,int r1,char in[],int l2,int r2){//   +        
    BTNode *s;//         
    int i;
    if(l1>r1){
        return NULL;
    }else{
        s=(BTNode *)malloc(sizeof(BTNode));
        s->lchild=NULL;
        s->rchild=NULL;
        for(i=l2;i<=r2;i++){
            if(in[i]==post[r1]){//            
                break;
            }
        }
        s->data=in[i];
        s->lchild=createBT2(post,l1,l1-l2+i-1,in,l2,i-1);//      ,           
        s->rchild=createBT2(post,l1-l2+i,r1-1,in,i+1,r2);//           
    }
}

void preOrder(BTNode *p){//     
    if(p!=NULL){
        printf("%c ",p->data);
        preOrder(p->lchild);
        preOrder(p->rchild);
    }
}

void postOrder(BTNode *p){//     
    if(p!=NULL){
        postOrder(p->lchild);
        postOrder(p->rchild);
        printf("%c ",p->data);
    }
}
int main(int argc, char** argv) {
    BTNode *p;
    char pre[]={'a','b','d','c'};//       
    char in[]={'b','d','a','c'};//       
    char post[]={'d','b','c','a'};//       
    int l1,r1,l2,r2;
    l1=l2=0;
    r1=r2=3;
    printf("   +              : ") ;
    p=createBT(pre,l1,r1,in,l2,r2);
    postOrder(p);
    printf("
");

    printf("   +              : ") ;
    p=createBT2(post,l1,r1,in,l2,r2);
    preOrder(p);
    return 0;
}