2009西電コンピュータ大学院生の再試験の上で問題(2)
2342 ワード
タイトルの説明
あるツリーの先頭シーケンスと中間シーケンスが既知であり、このツリーの後シーケンスシーケンスシーケンスをプログラミングして計算し、出力する.
入力
複数のグループのデータがあり、各グループは2行に分けて入力され、1行目は指定されたツリーのシーケンスを表し、2行目はこのツリーの中シーケンスを表し、シーケンス要素はすべて大文字の英語文字で、ツリーのノードを表します.
しゅつりょく
各配列のセットについて、二叉木の後続シーケンスを1行に出力します.
サンプル入力
サンプル出力
ヒント[+]
***プロンプトが非表示になっているので、上[+]をクリックすると***が表示されます.
ソース
2009年に西電のコンピュータの大学院生は再び試験して問題に乗ります
この問題は先序中序を試験して後序を求めることだ.もし后序の中序を见て先序を求めて私の博文を见ます:クリックしてリンクを开きます
あるツリーの先頭シーケンスと中間シーケンスが既知であり、このツリーの後シーケンスシーケンスシーケンスをプログラミングして計算し、出力する.
入力
複数のグループのデータがあり、各グループは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("
");
}
}