0

我正在尝试完成删除功能

这是伪代码,注意结尾。

我不知道伪代码是否错误。

以下是我的解释:

Node* minNode = Minimum(toDelete->right);

            int tmp = 0;
            tmp = minNode->val;
            // delete(&tmp);
            free(minNode);
            minNode=NULL;
            toDelete->val=tmp;

除了一旦删除它,它就会在打印时开始填充一万亿个零。

我在做什么有意义吗?我所拥有的其余代码是正确的,或者无论如何我都这么认为。它只会在这种情况下搞砸。

这也是最小功能

Node* BST::Minimum(Node *curr) {

    // if (curr->left != NULL) {
    //      return(Minimum(curr->left));
    //  }
    //  return curr;
    Node* node = curr;
    while (node->left != NULL) {
        node = node->left;
    }
    return node;

}
4

1 回答 1

0

您首先要搜索树,然后查看要删除的节点是否存在。

如果它在那里,你想检查三个套管:

1:当您要删除没有子节点的节点时。:在这种情况下,您只需删除所述节点,因为它没有任何子节点。

2:当您要删除具有左或右子节点的节点时:在这种情况下,您将左子节点或右子节点设置为要删除的节点的父节点

3:当你想删除一个有两个孩子的节点时:在这种情况下,你必须找到你要删除的节点的后继节点,然后将后继节点与删除节点交换。

public Boolean delete(int key)
{
    Node current = root;
    Node parent = root;

     //search for node here
    while(current->key != key)
    {
       parent = current; //save the parent the nodes as you loop through it
       if(key < current->key)
           current = current->left
       else
            current = current->right

        //if you do not find the key return false
        if(current==null)
           return false;
    }
    //case 1 start here:
    //check if the said node has no child. in this case we are looking at current
    if(current->left ==null && current->right == null)
     {
          //check if the node you want to delete is the root
          if(current == root)
            root = current
          else
             {
                 if(parent.key > current->key)
                     parent-left = null;
                 else
                     parent->right = null;
             }
     }//case 2 here:
      //check to see if the node has either left or right child
           else if(statement for checking left here)
           {
           //check for the case where your delete a root

           //set the the parent of the current->left to be current->parent
           }
          else if(statement for checking right here)
          {

           //check for the case where your delete a root

           //set the the parent of the current->right to be current->parent
          }
     else
        {
             //create a node successor and give it the successor you found
             Node successor = findSuccessor(Node NodeToDel);

             //check for root being the node you want to delete

             if(root == successor)
                root =  successor;
             else
                {
                    //navigate left, set parent->left = successor

                    //navigate right, set parent->right = successor

                    //with the nature of the findSuccessor() algorithm i have,
                    //i will have to code one more line:

                    // give succeccor->left = current->left; 
                }


        }

     }

我希望这会有所帮助。

于 2012-12-30T02:47:45.570 回答