C_Programing_Project : 이진탐색트리 프로그램

02. 사용자로부터 정수들을 입력받아 이진 탐색 트리 안에 저장하고 다음과 같은 기능을 하는 프로그램을 작성하라.

************** 
i: 입력
d: 삭제 
s: 탐색 
v: 순회
n: 트리의 높이를 구한다. 
c: 노드의 개수를 계산한다. 
t: 단말 노드의 개수를 출력한다. 
m: 가장 큰 값을 출력한다. 
n: 가장 작은 값을 출력한다. 
x: 노드를 전부 삭제
p: 출력
q: 종료
**************

입력(i): 사용자로부터 숫자를 입력받아 탐색 트리 안에 저장한다

삭제(d): 사용자로부터 숫자를 입력받아 탐색 트리로부터 숫자를 삭제한다.

탐색(s): 사용자로부터 숫자를 입력받아 탐색 트리를 탐색하여 숫자의 존재여부를 표시한다(

높이(h): 현재 생성된 이진 탐색 트리의 높이를 반환한다. 

노드의 개수(c): 현재 생성된 이진 탐색 트리안의 노드의 개수를 반환한다.

단말 노드의 개수(t): 현재 생성된 이진 탐색 트리안의 단말 노드의 개수를 반환한다. 

순회(v): 현재 생성된 이진 탐색 트리를 표준적인 3가지 방법으로 순회하고 순회한 결과를 화면에 출력한다.

최대숫자(m): 탐색 트리안의 가장 큰 숫자를 표시한다. 함수 get_maximum(TreeNode *root)를 작성한다. 이진 
탐색 트리에서 가장 큰 값은 가장 오른쪽에 있다. 

 

완벽한코드가 아닙니다..참고용으로 사용해주세요..

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<Windows.h>
#include<time.h>


typedef int element;
typedef struct Node
{
	element Key;
	// struct Node* Link;
	struct Node* LeftLink;
	struct Node* RightLink;	//왼쪽연결	//오른쪽연결
}Node;

// 함수 전방선언   함수이름 클릭후 F12누르면 함수로 이동
Node* CreateNode(int Key);							// 데이터생성
Node* Insert(Node* Head, int Key);					// NULL링크에 연결
void Display(Node* p);										// 출력함수
Node* Insert(Node* node, int Key);					// NULL일때 NULL링크로 연결
Node* Minvalue(Node* node);				// 작은값으로 내려간다.
void PrintNode(Node* Node);
void InOrder(Node* Node);
void PostOrder(Node* Node);
Node* Delete(Node* node, int Key);
void Release(Node* node);
int GetHeight(Node* Root);
int GetNodeCount(Node* node);
int GetLeafCount(Node* node);
int GetMaximum(Node* Root);
int GetMinimum(Node* Root);
void PrintOrder(Node* Root);
Node* Search(Node* Node, int Key);
void SearchNode(Node* Root);



// 데이터 생성
Node* CreateNode(int Key)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->Key = Key;
	NewNode->LeftLink = NewNode->RightLink = NULL;
	return NewNode;
}

// 링크 링크 링크 로 갔을 떄 NULL일때 NULL링크에 연결시킨다.
Node* Insert(Node* node, int Key)
{
	// 재귀함수가 풀리기 위한 조건
	// NULL일 경우에 데이터를 생성해준다.
	if (node == NULL)
		return CreateNode(Key);
	if (Key < node->Key)
		node->LeftLink = Insert(node->LeftLink, Key);
	else if (Key > node->Key)
		node->RightLink = Insert(node->RightLink, Key);
	else
	{
		printf("%d는 이미 존재하는 Data입니다.\n", Key);
		system("pause");
	}
	return node;
}

Node* Minvalue(Node* node)
{
	Node* current = node;

	while (current->LeftLink != NULL)
		current = current->LeftLink;

	return current;
}

// 전위 중위 후위 출력
void PrintNode(Node* Node)
{
	printf("%3d\n", Node->Key);

}
void PreOrder(Node* Node)
{
	if (Node == NULL)
		return;
	PrintNode(Node);//Root;
	PreOrder(Node->LeftLink);//Left
	PreOrder(Node->RightLink);//Right
}

void InOrder(Node* Node)
{
	if (Node == NULL)
		return;
	InOrder(Node->LeftLink);//Left
	PrintNode(Node);//Root;
	InOrder(Node->RightLink);//Right
}

void PostOrder(Node* Node)
{
	if (Node == NULL)
		return;
	PostOrder(Node->LeftLink);//Left
	PostOrder(Node->RightLink);//Right
	PrintNode(Node);//Root;
}

// 삭제함수(재귀함수)
Node* Delete(Node* node, int Key)
{
	if (node != NULL)
	{
		if (node->Key == Key)	// 노드의데이터와 내가 찾는 데이터와 일치하는지 확인
		{
			Node* DeleteNode = node;	// 노드보관
			node = node->RightLink;
			free(DeleteNode);	// 메모리 해제
		}
		else
			node->RightLink = Delete(node->RightLink, Key);	// 데이러를 찾아와라
	}
	return node;
}

// 전체 할당 하면서 삭제
void Release(Node* node)
{
	if (node == NULL)
		return;
	Release(node->RightLink);	// 리던이 풀리면서 삭제
	printf("해제 : %d\n", node->Key);	// 삭제데이터 출력
	free(node);		// 할당해제
}


int GetHeight(Node* Root)  //높이 구하기 연산
{
	if (!Root)
		return 0;
	else
	{
		int left = GetHeight(Root->LeftLink);
		int right = GetHeight(Root->RightLink);
		return 1 + (left > right ? left : right);
	}
}

