二叉樹刪除

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


     } 

    } 

我希望這會有所幫助。