C언어 트리

Source Code

#include <stdio.h>

/*

		   8
		  /  \
	   3      10
	  / \       \
	2     5       14
				 /  \
				11   16
*/


//최대 노드 수를 저장할 변수
int MAX_node = 16;

// 트리를 저장할 배열
//tree[0]에는 노드갯수를 삽입한다.
//tree에서 빈부분은 -1로 표현한다.

int tree[] = { 8, 8, 3, 18, 2, -1, -1, 21, -1, -1, -1, -1, -1, -1, 11, -1 };


//노드의 왼쪽 자식 노드
//배열 tree의 원소들을 반환하므로 반환값 int , tree의 인덱스의 값을 매개변수로 받아야 하므로 int index라 작성
int get_left_child(int index)
{
	// 노드가 null이 아니고
	//노드가 -1이 아니고(null 노드 확인)&&왼쪽 자식 노드 성립조건에 맞다면 
	if (tree[index] != -1 && (2 * index) <= MAX_node)
		return 2 * index; //노드(tree[1]의 왼쪽 자식 노드 인덱스값 반환
	
	return -1;// 위의 조건에 맞지않을 시 실행 리턴값 없음
}

//노드의 오른쪽 자식노드
//배열 tree의 원소들을 반환하므로 반환값 int , tree의 인덱스의 값을 매개변수로 받아야 하므로 int index라 작성
int get_right_child(int index)
{
	// 노드가 null이 아니고
	//노드가 -1이 아니고(null 노드 확인)&&오른쪽 자식 노드 성립조건에 맞다면 
	if (tree[index] != -1 && ((2 * index) + 1) <= MAX_node)
		return (2 * index) + 1;
	
	return -1;// 위의 조건에 맞지않을 시 실행 리턴값 없음
}


//전위순회 D-L-R
//출력하는 함수이므로 반환값x 배열 tree의 index를 매개변수로 받는다.
void preorder(int index) 
{
	// tree[1]부터 출력한다.&&노드가 -1(null 노드)이 아니여야 한다.
	if (index > 0 && tree[index] != -1) 
	{
		printf(" %d ", tree[index]);//현재노드 방문 D
		preorder(get_left_child(index)); //왼쪽 서브트리 이동 L
		preorder(get_right_child(index)); //오른쪽 서브트리 이동 R
	}
}

//중위순회 L-D-R
//출력하는 함수이므로 반환값x 배열 tree의 index를 매개변수로 받는다.
void inorder(int index)
{  
	// tree[1]부터 출력한다.&&노드가 -1(null 노드)이 아니여야 한다.
	if (index > 0 && tree[index] != -1)
	{
		inorder(get_left_child(index)); //왼쪽 서브트리 이동 L
		printf(" %d ", tree[index]);// 현재노드 방문 D
		inorder(get_right_child(index)); //오른쪽 서브트리 이동 R
	}
}

//후위순회 L-R-D
//출력하는 함수이므로 반환값x 배열 tree의 index를 매개변수로 받는다.
void postorder(int index) 
{
	// tree[1]부터 출력한다.&&노드가 -1(null 노드)이 아니여야 한다.
	if (index > 0 && tree[index] != -1) 
	{
		postorder(get_left_child(index)); //왼쪽 서브트리 이동 L
		postorder(get_right_child(index)); //오른쪽 서브트리 이동 R
		printf(" %d ", tree[index]); //현재노드 방문 D
	}
}


// 이진 탐색 트리에서 노드의 위치를 탐색하는 연산
//반환값: 트리의 자료형 int ,트리에서 노드의 위치를 탐색하는 매개변수 받는다
int searchBST(int value) 
{
	int i = 1; //루트노드변수== tree[1]
	while (i >= 0) 
	{
		if (tree[i] > value)  //루트노드의 키값 >키값(value) : 왼쪽서브트리 탐색한다.
		{
			i = get_left_child(i); //함수 호출해서 찾는다.
		}
		else if (tree[i] < value) ///루트노드의 키값 <키값(value) : 오른쪽서브트리 탐색한다.
		{
			i = get_right_child(i); 
		}
		else 
		{
			return i;  
		}
	}

	return i;
}

//메뉴를 출력한다.출력만 하는 함수이므로 매개변수,반환값x
void menu() {
	printf("\n*---------------------------*");
	printf("\n\t1 : 트리 출력");
	printf("\n\t2 : 숫자 검색");
	printf("\n\t3 : 종료");
	printf("\n*---------------------------*");
	printf("\n메뉴입력 >> ");
}

int main() 
{
	int key, foundedNode; //노드찾기에 쓰이는 변수 key: 찾고자 하는 노드 원소의 값 ,foundedNode:찾고자 하는 노드 인덱스의 값
	int choice; //메뉴 선택에 쓰이는 변수

	while (1) //무한 반복
	{
		menu();
		scanf(" %d", &choice); //choice의 값 입력받는다

		switch (choice) 
		{
		case 1://입력받은 choice값 1이면 실행(출력)
			printf("\t[이진 트리 출력]\n ");
			printf("\nPreorder:\n");
			preorder(1); //tree[1]부터 출력한다.
			printf("\nPostorder:\n");
			postorder(1);
			printf("\nInorder:\n");
			inorder(1);
			printf("\n");
			break;
		case 2: //입력받은 choice값 2이면 실행(검색)
			printf("찾을 숫자를 입력하세요 : ");
			scanf("%d", &key); //찾고 싶은 노드원소를 입력받는다.
			foundedNode = searchBST(key); //searchBST함수의 매개변수 key 값으로 찾아낸다.
			if (foundedNode != -1)//노드의 인덱스가 1이 아니라면 (null값이 아니라면)
				printf("\n %d를 찾았습니다!  \n", key);
			else printf("\n 숫자를 찾지 못했습니다. \n");
			break;
		case 3: //입력받은 choice값 3이면 실행
			printf("프로그램을 종료합니다.\n");
			return 0;
		default: //1,2,3 이 아닐때 실행 
			printf("없는 메뉴입니다. 메뉴를 다시 선택하세요! \n");
			break;
		}
	}
	return 0;
}

 

실행 결과