c++ - 列出所有函数仍在尝试检索我从二叉搜索树中删除的节点

Question

我有这些函数可以从我的二叉搜索树中删除一个节点:

bool collection::removeFromTree(const char name[])
{
    for (treeNode * curr = root; curr;)
    {
        int8_t result = strcmp(name, curr->item->getName());
        if (result == 0)
        {
            deleteNode(curr);
            return true;
        }
        else if (result < 0)
            curr = curr->left;
        else if (result > 0)
            curr = curr->right;
    }
    return false;
}
void collection::deleteNode(treeNode *& goneNode)
{
    //if it's a leaf
    if (!goneNode->left && !goneNode->right)
    {
        delete goneNode; //node's destructor gets invoked
        goneNode = nullptr;
    }
    //if it has right child
    else if (!goneNode->left)
    {
        goneNode = goneNode->right;
    }
    //if it has left child
    else if (!goneNode->right)
    {
        goneNode = goneNode->left;
    }
    //if it has both children
    else
    {
        treeNode * prev = nullptr;
        treeNode * curr = goneNode->right;
        while (curr->left)
        {
            prev = curr;
            curr = curr->left;
        }
        //prev points to the copy over data
        delete goneNode->item;
        if (!prev)
        {
            goneNode->item = curr->item;
            goneNode->right = curr->right;
            curr->item = nullptr;
        }
        else
        {
            goneNode->item = curr->item;
            curr->item = nullptr;
            prev->left = curr->right;
        }
    }
}

这运行良好，但是当我在删除节点后尝试列出树中的所有元素时(使用这些函数):

void collection::displayByName() const
{
    std::cout << std::endl
        << "========================================" << std::endl;
    //display the tree inorder
    listAll(root);
}
void collection::listAll(const treeNode * const & root) const
{
    if (root)
    {
        std::cout << *(root->item) << std::endl
            << "========================================" << std::endl;
        listAll(root->left);
        listAll(root->right);
    }
}

我收到此错误:

当我在删除一个节点后退出程序时(调用这些析构函数):

collection::~collection()
{
    delete root;
}
collection::treeNode::~treeNode()
{
    delete left;
    delete right;
}

我收到此错误:

任何建议将不胜感激，因为我认为我的 listAll() 函数没有理由调用我已经删除的节点。

顺便说一下，这是我的 treeNode 结构:

struct treeNode
    {
        treeNode();
        treeNode(vendor *& item);
        ~treeNode();
        vendor * item;
        treeNode *left, *right;
    };
    treeNode * root;    //the bst

    hashNode ** table;  //the hash table
    uint8_t capacity;
    uint8_t size;
    const static uint8_t INIT_CAP = 20;

Answer 1

当您需要从单链表或树中删除节点时，我发现使用指向指针的指针很方便。也就是说，如果我们有一个 treeNode** ptr;，那么 *ptr 就是指向我们节点的指针。因此，如果 ptr = &root，则 *ptr = nullptr 将 root 设置为 nullptr。

我删除了 deleteNode 函数并将其逻辑放入 removeFromTree 函数中。

bool collection::removeFromTree(const char name[])
{
    treeNode** ptr = &root;

ptr 不是指向treeNode 的指针，而是指向树结构中的treeNode*。这样，我们就可以修改将我们引导到当前节点的指针。标记为 //same as before 的行具有您正在使用的相同逻辑，只是可能被修改以说明 ptr 有另一个级别的取消引用要做。

    int result; //same as before
    while (*ptr) //While we haven't hit a dead end
    {
        result = strcmp(name, (*ptr)->item->getName()); //same as before
        if (result < 0) //same as before
            ptr = &((*ptr)->left); //same as before
        else if (result > 0) //same as before
            ptr = &((*ptr)->right); //same as before
        else //begin deleteNode() logic
        {
            if ((*ptr)->left && (*ptr)->right) //two children
            {

在这里，我们使用指向成员的指针，因为替代方案是在每一行上都有一个条件运算符。如果一个节点有两个 child ，我们需要在左侧找到最右边的节点，或者在右侧找到最左边的节点。这是我们可以用来替换当前节点的节点。

                treeNode* treeNode::*dir = some_condition ? &treeNode::right : &treeNode::left; //pointer to treeNode member of type treeNode*
                treeNode* treeNode::*ndir = some_condition ? &treeNode::left : &treeNode::right;  //pointer to treeNode member of type treeNode*

dir 现在指向 left 或 right，这是我们搜索树的方向。 ndir 是相反的方向。所以，如果我们想要最右边的节点在左边，(*ptr)->*dir == (*ptr)->left 和 (*ptr->*ndir == (*ptr)->right。如果我们想要最左边的右边节点，它会被颠倒过来。这只是一种更复杂的方式来做更少的工作，真的。应该不难删除。some_condition 只是 true 或 false。true 表示树的左侧(从当前节点开始)失去了一个节点，false 表示右侧。

                treeNode** replacement = &((*ptr)->*ndir); //the node to replace the current one with
                while ((*replacement)->*dir) //While we aren't at the edge
                    replacement = &((*replacement)->*dir);

循环直到 *replacement 是我们需要用其替换 *ptr 的节点。

                treeNode* rep_branch = (*replacement)->*ndir; //If the replacement node had a child, this is now it

                (*replacement)->left = (*ptr)->left; //Copy current to replacement
                (*replacement)->right = (*ptr)->right; //Copy current to replacement
                (*ptr)->left = nullptr; //null out current in case of destructor
                (*ptr)->right = nullptr; //null out current in case of destructor

现在，替换节点指向待删除节点的子节点，而我们即将过期的节点已经没有子节点了。现在，删除不需要的节点是安全的。如果节点类具有删除其子节点的析构函数，则 left 和 right 指针将设置为 nullptr 以防万一。

                delete *ptr; //delete unwanted node
                *ptr = *replacement; //replacement node has taken the unwanted node's place in the tree
                *replacement = rep_branch; //The replacement's child takes its own place
            }

这样就完成了树的结构。无论不需要的节点在哪里，替换节点都会取代它。并且由于要求替换节点是边缘节点，因此它最多有一个子节点。我们只是用 child 替换它。

            else if ((*ptr)->left) //one child on left
            {
                treeNode* current = *ptr;
                *ptr = (*ptr)->left; //replace current with left
                current->left = nullptr; //null out for safety
                delete current;
            }
            else if ((*ptr)->right) //one child on right
            {
                treeNode* current = *ptr;
                *ptr = (*ptr)->right; //replace current with right
                current->right = nullptr; //null out for safety
                delete current;
            }
            else //no children
            {
                delete *ptr;
                *ptr = nullptr;
            }
            return true; //yay it's over
        }
    }
    return false; //never found it
}

其余部分相当简单，只需替换更简单的节点并返回即可。希望这能给您一些关于如何处理此类问题的想法，以及偶尔使用其中一些结构的想法。这就是我在 treeNode* 上使用 treeNode** 进行此类操作的意思。