[DAY 06] Binary Search Tree

Program

/*
    Tree1.c
*/
 
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int            key;
    int            data;
    struct Node *left;
    struct Node *right;
} Node;
 
//int GetData(Node *head, int key, int *data);
int GetData(Node *head, int *key);
int Insert(Node *head, int key, int data);
int Delete(Node *head, int key);
int Display(Node *head);
void PreorderTraversal(Node *root);
void InorderTraversal(Node *root);
void PostorderTraversal(Node *root);
 
void main()
{
    Node *head = (Node *)malloc(sizeof(Node));
    int key = 0;
    int data = 0;
    head->left = NULL;
    head->right = NULL;
 
    int button;
    char sayYesOrNo;
    
    do {
        puts("========== MENU ==========");
        puts("1. Get data");
        puts("2. Insert node");
        puts("3. Delete node");
        puts("4. Show all nodes");
        puts("5. Exit");
        puts("==========================");
        printf("Select what you want to do : ");
        scanf("%d", &button);
 
        switch (button)
        {
        case 1:    // Get data
            printf("Input key : ");
            scanf("%d", &key);
            GetData(head, &key);
            break;
        case 2:    // Insert node
            printf("Input key : ");
            scanf("%d", &key);
 
            if (Insert(head, key, data) == 0) {
                puts("Error!");
                break;
            }
            puts("complete!");
            break;
        case 3:    // Delete node
            printf("Input key : ");
            scanf("%d", &key);
            Delete(head, key);
            break;
        case 4:    // Show all nodes
            Display(head);
            break;
        }
 
        printf("계속하시겠습니까?(Y/N) : ");
        rewind(stdin);
        scanf("%c", &sayYesOrNo);
    } while (sayYesOrNo == 'Y' || sayYesOrNo == 'y');
}
 
int GetData(Node *head, int *key)
{
    Node *root;
    Node *cur;
 
    // 더미 노드에 연결된 루트 노드 설정
    if (head->left == NULL) {
        puts("노드가 1도 없습니다.");
        return 0;
    } else {
        root = head->left;
        cur = root;
        while (1) {
            if ((*key) == cur->key) {
                puts("오 찾았다");
                printf("찾은 키 값 : %d \n", *key);
                return 1;
            } else {
                // 탐색
                if ((*key) < cur->key) {
                    cur = cur->left;
                    continue;
                } else {
                    cur = cur->right;
                    continue;
                }
            }
        }    // end of loop
    }
}
 
int Insert(Node *head, int key, int data)
{
    Node *root;
    Node *cur;
    Node *new1;
    
    // 새로운 노드 생성
    if ((new1 = cur = (Node *)calloc(1, sizeof(Node))) == NULL) {
        puts("failed to memory allocation!");
        exit(-1);
    }
    new1->key = key;
    new1->data = data;
    new1->left = NULL;
    new1->right = NULL;
        
    // 첫 노드는 탐색할 필요가 없으므로 바로 루트 노드로 선정
    if (head->left == NULL) {
        puts("첫 노드를 생성했습니다.");
        head->left = new1;
        return 1;
    } else {
        // 최소한 1개 이상 노드가 있는 경우 탐색 진행            
        root = head->left;
        cur = root;
        while (1) {
            if (key == cur->key) {
                puts("중복된 데이터가 존재합니다!");
                return 0;
            } else if (new1->key < cur->key) {
                if (cur->left == NULL) {
                    break;
                }
                cur = cur->left;
            } else {
                if (cur->right == NULL) {
                    break;
                }
                cur = cur->right;
            }
        }    // end of while loop
    }
 
    // 왼쪽에 붙일 지 오른쪽에 붙일 지 결정
    if (new1->key < cur->key) {
        cur->left = new1;
    } else {
        cur->right = new1;
    }
 
    puts("노드 추가 완료!");
    return 1;
}
 
