Binary Search Tree rekursive Destruktor

Question

Ich habe andere ähnliche Themen überprüft, aber keine schien mir zu helfen.

Ich versuche, einen Destruktor für diese spezifische BST-Implementierung zu schreiben. Jeder Knoten enthält einen Zeiger auf den Elternknoten, einen Zeiger auf den linken Knoten, einen Zeiger auf den rechten Knoten und einen Zeiger auf den darin enthaltenen Wert. Dies ist, wie der Beginn der Klasse aussieht:

#ifndef BST_H 
#define BST_H 

#include <iostream> 

template <typename T> 
class BST{ 
    private: 
     BST<T> *left; 
     BST<T> *right; 
     BST<T> *parent; 
     T *value; 

    public: 
     BST() { 
      this->parent = NULL; 
      this->left = NULL; 
      this->right = NULL; 
      this->value = NULL; 
     } 

     ~BST() { 
      removeRecursively(this); 
     } 

     void removeRecursively(BST<T>* node) { 
      if (node->left != NULL) 
       removeRecursively(node->left); 
      if (node->right != NULL) 
       removeRecursively(node->right); 
      if (node->left == NULL && node->right == NULL) { 
       if (node->parent->left == node) 
        node->parent->left = NULL; 
       if (node->parent->right == node) 
        node->parent->right = NULL; 

       node->parent = NULL; 
       node->value = NULL; 
       delete node->value; 
       delete node; 
      } 
     } 

     void add(T value) { 
      if (this->value == NULL) { // root-only case 
       this->value = new T; 
       *(this->value) = value; 
      } 
      else { 
       if (value < *(this->value)) { 
        if (this->left != NULL) // has left child 
         this->left->add(value); 
        else { // has no left child 
         this->left = new BST<T>; 
         this->left->value = new T; 
         this->left->parent = this; 
         *(this->left->value) = value; 
        } 
       } 
       else { 
        if (this->right != NULL) // has right child 
         this->right->add(value); 
        else { // has no right child 
         this->right = new BST<T>; 
         this->right->value = new T; 
         this->right->parent = this; 
         *(this->right->value) = value; 
        } 
       } 
      } 
     } 

     void inOrderDisplay() { 
      if (this->left != NULL) 
       this->left->inOrderDisplay(); 
      std::cout << *(this->value) << " "; 
      if (this->right != NULL) 
       this->right->inOrderDisplay(); 
     } 

     BST<T>* search(T value) { 
      if (*(this->value) == value) 
       return this; 
      else if (this->left != NULL && value < *(this->value)) 
       return this->left->search(value); 
      else if (this->right != NULL && value > *(this->value)) 
       return this->right->search(value); 
      else 
       return NULL; 
     } 

     BST<T>* remove(T value) { 
      BST<T>* node = search(value); 

      if (node != NULL) { 
       if (node->left == NULL && node->right == NULL) { // leaf node 
        delete node->value; 
        if (node->parent->left == node) // is left child 
         node->parent->left = NULL; 
        else // is right child 
         node->parent->right = NULL; 
        delete node; 
       } 

       // 1 child nodes 
       if (node->left != NULL && node->right == NULL) { // has left child 
        if (node->parent->left == node) // is left child 
         node->parent->left = node->left; 
        else // is right child 
         node->parent->right = node->left; 
        delete node->value; 
        node->parent = NULL; 
        delete node; 
       } 

       if (node->left == NULL && node->right != NULL) { // has right child 
        if (node->parent->left == node) // is left child 
         node->parent->left = node->right; 
        else // is right child 
         node->parent->right = node->right; 
        delete node->value; 
        node->parent = NULL; 
        delete node; 
       } 

       // 2 children nodes 
       if (node->left != NULL && node->right != NULL) { 
        T aux; 
        BST<T>* auxNode = node->right; 

        while (auxNode->left != NULL) 
        auxNode = auxNode->left; 

        aux = *(auxNode->value); 

        if (auxNode->right != NULL) { 
         *(auxNode->value) = *(auxNode->right->value); 
         auxNode->right->parent = NULL; 
         auxNode->right->value = NULL; 
         auxNode->right = NULL; 
         delete auxNode->right; 
        } 
        else { 
         if (auxNode->parent->left == auxNode) // is left child 
          auxNode->parent->left = NULL; 
         else // is right child 
          auxNode->parent->right = NULL; 
         auxNode->value = NULL; 
         delete auxNode; 
        } 
        *(node->value) = aux; 
       } 
      } 

      return this; 
     } 
}; 
#endif // BST_H 

