在我的刪除操作在C + +中的Seg錯誤

我正在寫一個C++分配的代碼，它是一個使用二叉搜索樹的字典實現。我的代碼編譯，但是當我嘗試「刪除」我得到一個seg故障。任何想法爲什麼會發生。由於在我的刪除操作在C + +中的Seg錯誤

這裏是我的代碼

// 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 
    }

我做了正確的它的工作，並沒有拋出任何錯誤或故障賽格相同。非常感謝！！！！

來源

2014-09-12 user642206

如果被刪除的單詞不在樹中，則會遞歸到一個空節點中。當你嘗試做'nodePtr-> word'時，你將會解引用一個空指針。 – Barmar 2014-09-12 21:43:14

啓用coredump並查看回溯。在刪除檢查null和打印輸出之前 – resultsway 2014-09-12 21:43:18

在'makeDeletion'中，您不處理左側和右側子項都爲空的情況。 – Barmar 2014-09-12 21:45:07

案例1：空樹：

假設你你的樹是空的：root會nullptr。因此，deleteContent()將針對nodePtr調用deleteNode()，參數爲nullptr。

你做的第一件事情有一個與nodePtr->word比較word沒有先檢查nodePtr不nullptr。你有第一個分段故障！

案例2：刪除一個字是不是在樹：

在這種情況下，deleteNode()將被遞歸調用，直到達到沒有後代的葉節點。由於搜索到的單詞不存在於樹中，因此它不是geater或小於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()現在應該由deleteNode()被稱爲當且僅當nodePtr不爲空和word==nodePtr->word。擺脫第一個if（），在任何情況下都不應該是真的。可以用assert替換它來驗證不變量。

案例3：在樹中刪除一個字：

所有的三種情況似乎工作（有兩個空指針甚至葉節點），至少如果我看看我的數據結構圖。

不過我建議你到驗證Node::~Node()：在任何情況下，你重新孩子，然後刪除舊節點（temNodePtr），而不必設置它的孩子nullptr。所以我想知道~Node()只是在不照顧孩子的情況下銷燬節點（然後makeDeletion()應該可以工作），或者如果它的遞歸析構函數刪除節點及其子節點（那麼makeDeletion()將不起作用，因爲您將刪除節點，我剛剛重新連接，沒有注意到它，因此在第一次創建seg.fault）。

順便說一下，即使NULL也可以正常工作，nullptr會比pernp更適合於NULL。

來源

2014-09-12 22:40:46 Christophe

在我的刪除操作在C + +中的Seg錯誤

回答

相關問題