Löschen binärer Suchbaum

Question

Ich versuche, den gesamten binären Suchbaum (jeden Knoten in der Struktur) zu löschen, welche dieser Funktionen wird Ihrer Meinung nach besser funktionieren?

private: 
    struct Node { 
     string value; 
     Node* left; 
     Node* right; 
    }; 
    Node* root; 

public: 
    BST() { 
     root = NULL; 
    } 

    ~BST() { 
     delete root->left; 
     delete root->right; 
    } 

oder:

... 
    void destroyTree (Node*& tree) { 
     while (tree != NULL) { 
      tree = tree->left; 
      delete tree; 
     } 
     while (tree != NULL) { 
      tree = tree->right; 
      delete tree; 
     } 
     delete tree; 
    } 

Answer 1

Weder die vorgeschlagene destructor ~BST() noch die vorgeschlagene Funktion destroyTree() des class BST die BST-Instanz löschen und wird als die andere besser.

Erläuterung 1 - Was macht der Destruktor ~BST()?

Die vorgeschlagene Quelle ist einfach delete root->left; von delete root->right; gefolgt und werden nur zwei Knoten des BinarySearchTree löschen.

1. Der Knoten root nicht mit NULL überprüfen und ansonsten nie gelöscht wird,
2. Der Knoten root->left ist nicht zu mit NULL zu überprüfen,
3. Der Knoten root->right nicht zu mit NULL überprüfen,

Erläuterung 2 - Was macht die Funktion destroyTree()?

Zwei while-loops versuchen die Erkundung des Baumes, einen für die linke Verzweigung und einen für den rechten Zweig. Die Bedingung (tree != NULL) ist , die nur zum Beenden der Schleife vorhanden ist, prüft jedoch nicht, ob der aktuelle Knoten gelöscht werden kann.

1. Mit der linken Schleife, nur ->left Knoten des root->left wird bis tree->left == NULL und CRASH wenn zu delete tree;, versuchen
2. Selbst gelöscht werden, nachdem sie von der Schleife eine if (tree==NULL) break; zu beenden Hinzufügen bevor die delete tree; Aufruf eine neue CRASH in der richtigen Schleife,
3. Und die letzte delete tree; ist ein Unsinn, weil an dieser Position, tree ist immer '== NULL'.

Bonus Lösung - basierend auf einer Modifikation der Funktion destroyTree().

Eine rekursive Funktion ist die einfachste Möglichkeit, alle erstellten und eingefügten Knoten zu löschen. Aber beachte die Größe des BinarySearchTree und vor allem die tiefste Verzweigung.

void destroyTree(Node *cur_node) { 
    if (cur_node!=NULL) { 
     // explore and delete on left 
     destroyTree(cur_node->left); // recursive-call 
     // explore and delete on right 
     destroyTree(cur_node->right); // recursive-call 
     // delete each node 
     delete cur_node; 
    } 
}