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

Question

我正在为 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
    }

我对右边也做了同样的事它有效并且没有抛出任何错误或段错误。非常感谢!!!!

Answer 1

案例 1:空树:

假设你的树是空的:root 将是 nullptr。所以 deleteContent() 将调用 deleteNode() 并为 nodePtr 设置参数 nullptr。

你做的第一件事是比较 word 和 nodePtr->word 而不是首先检查 nodePtr 不是 nullptr。您遇到了第一个段错误案例!

案例 2: 删除一个不在树中的单词:

在这种情况下，deleteNode() 将被递归调用，直到到达没有后代的叶节点。由于搜索到的单词不存在于树中，因此它比 nodePtr->word 大或小，但永远不相等。 deleteNode() 将调用自身，再次传递nodePtr 的参数 nullptr，如案例 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() 现在应该由 deleteNode() 调用当且仅当 nodePtr 不为 null 且 word== nodePtr->word.去掉第一个 if() ，它在任何情况下都不应该为真。可以将其替换为 assert at 以验证不变量。

案例三:删除树中的一个单词:

所有这三种情况似乎都有效(即使是带有两个空指针的叶节点)，至少如果我看一下您的数据结构图的话。

但是我建议验证Node::~Node():在所有情况下，您重新附加子节点然后删除旧节点(temNodePtr) 而无需将其子项设置为 nullptr。所以我想知道 ~Node() 是否只是销毁节点而不考虑其子节点(然后 makeDeletion() 应该起作用)或者它是否是递归析构函数，删除节点及其子节点(然后 makeDeletion() 将不起作用，因为您会删除刚刚重新附加的节点，而没有注意到它，从而在第一次创建 seg.fault )。

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