#include<stdio.h>
#ifdef _WIN32
	#include<conio.h>
	#include<Windows.h>
#endif

typedef struct node *tree_ptr;
typedef struct node
{
	tree_ptr left;
	int data;
	tree_ptr right;
}node;

void preorder(tree_ptr p)
{
	if(p!=NULL)
	{
		printf("%3d)",p->data);
		preorder(p->left);
		preorder(p->right);
	}
}

void inorder(tree_ptr p)
{
	if(p!=NULL)
	{
		inorder(p->left);
		printf("%3d)",p->data);
		inorder(p->right);
	}
}

void postorder(tree_ptr p)
{
	if(p!=NULL)
	{
		postorder(p->left);
		postorder(p->right);
		printf("%3d)",p->data);
	}
}

void insert(int x,tree_ptr *p)
{
	if(*p==NULL)
	{
		*p=(tree_ptr)malloc(sizeof(node));
		(*p)->data=x;
		(*p)->right=NULL;
		(*p)->left=NULL;
	}else if(x<(*p)->data)
	{
		insert(x,&((*p)->left));
	}else
	{
		insert(x,&((*p)->right));
	}
}

void main()
{
	tree_ptr prn=NULL;
	char ch;
	int x;

	printf("\n### Select number ###\n");
	printf("1. 전위 탐방(preorder)			search\n");
	printf("2. 중위 탐방(inorder)			search\n");
	printf("3. 후위 탐방(postorder) 		search\n");
	printf("4. insert\n");
	printf("5. ######## end ########\n");
	printf("먼저 4번을 선택해서 이진 트리를 만들고 그 이진 트리에서 탐방 하세요.\n");
	printf("4번의 입력 형태는 4 5와 같은 형태로 계속 같은 방법을 이용해서 이진 트리를 만드세요.\n");
	do
	{
		scanf("%c", &ch);

		if(ch == '5')
		{
			break;
		}

		switch(ch)
		{
		case '1':
			preorder(prn);
			break;
		case '2':
			inorder(prn);
			break;
		case '3':
			postorder(prn);
			break;
		case '4':
			scanf("%d",&x);
			insert(x,&prn);
			break;
		}
	}while(1);

	printf("######## end ########\n");

	system("PAUSE");
}