int Delete(Node *head, int delkey)
{
    Node *root = head->left;
    Node *cur, *del, *fix, *lboss, *rboss = NULL;
 
    cur = root;
    //    printf("root key : %d \n", cur->key);
 
    if (delkey == cur->key) {
        puts("루드에있네");
        del = cur;
        head->left = NULL;
    } else {
        // 삭제 전 노드 위치 탐색
        while (1) {
            if ((cur->left != NULL && delkey == cur->left->key) ||
                (cur->right != NULL && delkey == cur->right->key)) {
                puts("유레카");
                break;
            } else if (delkey < cur->key) {
                if (cur->left == NULL) {
                    puts("찾는 키 값 없음");
                    return 0;
                }
                cur = cur->left;
            } else {
                if (cur->right == NULL) {
                    puts("찾는 키 값 없음");
                    return 0;
                }
                cur = cur->right;
            }
        }
 
        // del 포인터 갖다 놓기
        if (delkey < cur->key) {
            del = cur->left;
        }
        else {
            del = cur->right;
        }
 
        // 자식 노드가 0개인 경우
        if (del->left == NULL && del->right == NULL) {
            if (delkey < cur->key) {
                cur->left = NULL;
            } else {
                cur->right = NULL;
            }
        } else if (del->left != NULL || del->right != NULL) {
            // 자식 노드가 1개인 경우
            fix = del;
            if (del->left == NULL) {
                del = del->right;
                fix->key = del->key;
                fix->right = NULL;
            } else {
                del = del->left;
                fix->key = del->key;
                fix->left = NULL;
            }
        } else {
            // 자식 노드가 2개인 경우
            lboss = del->left;
            rboss = del->right;
 
            while (1) {
                if (lboss->right == NULL) {
                    break;
                }
                lboss = lboss->right;
            }
 
            while (1) {
                if (rboss->left == NULL) {
                    break;
                }
                rboss = rboss->left;
            }
 
            if (abs((lboss->key) - (root->key)) < abs((rboss->key) - (root->key))) {
                // 왼쪽 leaf node를 del node로 옮긴다
                del->key = lboss->key;
                fix = del;
                del = del->left;
                fix->left = NULL;
            } else {
                // 오른쪽 leaf node를 del node로 옮긴다
                del->key = rboss->key;
                fix = del;
                del = del->right;
                fix->right = NULL;
            }
        }
    }
    
    free(del);
    puts("삭제 완료");
    return 1;
}
 
int Display(Node *head)
{
    Node *root;
 
    if (head->left == NULL) {
        puts("노드가 1도 없습니다.");
        return 0;
    }
 
    root = head->left;
 
    // preorder traversal
    puts("preorder traversal :");
    PreorderTraversal(root);
    puts("");
 
    // inorder traversal
    puts("inorder traversal :");
    InorderTraversal(root);
    puts("");
 
    // postorder traversal
    puts("postorder traversal :");
    PostorderTraversal(root);
    puts("");
 
    return 1;
}
 
void PreorderTraversal(Node *cur)
{
    if (cur == NULL) return;
    printf("%d ", cur->key);
    PreorderTraversal(cur->left);
    PreorderTraversal(cur->right);
}
 
void InorderTraversal(Node *cur)
{
    if (cur == NULL) return;
    InorderTraversal(cur->left);
    printf("%d ", cur->key);
    InorderTraversal(cur->right);
}
 
void PostorderTraversal(Node *cur)
{
    if (cur == NULL) return;
    PostorderTraversal(cur->left);
    PostorderTraversal(cur->right);
    printf("%d ", cur->key);
}

good

_Insert 함수 : 재귀호출(Pointer to pointer) 했다

포인터의 포인터를 쓰는 게 좋다 -> why? 코드가 깔끔하게 눈에 들어온다

_Search 함수

return NULL; // 예외처리한거

_FindLeft : 왼쪽 찾는거; _FindRight : 오른쪽 찾는거

Search 함수를 갖고 오면 _Search로 내 식대로 쓰겠다

cf. 함수를 사용하는 이유? 재사용하려고!

왜 안될까? 고민하면서 디버깅하는 습관은 아주 좋다!

최적화와 빠른 속도를 염두에 두면 좋다

debug: breaking point

F5, F9, F10,. F11

F5 : 디버깅 모드로 들어간다.

Ctrl + F5 : release mode(디버깅 하지 않고 실행하겠다).

F9 : Break point? breaking point?

F10 : 한 줄씩 디버깅을 진행하고 싶다 (현재 내가 속해 있는 함수 내에서만 실행)

F11 : 함수 호출일 때 거기로 넘어가겠다.

Shift + F5 : 디버깅 모드 해제