Wie lösche ich einen Knoten aus einem binären Suchbaum?

Question

Wie implementiere ich eine Funktion zum Löschen eines Knotens aus einem binären Suchbaum? Im Folgenden finden Sie meine aktuelle Funktion:

void makeDeletion(TreeNode *&tree) { 
    TreeNode *NodeToDelete; 
    NodeToDelete = tree; 
    TreeNode *InOrder; 

    if (tree->right == NULL && tree->left == NULL) { 
     delete NodeToDelete; 
    } 
    if (tree->right == NULL) { 
     tree = tree->left; 
     delete NodeToDelete; 
    } 
    else if (tree->left == NULL) { 
     tree = tree->right; 
     delete NodeToDelete; 
    } 
    else { 
     InOrder = tree->right; 
     while (InOrder->left != NULL) { 
      InOrder = InOrder->left; 
     } 

     NodeToDelete->value = InOrder->value; 
     remove(InOrder, InOrder->value); 
    } 
} 

Und hier ist die remove Funktion Ich habe, dass der Wert gelöscht werden lokalisiert:

void remove(TreeNode *&tree, ANY num) {//Removed Need for ">" 
    if (tree == NULL){ 
     return; 
    } 

    if (tree->value == num) { 
     makeDeletion(tree); 
    } else if (num < tree->value) { 
     remove(tree->left, num); 
    } else { 
     remove(tree->right, num); 
    } 
};//Remove 

Wie ich, dass ich ganz in der Nähe bin steht fühle mich wie, aber wenn Ich gehe, um den Inhalt des Binärbaums auszugeben, bei dem das Programm abstürzt. Ich versuche einen Ansatz zu verwenden, bei dem, wenn der Knoten zwei untergeordnete Elemente hat, der In-Reihenfolge-Nachfolger lokalisiert wird, die Werte der Knoten des In-Reihenfolge-Nachfolgers und des Knotens "gelöscht" werden und anschließend der In-Reihenfolge-Nachfolger gelöscht wird . Ohne die remove Funktion zu justieren, welche Information fehlt mir, damit die makeDeletion Funktion wie beschrieben funktioniert?

EDIT: in der makeDeletion Funktion schrieb ich fälschlicherweise zwei if Anweisungen nacheinander. Die zweite if Anweisung sollte eine else if Anweisung sein.

Answer 1

In makeDeletion, wenn tree ein Blatt ist (beide left und right sind NULL), können Sie den Blattknoten löschen, und nicht setzen tree = nullptr. Dies lässt einen baumelnden Verweis in Ihrem Baum auf Speicher, der freigegeben wurde. Außerdem dereferenzieren Sie dann den (jetzt gelöschten) Knoten im nächsten if. Beides kann zu einem Absturz führen.