Дерево вставки / удаления / печати сбоев

Question

Я пытаюсь реализовать дерево из файла hpp, и у меня, похоже, возникают проблемы с функцией удаления.Логика, которой я придерживаюсь, имеет смысл, однако я не могу понять, почему происходит сбой при печати чего-либо после удаления объекта.

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

void Tree::print() const {
    printinOrder(root);
}

void Tree::printinOrder(Tree::Node* root) const {
    if (root == NULL) return;
    printinOrder(root->left);
    cout<<root->val<<",";
    printinOrder(root->right);
}

Tree::Node::Node(DataType value) {
    left = NULL;
    right = NULL;
    val = value;
}

bool Tree::tree_ins(Tree::Node* node, Tree::Node* insert_node) {
    if (node-> val == insert_node->val) return false;
    if (insert_node->val > node->val && node-> right == NULL) {
        node->right = insert_node;
        return true;
    }
    if (insert_node->val < node->val && node-> left == NULL) {
        node->left = insert_node;
        return true;
    }
    if (insert_node->val > node->val) return tree_ins(node->right, insert_node);
    if (insert_node->val < node->val) return tree_ins(node->left, insert_node);
}

bool Tree::insert(int val) {
    if (root == NULL) {
        root = new Node(val);
        return true;
    }
    Node* insert_node = new Node(val);
    return tree_ins (root, insert_node);
}

Tree::Node* Tree::getMinValue(Tree::Node* node) {
    if (node->left == NULL) {
        return node;
    }
    return getMinValue(node->left);
}

bool Tree::tree_rem(Tree::Node* test_node, int value) {
    if (test_node == NULL) return false;
    else if (value < test_node-> val) tree_rem (test_node-> left, value);
    else if (value > test_node-> val) tree_rem (test_node-> right, value);
    else {
        if (test_node-> left==NULL && test_node->right == NULL) {
            delete (test_node);
            return true;
        }
        else if (test_node-> left==NULL) {
            test_node->val = (test_node->right)->val;
            test_node = test_node ->right;
            test_node=NULL;
            return true;
        }
        else if (test_node-> right==NULL) {
            test_node->val = (test_node->left)->val;
            test_node = test_node ->left;
            test_node=NULL;
            return true;
        } else {
            Node* minNode = getMinValue(test_node->right);
            test_node->val = minNode->val;
            tree_rem(test_node->right, minNode->val);
            return true;
        }
    }
}

bool Tree::remove(int val) {
    if (root == NULL) {
        return false;
    }
    Node* temp = root;
    return tree_rem (temp, val);
}

Вставка работает, печать на дереве работает.Я заметил, что после удаления объекта при печати дерево вылетает из программы, однако, если я вставляю что-то сразу после удаления объекта, а затем печатаю дерево, оно не вылетает (но вставляет его в неправильное место)

Если я запускаю его в такой последовательности, он вылетает:

bst->insert(5);
bst->insert(3);
bst->insert(7);
bst->remove(7);
bst->print();

Answer 1

Если вы измените значение указателя, оно должно быть передано по ссылке, поэтому:

bool Tree::tree_rem(Tree::Node*& test_node, int value)

В вашем коде все действия с указателем test_node имеют эффект только внутри функции, с которой вы работаетекопия test_node, поэтому test_node = test_node->right; действительно ничего не делает с переданным аргументом.

Кроме того, вам нужно установить test_node указатель на NULL после удаления.

 if (test_node->left == NULL && test_node->right == NULL) {
            delete (test_node);
            test_node = NULL;
            return true;
         }