データ構造実験の二叉樹五:層順エルゴード
2058 ワード
データ構造実験の二叉樹五:層順エルゴード
Time Limit:1000 MS Memory limit:65536 K
テーマの説明
abd、eg、cf、などの最初の順序で入力された文字列が知られています.二叉の木を創立して、二叉の木の階層がシーケンスを遍歴することを求めます.
入力
入力データは複数行あり、1行目は整数tである. (t<1000)は、t行のテストデータがあることを表します.各行は
50文字以下の長さの文字列.
出力
二叉のツリーを出力する階層は、シーケンスを巡回します.
例の入力
ソース
xam
このテーマの要求はこの先に入力された二叉の木を上から下へ順番に左から右へ出力することです.だから私たちはまずこの二叉の木を作ってから、階層的に遍歴して、全部の時間をかけて出力できます.どのように出力を階層的に巡回しますか?主な難点は、二叉の木をそれぞれの層に遍歴させることです.再帰的な操作ができます.その後、循環変数を設定して、始点から遍歴するようにしてください.そして、一回ごとに追加して、つまり深い層に入れて、二叉の木を層状にして出力することができます.ps:行列でもいいですが、それはちょっと面倒ですので、ここでは言いません.
こんな無駄話をしました.コードは次の通りです.
Time Limit:1000 MS Memory limit:65536 K
テーマの説明
abd、eg、cf、などの最初の順序で入力された文字列が知られています.二叉の木を創立して、二叉の木の階層がシーケンスを遍歴することを求めます.
入力
入力データは複数行あり、1行目は整数tである. (t<1000)は、t行のテストデータがあることを表します.各行は
50文字以下の長さの文字列.
出力
二叉のツリーを出力する階層は、シーケンスを巡回します.
例の入力
2
abd,,eg,,,cf,,,
xnl,,i,,u,,
サンプル出力abcdefg
xnuli
ヒントソース
xam
このテーマの要求はこの先に入力された二叉の木を上から下へ順番に左から右へ出力することです.だから私たちはまずこの二叉の木を作ってから、階層的に遍歴して、全部の時間をかけて出力できます.どのように出力を階層的に巡回しますか?主な難点は、二叉の木をそれぞれの層に遍歴させることです.再帰的な操作ができます.その後、循環変数を設定して、始点から遍歴するようにしてください.そして、一回ごとに追加して、つまり深い層に入れて、二叉の木を層状にして出力することができます.ps:行列でもいいですが、それはちょっと面倒ですので、ここでは言いません.
こんな無駄話をしました.コードは次の通りです.
#include
#include
#include
typedef char Qelement;
typedef struct node
{
Qelement data;
struct node *lchild,*rchild;
}node,*nodeptr;
char a[55];
int i;
struct node *Creat()//
{//
struct node *T;
if(a[i++]==',')T=NULL;
else
{
T=(struct node *)malloc(sizeof(struct node));
T->data=a[i-1];
T->lchild=Creat();
T->rchild=Creat();
}
return T;
}
int treelevel(struct node *T,int level)
{
if(!T)// ,
return 0;// ,
if(level==0)// ,
{
printf("%c",T->data);
return 1;// 1,
}// , ,
return treelevel(T->lchild,level-1)+treelevel(T->rchild,level-1);
}
void level1(struct node *T)
{// ,
int i=0;
for(i=0;;i++)// while
{
if(!treelevel(T,i))
break;// , ,
}
}
int main()
{
struct node *T;
int t;
scanf("%d",&t);
while(t--)
{
i=0;
scanf("%s",a);
T=Creat();
level1(T);
printf("
");
}
return 0;
}
注記参考までに環境codeblocksをコンパイルします.