首页 文章

树插入/删除/打印崩溃

提问于
浏览
-2

我正在尝试从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();

1 回答

  • 3

    如果更改指针值,则必须通过引用传递,因此:

    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;
             }
    

相关问题