카테고리 없음
[C/정렬] 이진탐색트리 구현 binary search tree sort, 이중연결리스트(double linked list) 사용
미친토끼
2021. 2. 28. 07:53
// BTSmain.c
// 이진 탐색 트리 (Double Linked List) 구현
// 참고 유튜브 영상: "초이스 프로그래밍"의 "[자료구조] 이진 탐색 트리 : 개념과 구현(C언어)"
// 참고 영상에서는 삭제 함수가 deleteBST인데, 여기서는 delete하려는 노드 특징에 따라 함수를 다시 모듈화했음.
// 코드 작성: 미친토끼의 가출일기, 2021년 2월
#include <stdio.h>
#include <stdlib.h>
typedef int Data;
typedef struct _Node {
Data data;
struct _Node *left;
struct _Node *right;
} Node;
Node *ROOT = NULL;
Node *makeNode(Data val) {
Node *p = (Node *)malloc(sizeof(Node));
//메모리 할당에 실패했을 경우 에러 처리 필요 -- 이후
p->data = val;
p->left = NULL;
p->right = NULL;
return p;
}
Node *makeRoot(Data val) {
return makeNode(val);
}
Node *searchNode(Node *root, Data val) {
Node *p = root;
while (p != NULL) {
if (p->data == val) {
printf("%d: %p에서 찾았습니다.\n", p->data, p);
return p;
}
else if (p->data < val) {
p = p->right;
}
else {
p = p->left;
}
}
printf("%d: 노드를 찾지 못했습니다.\n", val);
return NULL;
}
Node *insertNode(Node *root, Data val) {
Node *p = root;
Node *parent = NULL; // parent = NULL; 최초 root 구분하려면
while (p != NULL) {
parent = p;
if (p->data == val) {
printf("%d : 같은 값이 이미 있습니다.\n", p->data);
return NULL;
}
else if (p->data < val) {
p = p->right;
}
else {
p = p->left;
}
}
Node *newNode = makeNode(val);
//parent의 자식으로 새 노드 붙이기
if (parent->data > val) {
parent->left = newNode;
}
else {
parent->right = newNode;
}
return root;
}
// 반환값; 실패시 NULL, 성공시 parent 노드 반환
Node *removeEndNode(Node *end, Node * parent) {
if (end == NULL) {
printf("removeEndNode: 유효한 입력 노드가 아닙니다.\n");
return NULL;
}
if (end->left != NULL || end->right != NULL) {
printf("removeEndNode: 입력 노드가 단말 노드가 아닙니다.\n");
return NULL;
}
if (parent->left == end) parent->left = NULL;
else parent->right = NULL;
printf("%d: %p 단말 노드를 삭제합니다.\n", end->data, end);
free(end);
return parent;
}
// 성공시 1 반환, 실패시 0 반환
int removeRootNode(Node *boss, Node *parent) {
// 부모 노드가 있다면
if (parent != NULL) {
printf("removeRootNode: 최상위 ROOT 노드가 아닙니다.\n");
return 0;
}
//자식이 하나 있다면
if (boss->left == NULL || boss->right == NULL) {
ROOT = (boss->left != NULL) ? boss->left : boss->right;
}
//자식이 없는 루트 노드라면 메모리 해제만 함
printf("루트 노드 삭제 함수가 호출되었습니다. %d값 노드를 삭제합니다.\n", boss->data);
free(boss);
return 1;
}
// 자식이 하나인 노드 없애기. 실패 시 NULL, 성공시 parent
Node *removeOneChildNode(Node *one, Node *parent) {
if (parent == NULL) removeRootNode(ROOT, parent);
if (one == NULL) {
printf("removeOneChildNode: 유효한 입력 노드가 아닙니다.\n");
return NULL;
}
if (one->left != NULL && one->right != NULL) {
printf("removeOneChildNode: 입력 노드가 자식 하나 가진 노드가 아닙니다.\n");
return NULL;
}
// 자식 노드 구하기 & 조부와 손자 연결시키기
Node *child = (one->left != NULL) ? one->left : one->right;
if (parent->left == one)
parent->left = child;
else
parent->right = child;
printf("%d: %p 자식 하나 노드를 삭제합니다.\n", one->data, one);
free(one);
return parent;
}
// 자식 둘 있는 중간 노드 삭제.
// head: 삭제할 노드: 반환값: head
// 삭제할 노드 왼쪽에서 최대값을 찾는 방식
Node *removeTwoChildNode(Node *head) {
Node *parent = head;
Node *p = head->left;
while (p->right != NULL) {
parent = p;
p = p->right;
}
printf("%d: %p: 왼쪽에서 최대값 찾는 방식: 자식 둘 가진 노드를 삭제합니다.\n", head->data, head);
head->data = p->data;
if (parent->right == p) parent->right = NULL;
else parent->left = NULL;
free(p);
return head;
}
// 삭제할 노드 오른쪽에서 최소값을 찾는 방식
Node *removeTwoChildNode2(Node *head) {
Node *parent = head;
Node *p = head->right;
while (p->left != NULL) {
parent = p;
p = p->left;
}
printf("%d: %p: 오른쪽에서 최소값 찾는 방식: 자식 둘 가진 노드를 삭제합니다.\n", head->data, head);
head->data = p->data;
if (parent->right == p) parent->right = NULL;
else parent->left = NULL;
free(p);
return head;
}
Node *removeNode(Node *root, Data val) {
Node *p = root;
Node *parent = NULL;
while (p != NULL && p->data != val) { //끝까지 간 것도 아니고 값을 아직 찾는 중이라면...
parent = p;
if (p->data < val)
p = p->right;
else
p = p->left;
}
// 못 찾았다면
if (p == NULL) {
printf("해당 노드를 찾지 못했습니다.\n");
return root;
}
if (p->left == NULL && p->right == NULL) { // 자식 노드가 없는 경우
//root 노드인 경우
if (parent == NULL && removeRootNode(ROOT, parent) == 0) return NULL;
//단말 노드인 경우
else if (removeEndNode(p, parent) == NULL) return NULL;
}
else if (p->left == NULL || p->right == NULL) { // 자식 노드가 1개인 경우.
if (removeOneChildNode(p, parent) == NULL) return NULL;
}
// 자식 노드가 둘인 경우
else if (removeTwoChildNode2(p) == NULL) return NULL;
return root;
}
void inOrder(Node *root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
// 최초의 루트 노드 생성
ROOT = makeRoot(9);
int value[] = { 4, 2, 7, 6, 8, 15, 17, 16, 18 };
// 파이썬에서 np.random.randint(1,1000, 50) 으로 발생시킨 난수 50개
/*int value[] = { 358, 287, 953, 833, 864, 857, 706, 40, 181, 62, 221, 174, 837,
204, 911, 154, 50, 300, 59, 628, 272, 237, 247, 726, 27, 185,
691, 223, 894, 941, 684, 521, 929, 234, 758, 377, 368, 787, 290,
37, 499, 471, 447, 903, 846, 799, 182, 820, 305, 694 }; */
for (int i = 0; i < sizeof(value) / sizeof(int); i++) {
insertNode(ROOT, value[i]);
}
inOrder(ROOT);
printf("\n");
searchNode(ROOT, 15);
searchNode(ROOT, 14);
removeNode(ROOT, 2);
removeNode(ROOT, 7);
removeNode(ROOT, 16);
inOrder(ROOT);
printf("\n");
if (ROOT == NULL)
printf("노드가 하나도 없습니다.\n");
return 0;
}
----------------
출력결과
2 4 6 7 8 9 15 16 17 18
15: 0x405360에서 찾았습니다.
14: 노드를 찾지 못했습니다.
2: 0x4052e0 단말 노드를 삭제합니다.
7: 0x405300: 오른쪽에서 최소값 찾는 방식: 자식 둘 가진 노드를 삭제합니다.
16: 0x4053a0 단말 노드를 삭제합니다.
4 6 8 9 15 17 18