So löschen Sie einen Knoten in einem binären Suchbaum mit Rekursion

Question

Ich habe jetzt versucht, eine Löschfunktion zum Löschen eines Knotens in einem binären Suchbaum zu formulieren, da der Knoten den gesuchten Inhalt enthält. Ich habe das Skelett für die Funktion geschrieben, die die Suche nach dem Inhalt durchführt, und gibt true oder false zurück, je nachdem ob es gefunden wurde oder nicht. Das Problem ist, dass ich scheinbar nicht verstehe, wie ich den eigentlichen Löschteil für meine Funktion implementiere. Wenn der Wurzelknoten den Wert enthält, den ich suche, weiß ich nicht, wie ich nach dem Löschen einem der alten root-Kinder die Root-Position zuweisen soll. Es fällt mir auch schwer herauszufinden, wie man die Kinderzeiger nach dem Löschen eines Knotens NULL setzt und Teile des Baums, die möglicherweise durchtrennt werden könnten, erneut verknüpft, wenn ich einfach den Knoten, der den gesuchten Wert enthält, abtrenne.

Unten ist die Funktion, die ich bisher habe:

bool BSTree::Remove(int content, BSTNode*& bst_node) const { 
// makes sure the tree is not empty (function returns false if it is) 
if (bst_node != NULL) { 
    // checks to see if nodes contents matches content param 
    if (bst_node->GetContents() == content) { 
     // checks to see if the node has children 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 

     } else if (bst_node->GetLeftChild() == NULL) { 

     } else if (bst_node->GetRightChild() == NULL) { 

     } else { 

     } 
     return true; 
    // checks to see if the content of node is less/greater than content param 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() != NULL) 
      return Remove(content, bst_node->GetLeftChild()); 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() != NULL) 
      return Remove(content, bst_node->GetRightChild()); 
    } 
    } 
    return false; 
} 

Was ich hinzugefügt haben:

bool BSTree::Remove(int content, BSTNode*& bst_node) { 
    BSTNode* parent = bst_node; 
    if (bst_node == NULL) { 
    return false; 
    } else { 
    if (content == bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 
     if (bst_node == root_) { 
      Clear(); 
     } else { 
      // code for deleting leaf 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      size_--; 
     } 
     } else if (bst_node->GetLeftChild() == NULL) { 
     // code for deleting node with only right child 
     if (bst_node == root_) { 
      parent = bst_node->GetRightChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else if (bst_node->GetRightChild() == NULL) { 
     // code for deleting node with only left child 
     if (bst_node == root_) { 
      parent = bst_node->GetLeftChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else { 
     // code for deleting node with two children 
     size_--; 
     } 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetLeftChild()); 
     } 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetRightChild()); 
     } 
    } 
    } 
    return true; 
} 

Helper-Funktion für die Funktion remove:

int BSTree::FindMin(BSTNode* bst_node) const { 
    if (bst_node != NULL) { 
    if (bst_node->GetLeftChild() != NULL) 
     return FindMin(bst_node->GetLeftChild()); 
    return bst_node->GetContents(); 
    } 
    return 0; 
} 

Answer 1

Eine Möglichkeit, Löschen eines Knotens ist es mit seinem direkten Nachfolger das Blatt zu löschen, so dass Sie den Baum invari nicht zu brechen Ameise.

Der Nachfolger eines Knotens ist das linke untergeordnete Element seines rechten Teilbaums. Wenn Sie also zu dem Knoten gelangen, den Sie löschen möchten, suchen Sie nach dem Nachfolger und tauschen Sie die Knoten aus. Sobald es fertig ist, suchen Sie nach dem Blatt und entfernen Sie es. Wenn Sie das äußerste linke Kind genommen haben, sind Sie sicher, dass das Blatt ein NULL Kind hat. Es hat ein rechtes Kind, ersetze das Blatt durch das richtige Kind und das war's.

Eine übliche Implementierung, die für den binären Suchbaum verwendet wird, ist Remove einen Knoten zurückgeben, so dass Sie den Baum nur durch die Rückgabe der Knoten umformen können, und sich nicht mit Enkelkindern befassen müssen.