tree recovery.cpp

树的先序

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
#define OVERFLOW   0
typedef struct BiTNode{
        char       data;
        struct BiTNode  *lchild,*rchild;
        }BiTNode,*BiTree;
char pre[30];
char in[30];
BiTree creattree(char *a ,int p,int q,char *b,int r,int s)
{       
        //printf("%s %s\n",a,b);
        BiTree T; 
        int i;    
        for(i=r;i<=s;i++)
        if(b[i]==a[p])
        break;
        //printf("%d\n",i);
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=a[p];
        //printf("%c\n",T->data);
        if(p==q&&r==s)
        {T->lchild=NULL;
         T->rchild=NULL;
         return T;
        }
        if(i==r)
        {T->lchild=NULL;}
        else  T->lchild=creattree(a,p+1,p+(i-r),b,r,i-1);
        if(i==s)
        {T->rchild=NULL;}
        else
              T->rchild=creattree(a,p+(i-r)+1,q,b,i+1,s);
        return T;
}
int postorder(BiTree T){
        if(T)
          if(postorder(T->lchild))
           if(postorder(T->rchild))
            printf("%c",T->data);
        return 1;
}
int main()
{  int i,j;
   while(scanf("%s %s",pre,in)!=EOF)
   {   
       //printf("%s %s\n",pre,in);
       BiTree T;
       i=strlen(pre);
       j=strlen(in);
       //printf("%d %d\n",i,j);
       T=creattree(pre,0,i-1,in,0,j-1);
       postorder(T);
       printf("\n");
   }
   system("pause");
   return 0;
}