0 
// So I call this function after deleting a node.
// It works before I delete the node, but for some reason
// after I perform a deletion and update the tree it runs into
// EXC_BAD_ACCESS on the line below...

void BinaryTree::updateCost(BinaryNode *root) {
    if (root != NULL)
        root->updateCostRecursively(1);
}

void BinaryNode::updateCostRecursively(int newCost) {
    cout << this << endl; // prints 0x3000000000000000 before the bad access
    cost = newCost; // has a bad access here
    if (right != NULL)
        right->updateCostRecursively(newCost + 1);
    if (left != NULL)
        left->updateCostRecursively(newCost + 1);
}

为什么即使我每次都检查指针，也会在 NULL 对象上调用这个递归函数？

我已经复制了用于删除下面节点的代码。我仍然无法理解递归函数，但从无法判断的情况来看，我没有留下一个悬空指针。

BinaryNode *BinaryTree::findMin(BinaryNode *t) {
    if (t == NULL) return NULL;
    while (t->left != NULL) t = t->left;
    return t;
}

BinaryNode *BinaryTree::removeMin(BinaryNode *t) {
    if (t == NULL) return NULL;
    if (t->left != NULL)
        t->left = removeMin(t->left);
    else {
        BinaryNode *node = t;
        t = t->right;
        delete node;
    }
    return t;
}

bool BinaryTree::remove(int key) {
    if (root != NULL && remove(key, root))
        return true;
    return false;
}

BinaryNode *BinaryTree::remove(int x, BinaryNode *t) {
    if (t == NULL) return NULL;

    if (x < t->key)
        t->left = remove(x, t->left);
    else if (x > t->key)
        t->right = remove(x, t->right);
    else if (t->left != NULL && t->right != NULL) {
        // item x is found; t has two children
        t->key = findMin(t->right)->key;
        t->right = removeMin(t->right);
    } else { //t has only one child
        BinaryNode *node = t;       
        t = (t->left != NULL) ? t->left : t->right;
        delete node;
    }

    updateCost(root);
    return t;
}
4

1 回答 1

1

错误出在您的删除方法中，而不是您发布的代码中。删除节点（例如root->right）后，您需要设置root->right = NULL. 您所做的delete只是释放指针指向的内存。指针本身继续指向该地址。由于您试图访问已释放的内存，因此您遇到了错误的访问异常。

于 2013-03-19T22:21:33.880 回答