c++ - 二叉树删除

Question

我正在尝试完成删除功能

这是伪代码，注意结尾。

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

以下是我的解释：

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;

}

Answer 1

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

如果它在那里，你想检查三个套管：

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


        }

     }

我希望这会有所帮助。