Lab06 Binary Search Tree 코드

 

printInoder 함수의 경우, 트리 전체를 inorder로 순회하며 출력해야 한다.

 

전체 코드

#define _CRT_SECURE_NO_WARNINGS

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

int node_count = 0; // 노드의 개수들을 저장하는 변수. printInorder 함수의 원활한 실행(마지막 숫자를 출력한 이후 공백 없이 줄바꿈)을 위해 선언함
int i = 0; // printInorder 함수에서 마지막 숫자를 출력한 이후 공백 없이 줄바꿈을 하기 위한 변수

typedef struct BST* Tree;

typedef struct BST {
    int value;
    struct BST* left;
    struct BST* right;
}BST;

Tree insertNode(Tree root, int key);
Tree deleteNode(Tree root, int key);
int findNode(Tree root, int key);
void printInorder(Tree root);
void deleteTree(Tree root);
Tree FindMin(Tree root); // 노드를 delete할 때, 그 노드가 두 개의 자식 노드를 가지고 있는 경우 그 노드의 오른쪽 트리에서 제일 작은 수가 저장되어 있는 노드를 찾기 위한 함수

Tree insertNode(Tree root, int key) { // 노드를 새로 insert하는 함수
    Tree parent_node = NULL;
    Tree new_node = NULL;
    Tree current_node = root;

    // 새로운 노드가 insert될 위치를 찾는다.
    while (current_node != NULL) {
        if (key == current_node->value) {
            printf("insertion error: %d is already in the tree\n", key);
            return current_node;
        } // key값이 이미 트리 안에 존재한다면 에러메시지를 띄우고 함수를 빠져나옴.

        parent_node = current_node;

        if (key < current_node->value)
            current_node = current_node->left; // 넣고자 하는 key값이 current_node의 값보다 작다면 current_node는 자신의 왼쪽 자식이 되도록 설정 
        else
            current_node = current_node->right; // 넣고자 하는 key값이 current_node의 값보다 크다면 current_node는 자신의 오른쪽 자식이 되도록 설정
    }

    // 새 노드를 생성하고 정보 초기화
    new_node = (Tree)malloc(sizeof(BST));
    new_node->left = new_node->right = NULL;
    new_node->value = key;

    if (parent_node == NULL) { // 새로운 노드가 맨 처음 루트 노드일 때
        root = new_node;
    }
    else { // 새로운 노드가 맨 처음 루트 노드가 아닐 때는...
        if (key < parent_node->value) { // 넣고자 하는 key값이 parent_node의 값보다 작을 때
            parent_node->left = new_node; // 새로운 노드가 parent_node의 왼쪽 자식이 되도록 설정
        }
        else { // 넣고자 하는 key값이 parent_node의 값보다 클 때
            parent_node->right = new_node; // 새 노드가 parent_node의 오른쪽 자식이 되도록 설정
        }
    }

    printf("insert %d\n", key);
    node_count++;
    return root;
}

Tree deleteNode(Tree root, int key) { // 노드를 delete하는 함수
    Tree tmp;

    Tree current_node = root;

    if (key < current_node->value) { // 삭제하고자 하는 key값이 current_node의 값보다 작다면,
        current_node->left = deleteNode(current_node->left, key); // current_node의 왼쪽 자식으로 하여금 다시 deleteNode 함수를 실행
    }
    else if (key > current_node->value) { // 삭제하고자 하는 key값이 current_node의 값보다 크다면,
        current_node->right = deleteNode(current_node->right, key); // current_node의 오른쪽 자식으로 하여금 다시 deleteNode 함수를 실행
    }

    /* 이 밑의 else if문과 else문은, 이제 key값이 들어있는 노드를 찾았을 때 */

    else if (current_node->left && current_node->right) { // current_node가 2개의 자식 노드가 있다면,
        tmp = FindMin(current_node->right); // tmp 노드가 cuurrent_node의 오른쪽 subtree에서 가장 작은 값을 가지는 노드를 가리키게 하고
        current_node->value = tmp->value; // current_node를, 가장 작은 값을 가지는 노드로 교체한 후
        current_node->right = deleteNode(current_node->right, current_node->value); // current_node의 오른쪽 subtree에서, 교체한 노드를 찾아 삭제
    }
    else { // current_node의 자식 노드가 1개 또는 0개라면,
        tmp = current_node; // tmp 노드가 current_node를 가리키게 하고
        if (current_node->left == NULL && current_node->right != NULL) { // current_node가 오른쪽 자식만 있다면,
            current_node = current_node->right; // current_node는 자신의 오른쪽 자식이 되게 함
        }
        else if (current_node->left == NULL && current_node->right == NULL) { // current_node가 자식이 0개라면,
            current_node = NULL;
        } // current_node가 삭제되어야 할 바로 그 노드이므로 current_node는 NULL로 설정해야 한다.
          // 왜냐하면 어차피 tmp가 current_node를 가리키도록 위에서 설정했고 삭제하는 건 free(tmp)로 하기 때문이다.
          // 그리고 이렇게 안 하면 맨 밑의 return current_node; 에서 current_node가 쓰레기 값이 되어 버린다. (free(tmp) 때문)

        else { // current_node가 왼쪽 자식만 있다면,
            current_node = current_node->left; // current_node는 자신의 왼쪽 자식이 되게 함
        }

        free(tmp); // 삭제하고자 하는 노드를 삭제.
    }
    return current_node;
}