int GetNodeCount(Node* node) //노드의 개수 구하는 연산
{
	int count = 0;

	if (node != NULL)
		count = 1 + GetNodeCount(node->LeftLink) + //루트와 왼쪽으로 가고 오른쪽으로 가서 노드를 탐색하여 계산한다.
		GetNodeCount(node->RightLink);

	return count;
}



int GetLeafCount(Node* node) //단말 노드 개수 구하는 연산
{
	int count = 0;

	if (node != NULL)
	{
		if (node->LeftLink == NULL && node->RightLink == NULL)  //노드의 왼쪽과 오른쪽이 NULL일때 1을 반환하고 
			return 1;
		else
			count = GetLeafCount(node->LeftLink) + GetLeafCount(node->RightLink);  //그 반환한 값을 더해서 count에 저장한다.
	}
	return count;
}

void Display(Node* dis)  //화면에 출력해주는 함수
{
	if (dis != NULL)
	{
		printf("(");
		Display(dis->LeftLink);
		printf("%d", dis->Key);
		Display(dis->RightLink);
		printf(")");
	}
}


int GetMaximum(Node* Root) //최대값 함수
{
	if (Root == NULL)
	{
		return -1;
	}
	else if (Root->RightLink == NULL) //이진 탐색 트리의 특성상 오른쪽에 있는 노드들이
	{                             //더 크기 때문에 NLLL이 될 때까지 이동한다.
		return Root->Key;
	}
	else
	{
		return GetMaximum(Root->RightLink);
	}
}

int GetMinimum(Node* Root)// 최솟값 구하는 함수
{
	if (Root == NULL)
	{
		return -1;
	}
	else if (Root->LeftLink == NULL) //이진 탐색 트리의 특성상 왼쪽에 있는 노드들이
	{                            //더 작기 때문에 왼쪽으로 이동한다.
		return Root->Key;
	}
	else
	{
		return GetMinimum(Root->LeftLink);
	}
}

// 순회함수 전위, 중위, 후위
void PrintOrder(Node* Root)
{
	system("cls");
	printf("===== 순회함수 선택 =====\n");
	printf("   1. PreOrder\n");
	printf("   2. InOrder\n");
	printf("   3. PostOrder\n");
	printf("====================\n");
	int Select;
	printf("Select : ");
	scanf("%d", &Select);
	system("cls");
	switch (Select)
	{
	case 1:
		PreOrder(Root);
		break;
	case 2:
		InOrder(Root);
		break;
	case 3:
		PostOrder(Root);
		break;
	}
	system("pause");
}

// 탐색에서 입력받은 데이터를 찾아주는 함수
Node* Search(Node* Node, int Key)
{
	if (Node == NULL)
		return NULL;
	else if (Node->Key == Key)
		return Node;
	else if (Node->Key > Key)
		return Search(Node->LeftLink, Key);//LeftLink
	else
		return Search(Node->RightLink, Key);//RightLink
}

// 탐색 입력
void SearchNode(Node* Root)
{
	int Key;
	printf("Key : ");
	scanf("%d", &Key);
	Node* FindNode = Search(Root, Key);
	if (FindNode == NULL)
		printf("해당 Data %d는 존재하지 않습니다.\n", Key);
	else
		PrintNode(FindNode);
	system("pause");
}

void main()
{
	srand(time(NULL));
	int sum1 = 0;
	int sum2 = 0;
	Node* Root = NULL;
	int Key;
	while (TRUE)
	{
		system("cls");
		//Print(Head);
		printf("===이진탐색트리_프로그램===\n");
		printf("  1.   입력\n");
		printf("  2.   탐색\n");
		printf("  3.   출력\n");	// 출력시 전위 후위 후위 탐색 선택해서 출력
		printf("  4.   순회\n");	// 5번과 마찬가지로 순회 방법 선택후 출력
		printf("  5.   트리의 높이\n");
		printf("  6.   노드의 갯수\n");
		printf("  7.   단말 노드의 갯수\n");
		printf("  8.   가장 큰값\n");
		printf("  9.   가장 작은 값\n");
		printf("  10.  삭제\n");
		printf("  11.  전체 삭제\n");	// 노드 전부삭제와 종료를 동시에
		printf("  12.  Exit\n");	// 종료를 눌르면 노드를 전부삭제한다.
		printf("====================\n");
		printf("Selection : ");
		int Select;
		scanf("%d", &Select);
		switch (Select)
		{
		case 1:
			printf("입력 : ");
			scanf("%d", &Key);
			Root = Insert(Root, Key);
			break;
		case 2:
			SearchNode(Root);
			break;
		case 3:
			Display(Root);
			printf("\n");
			system("pause");
			break;
		case 4:
			PrintOrder(Root);
			break;
		case 5:
			sum1 = GetHeight(Root);
			printf("트리의 높이 : %d\n", sum1);
			system("pause");
			break;
		case 6:
			sum1 = GetNodeCount(Root);
			printf("노드의 개수 : %d\n", sum1);
			system("pause");
			break;
		case 7:
			sum2 = GetLeafCount(Root);
			printf("단말 노드의 개수 : %d\n", sum2);
			system("pause");
			break;
		case 8:
			sum1 = GetMaximum(Root);
			printf("가장 큰 값 : %d\n", sum1);
			system("pause");
			break;
		case 9:
			sum1 = GetMinimum(Root);
			printf("가장 작은 값 : %d\n", sum1);
			system("pause");
			break;
		case 10:
			printf("Delete Data : ");
			scanf("%d", &Select);
			Delete(Root, Select);
			break;
		case 11:
		case 12:
			Release(Root);
			system("pause");
			return;
		}
	}
}

 

완벽한코드가 아닙니다. 참고용으로 쓰세요~!