既知の木の最初の順序と中間順序は、「ツリーを再構築する方法」を巡回します.

2894 ワード

データ構造

多く言わないで直接コードを入れてください.
書いたのはやはりとても簡単で、再帰手続きです.

# include 
# include 
# include 
typedef struct node //         
{
  char data;
  struct node * lch; //    
  struct node * rch; //    
}Tree,*Ptree;
char pre[100];//          【       】 
char mid[100]; //         
void print(Ptree p);//          
Ptree creat(int pk,int mk,int mj);//        
int main ()
{
	scanf("%s",pre);
	scanf("%s",mid);
	int l=strlen(pre);//         
    Ptree p=creat(0,0,l-1);//         
	//        ,        ,         
    print(p);
    printf ("
");
	return 0;
} 
Ptree creat(int pk,int mk,int mj)
{
	Ptree p=(Ptree) malloc (sizeof(Tree));//           
	p->data=pre[pk];//         
	p->lch=NULL;//         
	p->rch=NULL;//          
	int root;
    for (root=mk;root<=mj;root++)//        
       	 if (pre[pk]==mid[root]) break;	
  	 int leftlength=root-mk;//       
  	 int rightlength=mj-root; //       
  	 if (leftlength>0) //if        0 
     p->lch=creat(pk+1,mk,root-1);//      
     if (rightlength>0) //if        0 
     p->rch=creat(pk+leftlength+1,root+1,mj);//      
     return p;//            P    
}
void print(Ptree p)//         
{
	if (p!=NULL)
	  { 
	   print(p->lch);
	   print(p->rch);
	   printf ("%c",p->data);	   
  	  }
}
/*
  1:
12473568
47215386
  : 
74258631
 */
/*
  2:
ABDCEF
BDAECF
  
DBEFCA
*/

もう一回変えてください.既知の後序と中序は先に巡回します.

# include 
# include 
# include 
typedef struct node //         
{
  char data;
  struct node * lch; //    
  struct node * rch; //    
}Tree,*Ptree;
char pre[100];//          【       】 
char mid[100]; //         
void print(Ptree p);//          
Ptree creat(int pk,int mk,int mj);//        
int main ()
{
	scanf("%s",pre);
	scanf("%s",mid);
	int l=strlen(pre);//         
    Ptree p=creat(l-1,0,l-1);//         
	//        ,        ,         
    print(p);
    printf ("
");
	return 0;
} 
Ptree creat(int pk,int mk,int mj)
{
	Ptree p=(Ptree) malloc (sizeof(Tree));//           
	p->data=pre[pk];//         
	p->lch=NULL;//         
	p->rch=NULL;//          
	int root;
    for (root=mk;root<=mj;root++)//        
       	 if (pre[pk]==mid[root]) break;	
  	 int leftlength=root-mk;//       
  	 int rightlength=mj-root; //            
    if (rightlength>0) //if        0 
     p->rch=creat(pk-1,root+1,mj);//      
  	 if (leftlength>0) //if        0 
     p->lch=creat(pk-rightlength-1,mk,root-1);//      

     return p;//            P    
}
void print(Ptree p)//         
{
	if (p!=NULL)
	  { 
       printf ("%c",p->data);	  
	   print(p->lch);
	   print(p->rch);
 
  	  }
}
/*
  1:
74258631
47215386
  : 
12473568
 */
/*
  2:
DBEFCA
BDAECF
  
ABDCEF
*/

uva 11995-I Can Gress the Data Structure!