C++로 이진 탐색 트리 구현하기

#include <iostream>

struct BSTNode {
    int key;
    BSTNode *left;
    BSTNode *right;

    BSTNode(int value) : key(value), left(nullptr), right(nullptr) {}
};

void insertNode(BSTNode **node, int value);
BSTNode* removeNode(BSTNode *root, int value);
void inorderTraversal(BSTNode *node);
void removeAll(BSTNode **node);

int main() {
    BSTNode *root = nullptr;

    insertNode(&root, 50);
    insertNode(&root, 30);
    insertNode(&root, 20);
    insertNode(&root, 40);
    insertNode(&root, 70);
    insertNode(&root, 60);
    insertNode(&root, 80);

    std::cout << "Inorder Traversal Result: ";
    inorderTraversal(root);
    std::cout << std::endl;

    root = removeNode(root, 20);
    std::cout << "After deleting 20: ";
    inorderTraversal(root);
    std::cout << std::endl;

    root = removeNode(root, 30);
    std::cout << "After deleting 30: ";
    inorderTraversal(root);
    std::cout << std::endl;

    root = removeNode(root, 50);
    std::cout << "After deleting 50: ";
    inorderTraversal(root);
    std::cout << std::endl;

    removeAll(&root);

    return 0;
}

void insertNode(BSTNode **node, int value) {
    if (*node == nullptr) {
        *node = new BSTNode(value);
    } else {
        if (value < (*node)->key) 
            insertNode(&((*node)->left), value);
        else if (value > (*node)->key) 
            insertNode(&((*node)->right), value);
    }
}

BSTNode* removeNode(BSTNode *root, int value) {
    if (root == nullptr) return nullptr;

    if (value < root->key) 
        root->left = removeNode(root->left, value);
    else if (value > root->key) 
        root->right = removeNode(root->right, value);
    else {
        // 1. 리프 노드를 제거하는 경우
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // 2. 자식이 1개 있는 노드를 제거하는 경우
        else if (root->left != nullptr && root->right == nullptr) {
            BSTNode *tmp = root->left;
            delete root;
            return tmp;
        }
        else if (root->left == nullptr && root->right != nullptr) {
            BSTNode *tmp = root->right;
            delete root;
            return tmp;
        }
        // 3. 자식이 2개 있는 노드를 제거하는 경우
        else {
            BSTNode* predecessor = root->left;
            while (predecessor->right != nullptr) 
                predecessor = predecessor->right;
            root->key = predecessor->key;
            root->left = removeNode(root->left, predecessor->key);
        }
    }
    return root;
}

void inorderTraversal(BSTNode *node) {
    if (node != nullptr) {
        inorderTraversal(node->left);
        std::cout << node->key << " ";
        inorderTraversal(node->right);
    }
}

void removeAll(BSTNode **node) {
    if (*node != nullptr) {
        removeAll(&((*node)->left));
        removeAll(&((*node)->right));
        delete *node;
        *node = nullptr;
    }
}

코드 실행 결과