이진 탐색 트리 - 참가자 정보 관리 프로그램

Binary search tree를 사용한 “참가자 정보 관리 프로그램”

---

#define _CRT_SECURE_NO_WARNINGS

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

//데이터 형식 정의
typedef struct {
	char name[10];
	char date[10];
	char location[20];
} element;

//노드의 구조
typedef struct TreeNode {
	element key;
	struct TreeNode* left, * right;
} TreeNode;

//이진 탐색 트리 탐색에서 사용할 파라미터 함수
int compare(element a, element b)
{
	return strcmp(a.name, b.name);
}

//노드 갯수 세기
int count(TreeNode* root)
{
	int cnt = 0;
	if (root != NULL) {
		if (root->left == NULL && root->right == NULL)
			return 1;
		else
			cnt = count(root->left) + count(root->right);
	}
	return cnt;
}

// 이진 탐색 트리 탐색 함수
TreeNode* search(TreeNode* root, element key)
{
	TreeNode* p = root;
	
	while (p != NULL) {
		if (compare(key, p->key) == 0)
			return p;
		else if (compare(key, p->key) < 0)
			p = p->left;
		else if (compare(key, p->key) > 0)
			p = p->right;
	}
	//탐색에 실패했을 경우 NULL 반환
	return p;
}

//노드 생성
TreeNode* new_node(element item)
{
	TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;
	return temp;
}

//노드 삽입
TreeNode* insert_node(TreeNode* node, element key)
{
    //트리가 공백이면 새로운 노드 반환
	if (node == NULL)
		return new_node(key);

	//공백이 아닐 경우, 순환적으로 트리를 내려가며 탐색
	if (compare(key, node->key) < 0)
		node->left = insert_node(node->left, key);
	else if (compare(key, node->key) > 0)
		node->right = insert_node(node->right, key);
	
	//루트 포인터 반환
	return node;
}

TreeNode* min_value_node(TreeNode* node)
{
	TreeNode* current = node;
	//맨 왼쪽 단말 노드 찾기
	while (current->left != NULL)
		current = current->left;

	return current;
}

//이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 새로운 루트 노드를 반환
TreeNode* delete_node(TreeNode* root, element key)
{
	if (root == NULL)
		return root;

	//키가 루트보다 작은 경우
	if (compare(key, root->key) < 0)
		root->left = delete_node(root->left, key);
	//키가 루트보다 큰 경우
	if (compare(key, root->key) > 0)
		root->right = delete_node(root->right, key);
    //키와 루트가 같은 경우
	else {
        //삭제하려는 노드가 단말 노드거나, 하나의 서브트리만 가지고 있는 경우
		if (root->left == NULL) {
			TreeNode* temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL) {
			TreeNode* temp = root->left;
			free(root);
			return temp;
		}

        //삭제하려는 노드가 두개의 서브트리를 가지고 있는 경우
		TreeNode* temp = min_value_node(root->right);
        //중위 순회시 후계 노드 복사
		root->key = temp->key;
        //중위 순회시 후계 노드 삭제
		root->right = delete_node(root->right, temp->key);
	}
	return root;
}

int main(void)
{
	int answer = NULL;
	element e;
	TreeNode* root = NULL;
	TreeNode* tmp;
	char modify[20];

	printf("참가자 정보 관리 프로그램");
	
	while (1)
	{
		printf("\n입력(1), 검색(2), 정보 변경(3), 참가 취소(4), 종료(5)\n");
		scanf_s("%d", &answer);
		
		if (answer == 5 || count(root) > 99) {
			printf("\n종료합니다.");
			return 0;
		}
		
		switch (answer)
		{
		case 1:
			printf("정보를 입력하십시오.\n");
			printf("이름(영문 10자 이내)\n");
			scanf("%s", e.name);
			printf("신청날짜(YYYYMMDD)\n");
			scanf("%s", e.date);
			printf("신청지역(영문 20자 이내)\n");
			scanf("%s", e.location);

			tmp = search(root, e);

			if (tmp == NULL) {
				root = insert_node(root, e);
			}
			else {
				printf("이미 존재합니다.\n");
			}
			break;

		case 2:
			printf("검색할 이름을 입력하십시오.\n");
			scanf("%s", e.name);
			getchar();

			tmp = search(root, e);

			if (tmp != NULL) {
				printf("검색이 완료되었습니다.\n");
				printf("이름 %s \n", tmp->key.name);
				printf("신청날짜 %s \n", tmp->key.date);
				printf("신청지역 %s \n", tmp->key.location);
			}
			else {
				printf("존재하지 않는 이름입니다.\n");
			}
			break;

		case 3:
			printf("변경할 정보를 입력하십시오.(이름, 정보)\n");
			scanf("%s %s", e.name, modify);

			if (modify[0] >= 65) {
				strcpy(root->key.location, modify);
			}
			else {
				strcpy(root->key.date, modify);
			}
			break;

		case 4:
			printf("취소할 이름을 입력하십시오.\n");
			scanf("%s", e.name);
			getchar();

			tmp = search(root, e);

			if (tmp == NULL) {
				printf("존재하지 않는 이름입니다.\n");
				continue;
			}

			root = delete_node(root, e);
			printf("참가가 취소되었습니다.\n");

			break;
		}
	}
}