0

二叉搜索树的这个删除函数看起来正确吗？当我尝试删除一个节点时，它会运行并返回调用它的开关菜单，但在重新打印树时实际上并没有删除它。我不确定我的退货是否不合适，可能吗？

我的问题是：这个删除语句是否真的删除了传递的项目，还是只是以一种残忍的方式玩弄它让我头疼？

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;
       }

    }
4

1 回答 1

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;
   }

我没有编译或测试它，但我认为它会工作，请让我知道

于 2012-11-22T08:41:25.803 回答