[C] C언어로 이진트리를 구현하기 2
학원에서 배운 C로 이진트리를 구현하는 과정을 이 포스트에다가 저장한다.
파이썬에서는 클래스와 무한루프를 이용해서 이진트리를 구현하였는데, C언어에서는 무한루프를 사용하기 힘들어서
재귀함수로 구현하였다.
그리고 재귀함수를 이용하니 전위순회, 중위순회, 후위순회까지 잘 구현할 수 있었다.
그래도 근본적인 내용은 C와 파이썬 둘 다 같은 것 같다.
구현 코드
#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
enum treeMenu {
TERMINATE, ADD, REMOVE, SEARCH, PRINT, MIN, MAX
};
typedef struct treeNode {
int value;
struct treeNode* left;
struct treeNode* right;
}treeNode;
treeNode* addNode(treeNode* t, int data);
void _print(treeNode* t);
void terminate(treeNode* t);
treeNode* findMin(treeNode* t);
treeNode* findMax(treeNode* t);
treeNode* removeNode(treeNode* t, int data);
treeNode* searchNode(treeNode* t, int data);
int main() {
int select, data;
treeNode* root = NULL; // 첫 노드의 주소를 저장한다.
treeNode* find;
while (1) {
system("clear");
printf("1. add\n");
printf("2. remove\n");
printf("3. search\n");
printf("4. print\n");
printf("5. min\n");
printf("6. max\n");
printf("0. terminate\n");
printf("\nselect : [ ]\b\b");
scanf("%d", &select);
getchar();
switch(select) {
case ADD:
{
printf("\n정수를 입력하세요 : "); // 밖에서 받아서 입력처리하는 것이 좋음.
scanf("%d", &data);
root = addNode(root, data); // 최종적으로 루트의 주소를 돌려주는 형식으로 진행.
break;
}
case REMOVE:
{
printf("삭제할 정수 입력 : ");
scanf("%d", &data);
root = removeNode(root, data);
break;
}
case SEARCH:
{
printf("검색할 정수 입력 : ");
scanf("%d", &data);
getchar();
find = searchNode(root, data);
if (find == NULL) {
printf("해당한 값이 존재하지 않습니다.\n");
getchar();
}
else {
printf("%d값이 있습니다.\n", find->value);
getchar();
}
break;
}
case PRINT:
{
_print(root);
puts("");
getchar();
break;
}
case MIN:
{
find = findMin(root);
if (find == NULL) {
printf("tree가 구성되지 않았습니다.\n"); // tree가 구성되지 않았을 경우 NULL이 반환되므로.
}
else {
printf("\n최솟값은 %d입니다.\n", find->value);
}
getchar();
break;
}
case MAX:
{
find = findMax(root);
if (find == NULL) {
printf("tree가 구성되지 않았습니다.\n"); // tree가 구성되지 않았을 경우 NULL이 반환되므로.
}
else {
printf("\n최댓값은 %d입니다.\n", find->value);
}
getchar();
break;
}
case TERMINATE:
{
terminate(root);
exit(0);
break;
}
}
}
return 0;
}
treeNode* addNode(treeNode* t, int data) {
if (t == NULL) {
t = (treeNode*)malloc(sizeof(treeNode));
t->value = data;
t->left = NULL;
t->right = NULL;
}
else if (t->value == data) {
printf("\n\n\t\t이미 등록된 data입니다.\n");
}
else if (t->value < data) {
t->right = addNode(t->right, data); // data값이 현재 노드의 값보다 큰 경우
}
else if (t->value > data) {
t->left = addNode(t->left, data); // data값이 현재 노드의 값보다 작은 경우
}
return t;
}
void _print(treeNode* t) { // 중위순회로 보이기
if (t != NULL) {
_print(t->left);
printf("%d ", t->value);
_print(t->right);
}
return;
}
void terminate(treeNode* t) { // 후위순회로 제거하기
if (t != NULL) {
terminate(t->left);
terminate(t->right);
printf("%d를 삭제합니다.\n", t->value);
free(t);
}
return;
}
treeNode* findMin(treeNode* t) {
if (t->left != NULL) {
while(t->left != NULL) {
t = t->left;
}
}
return t;
}
treeNode* findMax(treeNode* t) {
if (t->right != NULL) {
while(t->right != NULL) {
t = t->right;
}
}
return t;
}
treeNode* removeNode(treeNode* t, int data) {
treeNode* temp;
if (t != NULL) {
if (data == t->value) {
// 삭제
// case 1. 자식이 없는 경우
if (t->left == NULL && t->right == NULL) {
free(t);
return NULL;
}
else { // 자식이 있는 경우
// case 2. 자식이 1개인 경우
if (t->right == NULL) { // case 2-1. 자식이 왼쪽만 있는 경우
temp = t->left; // 왼쪽 자식의 주소 저장
free(t); //삭제
return temp; // 왼쪽 자식 값 리턴. -> 이 과정에서 부모노드의 왼쪽 자식으로 자동으로 연결 됨.
}
if (t->left == NULL) { // case 2-1. 자식이 오른쪽만 있는 경우
temp = t->right; // 오른쪽 자식의 주소 저장
free(t); //삭제
return temp; // 오른쪽 자식 값 리턴. -> 이 과정에서 부모노드의 오른쪽 자식으로 자동으로 연결 됨.
}
// case 3. 자식이 둘다 있는 경우
if (t->left != NULL && t->right != NULL) {
temp = findMax(t->left); // left 중에서 최댓값으로 값을 정렬이 완료됨.
// 혹은 right 중에서 최댓값으로 지정해주어도 된다.
t->value = temp->value;
// 왼쪽 자식 중 최댓값을 가진 노드의 value 값을 지금 자리에 넣어준다.
t->left = removeNode(t->left, temp->value);
// 그리고 temp를 삭제 시키면 된다. 이때, 재귀호출 방식을 이용한다.
// 출발지점은 t->left, 타겟은 temp->value
// 원래 자리에 temp Node를 넣었으니 원래 temp Node 자리에 있던 Node는 삭제시켜야한다.
}
}
}
else {
// 왼쪽, 오른쪽으로 재귀호출
if(t->value > data) {
t->left = removeNode(t->left, data); // 왼쪽으로 이동
}
else {
t->right = removeNode(t->right, data); // 오른쪽으로 이동
}
}
}
return t;
}
treeNode* searchNode(treeNode* t, int data) {
if (t != NULL) {
if (t->value == data) {
// 일치한 값을 발견하면 반환
return t;
}
else {
if (t->value < data) {
// 찾으려는 값이 현재 값보다 더 크면 오른쪽 자식으로 순회
return searchNode(t->right, data);
}
else { // 찾으려는 값이 현재 값보다 더 작으면 왼쪽 자식으로 순회
return searchNode(t->left, data);
}
}
}
}
