#include<stdio.h>
#include<stdlib.h>

#define N 100//S配列の長さ
//cellの構造体
struct cell{
	int node;
	struct cell *next;
};
//関数を下で呼び出しているので先に定義しておく
void preorder(int k,struct cell **S);
void postorder(int k,struct cell **S);
void inorder(int k,struct cell **S);
//===================ここからメイン====================================================
int main(int argc,char* argv[]){
	struct cell *S[N],*q,*p,*r,*s;
	int root=0;
	int b;
	printf("preorder:1\ninorder:2\npostorder:3\n");
	scanf("%d",&b);
	for(int i=0;i<N-1;i++) {
	S[i]=(cell *)malloc(sizeof(cell));
	S[i]->next=NULL;//S[N]のすべてのnextにNULLを入れる
	S[i]->node=11;//S[N]のすべてに逃げる数字を入れる
}
//==================Ｓ［０］に１、２をつなぐ=====================================
	//スタックと同じつなぎ方なので先に２を入れてから１を入れる
	for(int i=2;i>0;i--){//nodeに１と2を入れるために2から1
	q=(cell *)malloc(sizeof(cell));
	q->node=i;//qのnodeに１と２を入れる
	q->next=S[root]->next;//S[0]に１、１に２をつなげる
	S[root]->next=q;
	}
//===================Ｓ［１］に３，４，５をつなぐ=======================================================
	//上と同じつなぎ方でつなげる
	for(int i=5;i>2;i--){
		p=(cell *)malloc(sizeof(cell));
		p->node=i;
		p->next=S[1]->next;//S[1]に５、４、３をつなげる
		S[1]->next=p;
	}
//===========================================================================
	for(int i=7;i>5;i--){
		r=(cell *)malloc(sizeof(cell));
		r->node=i;
		r->next=S[2]->next;//S[2]に７、６をつなげる
		S[2]->next=r;
	}
//=============================================================================
	for(int i=9;i>7;i--){
		s=(cell *)malloc(sizeof(cell));
		s->node=i;
		s->next=S[6]->next;//S[6]に９，８をつなげる
		S[6]->next=s;
	}
	switch(b){
		case 1:
	printf("preorder:");
	preorder(root,S);//前順関数の関数を呼び出す
	break;
		case 2:
	printf("\ninorder:");
	inorder(root,S);//中順関数を呼び出す
	break;
		case 3:
	printf("\npostorder:");
	postorder(root,S);//後順関数を呼び出す
	break;
	printf("\n");
	}
}
//===================前順=========================================================
/*ほぼ教科書と同じだが、S配列の中身は、参照したくないので
１１を逃げにして、if(q->node==0) q=q->next;を書く。
これで、Ｓ配列の中のnodeは読まれない*/
void preorder(int k,struct cell **S)
{
	struct cell *q;
	printf("%d",k);//前順は先に数字を出力する
	q=S[k];
	if(q->node==11) q=q->next;//S配列のときは次へ
	while(q!=NULL){//ポインタが最後まで呼び出したらwhileを抜ける
		preorder(q->node,S);//再起呼び出し!!
		q=q->next;//qに次のセルを指させる
	}
	return;
}
//=======================後順========================================================
void postorder(int k,struct cell **S)
{
	struct cell *q;
	q=S[k];
	if(q->node==11) q=q->next;
	while(q!=NULL){
		postorder(q->node,S);
		q=q->next;
	}
	printf("%d",k);//後順は、後ろで出力
	return;
}
//========================中順===========================================================
void inorder(int k,struct cell **S)
{
	struct cell *q;
	int count=0;
	q=S[k];
	if(q->node==11) q=q->next;
	while(q!=NULL){
		inorder(q->node,S);
		if(count==0)printf("%d",k);//1回目じゃなければ出力する
		q=q->next;
		count++;//ここを通るのが何回目なのかをカウントする
	}
	if(count==0)printf("%d",k);//1回目じゃなければ出力する
	return;
}
//===========================================
//出力結果
//===========================================
//preorder:0134526897
//inorder:3145086927
//postorder:3451896720