c++ - 在C++中的删除操作中出现段错误

我正在为C ++赋值编写代码，它是使用二进制搜索树的字典实现。我的代码可以编译，但是当我尝试“删除”时，出现段错误。任何想法为什么会发生。谢谢

这是我的代码

// this function calls the deleteNode function where the deletion is done
void BST::deleteContent(string *word)
{
    deleteNode(word, root);
}
// a helper fuuntion for the deletecontent function
//uses recursion to find the node to be deleted
void BST::deleteNode(const string *word, Node *&nodePtr)
{
    if(word < nodePtr->word)
        deleteNode(word, nodePtr->left);
    else if(word > nodePtr->word)
        deleteNode(word, nodePtr->right);
    else
        makeDeletion(nodePtr);
}
// a helper function for the deleteNode function
void BST::makeDeletion(Node *&nodePtr)
{
    Node *tempNodePtr;

    if(nodePtr == NULL)
        cout<< "cannot delete empty node. \n";
    // if node has no right child
    else if (nodePtr->right == NULL)
        {
            tempNodePtr = nodePtr;
            nodePtr = nodePtr->left; // reattach child
            delete tempNodePtr;
        }
    else if(nodePtr-> left == NULL)
        {
            tempNodePtr = nodePtr;
            nodePtr = nodePtr->right; // reattach child
            delete tempNodePtr;
        }
    // if node has 2 children
    else
        {
            tempNodePtr = nodePtr->right;
            while (tempNodePtr->left)
                tempNodePtr = tempNodePtr->left;
            tempNodePtr->left = nodePtr->left;
            tempNodePtr = nodePtr;
            nodePtr = nodePtr->right;
            delete tempNodePtr;
        }
}

编辑：

谢谢你们！！从您的帖子中，我意识到检查节点是否为最后一个节点并且没有子节点是个好主意。我在deleteNode中添加了此检查

    if((nodePtr->left) && word < nodePtr->word)
    {
        do something
    }

我为权利做了同样的事情
它有效，没有引发任何错误或段错误。非常感谢！！！！

最佳答案

情况1：空树：

假设您的树为空：root将为nullptr。因此，deleteContent()将为deleteNode()用参数nullptr调用nodePtr。

您要做的第一件事是将word与nodePtr->word进行比较，而无需先检查nodePtr不是nullptr。这是您出现分割错误的第一种情况！

情况2：删除不在树中的单词：

在这种情况下，deleteNode()将被递归调用，直到到达没有后代的叶节点。由于搜索到的单词在树中不存在，因此它的名称比nodePtr-> word少，或者小于nodePtr-> word，但绝不相等。然后deleteNode()会自称，再次传递
与nullptr的参数nodePtr，如情况1所示。同样，您将遇到分段错误！

情况1和2的解决方案：在deleteNode（）中控制nullptr：

void BST::deleteNode(const string *word, Node *&nodePtr)
{
    if (nodePtr==nullptr)
        cout << word << " not found in the tree\n";
    else if (word < nodePtr->word)
        ...   // the rest as in your original function
}

现在且仅当makeDeletion()不为null且deleteNode()时，nodePtr才应由word==nodePtr->word调用。摆脱第一个if（）在任何情况下都不再为真。可以用断言at代替它以验证不变量。

情况3：删除树中的单词：

至少在我查看数据结构图的情况下，所有这三种情况似乎都起作用（甚至具有两个空指针的叶子节点）。

但是，我建议您验证Node::~Node()：在所有情况下，您都必须重新附加子节点，然后删除旧节点（temNodePtr），而不必将其子节点设置为nullptr。因此，我想知道~Node()是否只是在不照顾其子节点的情况下销毁了该节点（然后makeDeletion()应该可以工作），还是它的递归析构函数，删除了该节点及其子节点（然后makeDeletion()将无法工作，因为您会删除您刚刚重新连接的节点，而不注意它，从而在第一次创建seg.fault。

顺便说一句，即使NULL也可以正常工作，对于指针，nullptr也许比NULL更合适。