删除二进制搜索树的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让我知道它