Die BST-Klasse verwendet wird, wie folgt:

BST<int>* root = new BST<int>(); 

root->add(5); 
root->add(2); 
root->add(-17); 

root->inOrderDisplay(); 

root->remove(5); 

ich erwähnen, dass alle Methoden richtig funktionieren (ich beschlossen, sie nicht zu veröffentlichen, da Sie sind nicht Gegenstand dieser Frage). Das Problem ist, dass, wenn ich meine Testdatei mit Valgrind ausführe, es einige Speicherlecks entdeckt und ich bin sicher, dass sie auftreten, weil ein richtiger Destruktor fehlt (der obige erzeugt einen Segmentierungsfehler).

EDIT: Ich habe den Code für die anderen Methoden

Thank you!

Answer 1

Ihre grundlegende Design ist eine Art gebrochen, zumindest meiner Meinung nach. Das heißt, wenn Sie bereit sind, durch genug Reifen zu springen, können Sie wahrscheinlich es funktionieren lassen, aber im besten Fall wird es wahrscheinlich immer ein wenig ungeschickt sein, mit zu arbeiten.

Ich würde beginnen, indem ich eine separate Klasse für die Knoten in der Struktur definieren. Dann wird der Baum selbst einen Zeiger auf die Wurzel des Baumes halten und den größten Teil der Schnittstelle zum Baum definieren.

template <class T> 
class Tree { 

    struct node { 
     node *parent; 
     node *left; 
     node *right; 
     T *value; 

     node(T *value) 
      : parent(nullptr), left(nullptr), right(nullptr), value(new T(value)) 
     {    
     } 

     ~node() { 
      delete(left); 
      delete(right); 
      delete(value); 
     }   
    } *root; 

    Tree() : root(nullptr) {} 

    ~Tree() { 
     delete(root); 
    } 
}; 

Die Zerstörung muss nicht explizit rekursiv sein. Die delete(left) (zum Beispiel) ruft den dtor für den linken Kindknoten auf (falls es einen gibt), der den dtor für seine Kindknoten aufruft, und so weiter. Wenn wir einen Blattknoten erreichen, erhalten wir (das Äquivalent von) delete nullptr;, was definiert ist, als würde nichts getan, und die Rekursion gestoppt.

Answer 2

Die schwersten Fehler, die es zu finden gibt, sind diejenigen im Code, die Sie sich nicht angesehen haben, weil Sie sich davon überzeugt haben, dass sie nicht relevant sind.

Sowieso ist es ein offensichtlich Probleme mit der Umsetzung: nach ein paar andere Sachen zu entfernen, sind Sie im Grunde

class foo 
{ 
    ~foo() { delete this; } 
}; 

Answer 3

tun Sie sollten die Linien tauschen:

  node->value = NULL; 
      delete node->value; 

wie folgt aus:

  delete node->value; 
      node->value = NULL; 

Wenn Sie zuerst NULL zuweisen, löschen Sie nichts.

Answer 4

Verwenden RAII mit unique_ptr, um diese Probleme zu vermeiden:

template <typename T> 
class BST{ 
public: 
    BST() = default; 
    ~BST() = default; 

    BST(const BST&) = delete; 
    BST& operator =(const BST&) = delete; 
    BST(BST&&) = delete; 
    BST& operator =(BST&&) = delete; 

private: 
    std::unique_ptr<BST<T>> left; 
    std::unique_ptr<BST<T>> right; 
    BST<T>* parent = nullptr; 
    std::unique_ptr<T> value; 
};