2009西電コンピュータ大学院生の再試験の上で問題(2)


タイトルの説明
あるツリーの先頭シーケンスと中間シーケンスが既知であり、このツリーの後シーケンスシーケンスシーケンスをプログラミングして計算し、出力する.
 
入力
複数のグループのデータがあり、各グループは2行に分けて入力され、1行目は指定されたツリーのシーケンスを表し、2行目はこのツリーの中シーケンスを表し、シーケンス要素はすべて大文字の英語文字で、ツリーのノードを表します.
 
しゅつりょく
各配列のセットについて、二叉木の後続シーケンスを1行に出力します.
 
サンプル入力
ABDGCEFH
DGBAECHF

 
サンプル出力
GDBEHFCA

 
ヒント[+]
***プロンプトが非表示になっているので、上[+]をクリックすると***が表示されます.
 
ソース
2009年に西電のコンピュータの大学院生は再び試験して問題に乗ります
 
この問題は先序中序を試験して後序を求めることだ.もし后序の中序を见て先序を求めて私の博文を见ます:クリックしてリンクを开きます
/********************************* 
 *      :2013-3-11
 *      :SJF0115 
 *      :   OJ   1218: Problem D
 *      :http://acmclub.com/problem.php?id=1218
 *      :AC 
 *      :2009               
 *      : 
**********************************/ 
#include<stdio.h>
#include<string.h>
#include<malloc.h>

//       
typedef struct BiTNode{  
    //    
    char data;  
    //        
    struct BiTNode *lchild,*rchild;  
}BiTNode,*BiTree; 

/*
	PreIndex:                  PreArray[]    
    InIndex:                   InArray[]    
	subTreeLen:            
	PreArray:       
	InArray:      
*/


char PreArray[101],InArray[101];

void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){
	//subTreeLen < 0     
	if(subTreeLen <= 0){
		T = NULL;
		return;
	}
	else{
		T = (BiTree)malloc(sizeof(BiTNode));
		//     
		T->data = PreArray[PreIndex];
		//              
		int index = strchr(InArray,PreArray[PreIndex]) - InArray;
		//       
		int LenF = index - InIndex;
		//     
		PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);
		//       (    -     -      )
		int LenR = subTreeLen - 1 - LenF;
		//     
		PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);
	}
}

//        
void PostOrder(BiTree T){    
    if(T != NULL){    
        //          
        PostOrder(T->lchild);    
        //          
        PostOrder(T->rchild);   
        //         
        printf("%c",T->data);  
    }    
}    

int main(){
	while(scanf("%s %s",PreArray,InArray) != EOF){
		BiTree T;
		PreInCreateTree(T,0,0,strlen(InArray));
		PostOrder(T);
		printf("
"); } }