刪除二進制搜索樹的fcn

Question

這是否刪除二進制搜索樹的功能看起來是否正確？當我嘗試刪除一個節點時，它會運行並返回它從中調用的開關菜單，但在重新打印樹時不會實際刪除它。我不確定我是否有退換貨的可能？

我的問題是：這個刪除語句實際上刪除了傳遞的項目，還是隻是以一種殘酷的方式玩弄它，讓我頭痛？

void BinarySearchTree::remove(int d) 
    { 
     //Locate the element 
     bool found = false; 
     if(isEmpty()) 
     { 
      cout<<" This Tree is empty! "<<endl; 
      return; 
     } 

     tree_node* curr; 
     tree_node* parent; 
     curr = root; 

     while(curr != NULL) 
     { 
      if(curr->data == d) 
      { 
      found = true; 
      break; 
      } 
      else 
      { 
      parent = curr; 
      if(d>curr->data) curr = curr->right; 
      else curr = curr->left; 
      } 
     } 
     if(!found) 
     { 
      cout<<" Data not found! "<<endl; 
      return; 
     } 


     // 3 cases : 
     // 1. We're removing a leaf node 
     // 2. We're removing a node with a single child 
     // 3. we're removing a node with 2 children 

     // Node with single child 
      // Node with single child 
if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL)) 
{ 
    if(curr->left == NULL && curr->right != NULL) 
    { 
    if(parent->left == curr) 
    { 
     parent->left = curr->right; 
     delete curr; 
    } 
    else 
    { 
     parent->right = curr->right; 
     delete curr; 
    } 
    } 
    else // left child present, no right child 
    { 
    if(parent->left == curr) 
    { 
     parent->left = curr->left; 
     delete curr; 
    } 
    else 
    { 
     parent->right = curr->left; 
     delete curr; 
    } 
    } 
    return; 
} 

     //We're looking at a leaf node 
     if(curr->left == NULL && curr->right == NULL) 
     { 
      if(parent->left == curr) 
      { 
      parent->left = NULL; 
      } 
      else 
      { 
      parent->right = NULL; 
      } 
      delete curr; 
      return; 
     } 


     //Node with 2 children 
     // replace node with smallest value in right subtree 
     if (curr->left != NULL && curr->right != NULL) 
     { 
      tree_node* chkr; 
      chkr = curr->right; 
      if((chkr->left == NULL) && (chkr->right == NULL)) 
      { 
      curr = chkr; 
      delete chkr; 
      curr->right = NULL; 
      } 
      else // right child has children 
      { 
      //if the node's right child has a left child 
      // Move all the way down left to locate smallest element 

      if((curr->right)->left != NULL) 
      { 
       tree_node* lcurr; 
       tree_node* lcurrp; 
       lcurrp = curr->right; 
       lcurr = (curr->right)->left; 
       while(lcurr->left != NULL) 
       { 
        lcurrp = lcurr; 
        lcurr = lcurr->left; 
       } 
       curr->data = lcurr->data; 
       delete lcurr; 
       lcurrp->left = NULL; 
      } 
      else 
      { 
       tree_node* tmp; 
       tmp = curr->right; 
       curr->data = tmp->data; 
       curr->right = tmp->right; 
       delete tmp; 
      } 

      } 
      return; 
     } 

    } 

Answer 1

我閱讀我們的代碼，我在紙上寫不同的情況，我認爲在該節點有2個孩子的代碼應該是這樣的

//Node with 2 children 
    if (curr->left != NULL && curr->right != NULL) 
    { 
     tree_node* chkr; 
     if(parent==NULL || parent->left==curr){ //if parent==NULL it means that the node that we want to delete is root 
      chkr=curr->right; 
      while(chkr->left!=NULL) 
       chkr=chkr->left; 
      if(parent!=NULL) 
       parent->left=curr->right; 
      else 
       root=curr->right; 
      chkr->left=curr->left; 
      curr->left=curr->right=NULL; 
      delete curr; 
     }else if(parent->right==curr){ 
      chkr=curr->left; 
      while(chkr->right!=NULL) 
       chkr=chkr->right; 
      parent->right=curr->left; 
      chkr->right=curr->right; 
      curr->left=curr->right=NULL; 
      delete curr; 
     } 
     return; 
    } 

我沒有編譯的情況下或測試它，但我認爲它會工作， plz讓我知道它