指向以我不希望的方式超出范围的指针

Question

我有一个函数可以在二叉搜索树中查找指定节点以及该节点的前一个节点：

bool collection::removeFromTree(const char name[])
{
    treeNode ** prev = nullptr;
    for (treeNode ** curr = &root; *curr;)
    {
        int8_t result = strcmp(name, (*curr)->item->getName());
        if (result == 0)
        {
            deleteNode(prev, curr);
            return true;
        }
        else if (result < 0)
        {
            prev = curr;
            curr = &((*curr)->left);
        }
        else if (result > 0)
        {
            prev = curr;
            curr = &((*curr)->right);
        }
    }
    return false;
}

我遇到的问题不是这个函数，而是我的 deleteNode() 函数。我无法将我以前的节点指定为指向我当前节点（或我计划删除的节点）之后的节点。这是我的 deleteNode() 函数的重要部分：

void collection::deleteNode(treeNode **& prevNode, treeNode **& goneNode)
{
    //irrelevant code
    //if it has right child
    if (!(*goneNode)->left)
    {
        treeNode * temp = (*goneNode)->right;
        (*goneNode)->right = nullptr;
        delete *goneNode;
        (*prevNode)->right = temp;
        *goneNode = nullptr;
    }
    //irrelevant code
}

问题当然是这个函数运行后(*prevNode)->right变成了null。指向指针的指针超出范围，数据丢失。 goneNode 右侧的任何节点都超出范围。有什么好的方法可以解决这个问题吗？

我也试过：

void collection::deleteNode(treeNode **& prevNode, treeNode **& goneNode)
{
    //irrelevant code
    //if it has right child
    if (!(*goneNode)->left)
    {
        (*prevNode)->right = (*goneNode)->right;
        (*goneNode)->right = nullptr;
        delete *goneNode;
        *goneNode = nullptr;
    }
    //irrelevant code
}

当我这样做时，(*prevNode)->right 在 delete *goneNode; 之后立即变为 null（甚至在函数完成执行之前）。

Answer 1

这里使用双星指针的好处是避免使用 current 和 previous 指针。有了一个指向节点指针的 指针，我们可以编辑将该节点绑定到树中的 link 。前一个节点的其余部分无关紧要；我们只关心指向我称之为 bad_node（要删除的那个）的指针。

(*prevNode)->right = (*goneNode)->right; //50% chance that (*prevNode)->right was (*goneNode)

或者 bad_node 在 prevNode 的右边，我们擦除 bad_node 的位置，或者它在左边，我们毁坏了树。我敢打赌第一个场景正在发生。一旦该行执行，*goneNode 将是错误的值，因此它最终会泄漏 goneNode 并删除其子项。

至：

else if (!(*goneNode)->left) //one child on right { treeNode* temp = *goneNode; //store address of bad_node *goneNode = (*goneNode)->right; //replace bad_node with child temp->right = nullptr; //bad_node now has no children delete temp; //delete bad_node }

要记住的重要一点是 *goneNode 是指向树 中 bad_node 的指针。分配给 *goneNode 会改变树的结构。

指向以我不希望的方式超出范围的指针

Pointer to pointer going out of scope in a way that I don't want it to

c++

pointers

binary-search-tree