C++二進制搜索樹刪除

所以，我的問題是我不明白爲什麼這不起作用。我在下面評論了它在說什麼，當它明確時父從未被初始化。我在做指針錯誤嗎？我是否已經將邏輯向後推進，我現在離開了，從頭開始更好？這是我遇到的最困難的任務，所以任何幫助都是非常有益的。C++二進制搜索樹刪除

void Dictionary::remove(string word) 
{ 
if(root == NULL) 
{ 
    cout << "list is empty\n"; 
    return; 
} 
DictionaryNode *curr = root; 
DictionaryNode *parent = NULL;` 

while(curr != NULL) 
{ 
    if(curr->word == word) 
     break; 
    else 
    { 
     parent = curr; 
     if(word > curr->word) 
      curr = curr->right; 
     else 
      curr = curr->left; 
    } 
} 
//LEAF node. 
if(curr->left == NULL && curr->right == NULL) 
{ 
    if(parent->left == curr) // Right here is an access violation. Which doesn't //make sense. 
    { 
     parent->left = NULL; 
    } 
    else 
    { 
     parent->right = NULL; 
    } 
    delete curr; 
} 

/* 
* Node has a single child LEFT or RIGHT 
*/ 
if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL)) 
{ 
    if(curr->left == NULL && curr->right != NULL) 
    { 
     if(parent->left == curr) //if(parent->left == curr) //says parent is //not intialized 
     { 
      parent->left = curr->right; 
      delete curr; 
     } 
     else 
     { 
      parent->right = curr->right; 
      delete curr; 
     } 
    } 

    else 
    { 
     if(parent->left == curr) 
     { 
      parent->left = curr->left; 
      delete curr; 
     } 
     else 
     { 
      parent->right = curr->left; 
      delete curr; 
     } 
    } 

} 

if (curr->left != NULL && curr->right != NULL) 
{ 
    DictionaryNode* temp; 
    if(parent == NULL || parent->left==curr) 
    { 
     temp = curr->right; 
     while(temp->left!=NULL) 
      temp = temp->left; 
     if(parent!=NULL) 
      parent->left = curr->right; 
     else 
      root = curr->right; 
     temp->left = curr->left; 
     curr->left = curr->right=NULL; 
     delete curr; 

    } 

    else if(parent->right==curr) 
    { 
     temp = curr->left; 
     while(temp->right!=NULL) 
      temp = temp->right; 
     parent->right=curr->left; 
     temp->right = curr->right; 
     curr->left = curr->right=NULL; 
     delete curr; 
    } 
    } 

}

來源

2014-03-28 varrick

如果字典中只包含1個元素，該怎麼辦？ 'curr == root'，'parent == NULL'，'parent-> left'是一個訪問衝突。 – timrau

另外，您嘗試在'delete curr;'之後訪問'curr-> left'。這顯然是一個釋放的內存讀取。 – timrau

首先，謝謝你編輯它我不能爲我的生活弄清楚。如果我有一個元素，它的作品。我應該在我的問題上更具體。這是當我去刪除它開始拋出我的臉上的錯誤的東西。 – varrick

1. 第一件事，我看到：

while(curr != NULL) 
{ 
//stuff 
}

因爲它是寫的，它似乎在你的循環CURR == NULL結束

懶惰的我不得不看你的循環的內容注意到休息。循環中的更大塊可能會更不明顯。這不是一個好習慣。

使用bool（例如：bool isNodeFound;），它很便宜（一位）並使其更清晰。 while（curr！= NULL & &！isNodeFound）更加清楚你的意圖，乍一看，沒有看你的循環內容。

2.如果確實沒有在循環中打中斷並且curr == NULL？你的下一個指令curr-> left會失敗！似乎布爾將再次有用！

if(!isNodeFound) 
{ 
//log error if you can "cannot remove node because it is not in dictionary" 
return false; //make your function a bool to return if it succeeded or not 
}

嘗試分析你的代碼的其餘部分用着相同的狀態，更加清晰和測試，讓我知道，如果它的工作原理。

來源

2014-03-28 00:43:27 vincentB

嗯，看我明白你的意思，但是，我不認爲做布爾函數真的會幫助我。事情是，它會刪除一些東西，不管它是根節點還是最後一個節點還是最後一個孩子。這只是有時，它給了我訪問衝突。我不明白，但我會嘗試你所說的。謝謝 – varrick

在技術上bool使用一個字節的空間而不是一個位，因爲計算機無法尋址單個位，只能尋址字節。 – isaac9A

std :: vector 可以將bools包裝成點！但是我的意思是字節哈哈，謝謝varrick – vincentB

C++二進制搜索樹刪除

回答

相關問題