二叉搜索樹刪除節點

我改編了本書的代碼：數據結構和算法由Mark Allen Weiss編寫，第3版。二叉搜索樹刪除節點

每當我運行它，它崩潰。通過請求，我將添加整個二叉樹代碼（其長）。每當我試圖在調試模式下運行它，我結束了在remove()功能前三如果else語句之間循環，然後我最終得到這樣的輸出：在項目4Draft

「未處理的異常在0x0007300d。 exe：0xC0000005：訪問衝突讀取位置0x003c0000。「

我很確定這是一個段錯誤，只是試圖找到源代碼。另外，當我運行它時，它不會步入findMin()，但我將它包含在內，因爲它在刪除內，並且尚未完全測試。任何人都可以幫我導出源代碼嗎？

下面是刪除功能：

void remove(const T& x, TreeNode * & tn) const { 
    if(tn == NULL) 
     return; 
    else if(x < tn->data) 
     remove(x, tn->left); 
    else if(tn->data < x) 
     remove(x, tn->right); 
    else if(tn->left != NULL && tn->right != NULL) {//Two Children(Swap the min of the right subtree, and swap 
     tn->data = findMin(tn->right)->data; 
     remove(tn->data,tn->right); 
    } 
    else{ 
     TreeNode *oldNode = tn; 
     tn = (tn->left != NULL) ? tn->left : tn->right; 
     delete oldNode; 
    } 

}

這裏是findMin（）：

TreeNode * findMin(TreeNode *x) const { 
     if(debugMode==true){ 
     cout << "\nWERE IN FINDMIN\n"; 
     } 
     if(x==NULL){ 
      return NULL; 
     } 
     if(x->left==NULL){ 
      if(debugMode==true){ 
      cout << x; 
      } 
      return x; 
     } 

     return findMin(x->left); 
    };

這裏是我在我的測試文件中稱：

cout << "Checking remove()\n"; 
    for(int i =SIZE; i>0;i++){ 
     z.remove(x[i]); 
    } 
    cout << "DONE Checking remove()\n";

來源

2013-11-01 TaylorTheDeveloper

你確定你的循環條件是正確的？

for(int i =SIZE; i>0;i++){ 
    z.remove(x[i]); 
} 
cout << "DONE Checking remove()\n";

也許你應該寫類似：

for(int i = 0; i < SIZE; i++){ 
    z.remove(x[i]); 
}

或

for(int i = SIZE - 1; i >= 0; i--){ 
    z.remove(x[i]); 
}

來源

2013-11-01 20:39:04 dnk

完全正確;該描述使它看起來像一個無限循環或堆棧粉碎，這表明它是。 –

我現在看到它，我花了我所有的時間在看類的功能。多謝你們！ – TaylorTheDeveloper

二叉搜索樹刪除節點

回答

相關問題