int findNode(Tree root, int key) {
    Tree tmp = root; // tmp 노드를 따로 만들어 맨 처음 root 노드를 가리키게 함

    while (tmp != NULL) {
        if (key == tmp->value) {
            return 1; // key값이 저장된 노드를 찾았다면 true값인 1 반환
        }
        else if (key < tmp->value) {
            tmp = tmp->left; // key값이 tmp노드의 value값보다 작다면 tmp노드는 자신의 왼쪽 자식을 가리키게 함
        }
        else {
            tmp = tmp->right; // key값이 tmp노드의 value값보다 크다면 tmp노드는 자신의 오른쪽 자식을 가리키게 함
        }
    }
    return 0; // key값이 저장된 노드를 찾지 못했다면 false값인 0 반환
}

void printInorder(Tree root) {
    if (root == NULL)
        return; // 인자로 전달받은 노드가 NULL이라면 함수 탈출

    printInorder(root->left); // 왼쪽 서브 트리 출력
    i++; // 노드 하나의 value값을 출력할 때마다 i값을 1씩 증가시킴 (마지막 숫자 출력 후 공백을 없게 하기 위해)
    if (i != node_count)
        printf("%d ", root->value); // 인자로 전달받은 노드 방문 (변수 i의 값이 노드들의 전체 개수와 다르다면 숫자 사이에 공백을 넣어 출력)
    else
        printf("%d", root->value); // 인자로 전달받은 노드 방문 (변수 i의 값이 노드들의 전체 개수와 같다면 공백 없이 마지막 숫자 출력)
    printInorder(root->right); // 오른쪽 서브 트리 출력
}

void deleteTree(Tree root) {
    if (root == NULL)
        return;

    deleteTree(root->left);
    deleteTree(root->right);
    free(root);
    // 노드들의 삭제는 후위 순회로 진행해야
}

Tree FindMin(Tree root) {
    if (root == NULL)
        return NULL;
    if (root->left == NULL) // 인자로 전달받은 노드의 왼쪽 자식이 NULL이라면,
        return root; // 인자로 전달받은 노드가 제일 작은 값을 가지는 노드인 것이므로 인자로 받은 노드 그대로 다시 리턴
    else // 인자로 전달받은 노드의 왼쪽 자식이 NULL이 아니라면,
        return FindMin(root->left); // 더 작은 값을 가지는 노드가 있는 것이므로
                                    // 인자로 받은 노드의 왼쪽 자식을 인자로 넘겨주어 FindMin 함수 다시 실행
}

int main(void) {
    char cv;
    int key;

    Tree root = NULL;

    while (1) {
        scanf("%c", &cv);
        switch (cv) {
        case 'i':
            scanf("%d", &key);
            root = insertNode(root, key);
            break;
        case 'f':
            scanf("%d", &key);
            if (findNode(root, key))
                printf("%d is in the tree\n", key);
            else
                printf("finding error: %d is not in the tree\n", key);
            break;
        case 'd':
            scanf("%d", &key);
            if (findNode(root, key)) {
                root = deleteNode(root, key);
                node_count--; // 노드 하나를 삭제했으므로 전체 노드의 개수가 담겨있는 변수 node_count의 값을 1 줄임
                printf("delete %d\n", key);
            }
            else {
                printf("deletion error: %d is not in the tree\n", key);
            }
            break;
        case 'p':
            scanf("%c", &cv);
            if (cv == 'i') {
                if (root == NULL)
                    printf("tree is empty");
                else {
                    printInorder(root);
                    i = 0; // 중위 순회 출력을 다 마쳤으므로 i값을 다시 0으로 초기화
                }
            }
            printf("\n");
            break;
        case 'q':
            return 0;
        }
    }
    deleteTree(root);
}