c++ - 二分木削除

Question

削除機能を終了しようとしています

これが擬似コードです。終わりに注意してください。

ただし、擬似コードが間違っているかどうかはわかりません。

これが私がそれをどのように解釈したかです：

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

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

一度削除する場合を除いて、印刷時に1兆個のゼロを埋め始めます。

私がしていることは意味がありますか？私が持っている残りのコードは正しいか、とにかくそう思います。このシナリオでは失敗するだけです。

これが最小関数でもあります

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

最初にツリーを検索したいので、削除したいノードがあるかどうかを確認します。

そこにある場合は、3 つのケーシングを確認します。

1: 子を持たないノードを削除する場合。: この場合、子がないため、前述のノードを削除するだけです。

2: 左または右の子を持つノードを削除する場合: この場合、削除するノードの親に左または右の子を設定します。

3: 2 つの子を持つノードを削除する場合: この場合、削除するノードの後続ノードを見つけて、後続ノードを削除ノードと交換する必要があります。

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


        }

     }

これが何らかの形で役立つことを願っています。