(C언어) 이진 탐색 트리(BTS, Binary Search Tree)에서 노드의 삽입 삭제 검색

C언어를 이용해서 이진 탐색 트리(BTS, Binary Search Tree)를 구현한 코드입니다.

노드의 생성, 삽입, 삭제 그리고 중위 순회로 탐색하는 코드를 포함하고 있습니다.

 

이진 트리의 노드를 나타내는 구조체입니다.

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

 

노드를 생성하는 함수입니다.

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

 

노드의 삽입, 삭제, 중위 순회하는 코드는 전체 코드에서 확인해 주십시오.

전체 코드는 아래와 같습니다.

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

// 이진 트리의 노드를 나타내는 구조체
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 새 노드를 생성하는 함수
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// BST에 노드를 삽입하는 함수
struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    }
    else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;
}

// BST에서 최소값 노드를 찾는 함수
struct Node* findMinNode(struct Node* node) {
    struct Node* current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

// BST에서 노드를 삭제하는 함수
struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) {
        return root;
    }

    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    }
    else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    }
    else {
        // 하나의 자식이나 자식이 없는 노드의 경우
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // 두 개의 자식을 가지는 노드의 경우
        struct Node* temp = findMinNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// BST를 중위 순회하여 출력하는 함수
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("BST의 중위 순회 결과: ");
    inorder(root);
    printf("\n");

    root = deleteNode(root, 20);
    printf("20을 삭제한 후의 중위 순회 결과: ");
    inorder(root);
    printf("\n");

    return 0;
}

(C언어) 이진 탐색 트리(BTS, Binary Search Tree)에서 노드의 삽입 삭제 검색