이진 검색트리 삭제 구현시 발생한 문제입니다.

delete_node 함수에서

if (leaf->left == NULL && leaf->right == NULL) {
            delete leaf;
            leaf = NULL;
        }

이 부분에서 leaf를 delete하고 NULL을 넣었는데, 디버깅을 해보니 이때, NULL값이 아닌 쓰레기 값을 가지고 있어 오류가 발생합니다.

이부분에서 어떻게 고쳐야 하는지 가르쳐주시면 감사하겠습니다...ㅠㅠ

소스코드)

#include <iostream>

using namespace std;


struct node {
    int value;
    node *left;
    node *right;
};

class btree {
public:
    btree();
    ~btree();

    void insert(int key);
    void destroy_tree();
    void delete_node(int key);
    void preorder_print();


private:
    void destroy_tree(node *leaf);
    void insert(int key, node *leaf);
    void delete_node(int key, node* leaf);
    node* findMin(node* root);
    void preorder_print(node *leaf);

    node *root;
};


btree::btree() {
    root = NULL;
}

btree::~btree() {
    destroy_tree();
}

void btree::destroy_tree(node *leaf) {
    if (leaf != NULL) {
        destroy_tree(leaf->left);
        destroy_tree(leaf->right);
        delete leaf;
    }
}

void btree::insert(int key, node *leaf) {

    if (key < leaf->value) {
        if (leaf->left != NULL) {
            insert(key, leaf->left);
        }
        else {
            leaf->left = new node;
            leaf->left->value = key;
            leaf->left->left = NULL;
            leaf->left->right = NULL;
        }
    }
    else if (key >= leaf->value) {
        if (leaf->right != NULL) {
            insert(key, leaf->right);
        }
        else {
            leaf->right = new node;
            leaf->right->value = key;
            leaf->right->right = NULL;
            leaf->right->left = NULL;
        }
    }

}

void btree::insert(int key) {
    if (root != NULL) {
        insert(key, root);
    }
    else {
        root = new node;
        root->value = key;
        root->left = NULL;
        root->right = NULL;
    }
}




void btree::destroy_tree() {
    destroy_tree(root);
}


void btree::delete_node(int n) {
    if (root!=NULL) {
        delete_node(n, this->root);
    }
    else {
        return;
    }
}
node* btree::findMin(node* root) {
    while (root->left != NULL) root = root->left;
    return root; 
}

void btree::delete_node(int n, node* leaf) {

    if (n < leaf->value)
        delete_node(n, leaf->left);
    else if (n > leaf->value)
        delete_node(n, leaf->right);
    else {
        if (leaf->left == NULL && leaf->right == NULL) {
            delete leaf;
            leaf = NULL;
        }
        else if (leaf->left == NULL) {
            node* temp = leaf;
            leaf = leaf->right;
            delete temp;
        }
        else if (leaf->right == NULL) {
            node* temp = leaf;
            leaf = leaf->left;
            delete temp;
        }
        else {
            node* temp = findMin(leaf->right);
            leaf->value = temp->value;
            delete_node(temp->value, leaf->right);
        }
    }
}

void btree::preorder_print() {
    preorder_print(root);
    cout << "\n";
}

void btree::preorder_print(node *leaf) {
    if (leaf != NULL) {
        cout << leaf->value << ",";
        preorder_print(leaf->left);
        preorder_print(leaf->right);
    }
}


int main() {
    int n;
    cin >> n;
    btree *tree = new btree();

    for (int i = 0; i < n; i++) {
        int data;
        cin >> data;
        tree->insert(data);
    }
    tree->preorder_print();

    tree->delete_node(30);
    tree->preorder_print();

    delete tree;

}