從二進制搜索樹中刪除？

Question

我試圖從二叉搜索樹中刪除，並在調試器 中不斷收到此錯誤，我不知道如何糾正它。這段代碼是否正確？

編程接收到的信號EXC_BAD_ACCESS，無法訪問存儲器。 原因：KERN_INVALID_ADDRESS地址：0x0000000000000000 0x00007fff8cc17fe2中的std :: string ::比較（）

void remove(const Comparable & x, BinaryNode *& t) 
{ 
    if (t != NULL) 
    { 
     if(t->element.find(x) != std::string::npos) 
     { 
      if(t->left != NULL && t->right != NULL) // Two children 
      { 
       t->element = findMin(t->right)->element; 
       remove(t->element, t->right); 
      } 
      else 
      { 
       BinaryNode *oldNode = t; 
       t = (t->left != NULL) ? t->left : t->right; 
       delete oldNode; 
       cout << "Successly deleted!" << endl; 
      } 
     } 
     if(x < t->element) 
     { 
      remove(x, t->left); 
     } 
     else 
     { 
      remove(x, t->right); 
     } 
    } 
    else 
    { 
     cout << x << "<-could not delete?" << endl;    
    }  
} 

Answer 1

首先，一個調試器下與調試設置編譯這一點，那麼運行它。我可以全部 - 但 - 保證它會絆倒確切地說您的失敗案件是。

關於這一點，我猜測這是這一行：

if(x < t->element) // <==== here 
{ 
    remove(x, t->left); 
} 
else 
{ 
    remove(x, t->right); 
} 

出於某種原因，在此之前您的邏輯採取下列扣減：

• 沒有留下也不是，右爲空
• 只有左側或右側爲空

您不會考慮均爲左右爲空，例如在樹葉節點中就是這種情況。因此這一點，從您的其他條件採取：

BinaryNode *oldNode = t; 
t = (t->left != NULL) ? t->left : t->right; 
delete oldNode; 
cout << "Successly deleted!" << endl; 

在葉節點的情況下，將離開t設置爲NULL，即將由該代碼在此答案的開始取消引用。

您需要爲此重寫您的邏輯，並且如果解除引用之前的代碼可以使指針被解除引用無效，那麼您需要首先檢查它第一個。

最後，如果你想知道什麼是提示是違規行，你得到報告字符串比較的具體錯誤是解引用空ptr。除了通過operator <過載之外，字符串比較不會在此函數的其他任何位置執行。