#include<stdio.h>
#include<conio.h>
#include<windows.h>
#pragma warning (disable : 4996)
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     메뉴     \n");
	printf("1. 전위 탐방\n");
	printf("2. 중위 탐방\n");
	printf("3. 후위 탐방\n");
	printf("4. 이진 트리에 노드 삽입\n");
	printf("5. 프로그램 종료\n");
	printf("먼저 4번을 선택해서 이진 트리를 만들고, 그 이진 트리에서 탐방하라.\n");
	printf("4번의 입력 형태는 4 5와 같은 형태로 계속 같은 방법을 이용해 이진 트리를 만들어라.\n\n");
	// 메뉴의 선택번호가 5가 될 때까지 반복
	do
	{
		printf("메뉴를 입력하라.: ");
		scanf("%c", &ch);		  	         // 메뉴 선택번호 입력
		if (ch == '5')		   		// 프로그램 종료
		{
			printf("\n프로그램이 종료되었다!\n");
			break;
		}
		switch (ch)
		{
		case '1':     // 입력된 이진 트리에 대한 전위 탐방 출력
			printf("전위 탐방: ");
			preorder(prn);         // 전위 탐방 함수 호출
			printf("\b\b\b    \n");
			break;
		case '2':    // 입력된 이진 트리에 대한 중위 탐방 출력
			printf("중위 탐방: ");
			inorder(prn);    // 중위 탐방 함수 호출
			printf("\b\b\b    \n");
			break;
		case '3':  // 입력된 이진 트리에 대한 후위 탐방 출력
			printf("후위 탐방: ");
			postorder(prn);      // 후위 탐방 함수 호출
			printf("\b\b\b    \n");
			break;
		case '4':		        // 이진 트리를 입력받음 
			printf("노드 값 몇 개를 (마지막으로 –1을) 입력하라.: ");
			while (1) {
				scanf("%d", &x);
				if (x == -1)
					break;
				insert(x, &prn);
			}
			printf("\n");
			break;
		}
		scanf("%c", &ch);     // 필요 없는 엔터키를 입력받는 코드
	} while (1);
	system("PAUSE");
}