Деструктор для дерева двоичного поиска

Question

Я пытаюсь написать деструктор для моего двоичного дерева поиска, и я знаю, как рекурсивно прокручивать дерево, но я не знаю, как это сделать в деструкторе, чтобы каждый узел был удален.

Мой Заголовок является:

struct Node; 
typedef string TreeType; 
typedef Node * TreePtr; 

//Defines a Node 
struct Node 
{ 
    TreeType Info; 
    int countDuplicates = 1; 
    TreePtr Left, Right; 
}; 

class Tree 
{ 
public: 
    //Constructor 
    Tree(); 

    //Destructor 
    ~Tree(); 

    //Retruns true if the tree is Empty 
    bool Empty(); 

    //Inserts a Node into the tree 
    bool Insert(TreeType); 

    //Delete decides what type of delection needs to occur, then calls the correct Delete function 
    bool Delete(Node * , Node *); 

    //Deletes a leaf node from the tree 
    bool DeleteLeaf(TreePtr, TreePtr); 

    //Deletes a two child node from the tree 
    bool DeleteTwoChild(TreePtr); 

    //Deletes a one child node from the tree 
    bool DeleteOneChild(TreePtr, TreePtr); 

    //Finds a certain node in the tree 
    bool Find(TreeType); 

    //Calculates the height of the tree 
    int Height(TreePtr); 

    //Keeps a count of the nodes currently in the tree; 
    void Counter(); 

private: 

    //Prints the nodes to the output text file in order alphabetically 
    void InOrder(ofstream &,TreePtr); 

    //Defines a TreePtr called Root 
    TreePtr Root; 

    //Defines a TreePtr called Current 
    TreePtr Current; 

    //Defines a TreePtr called Parent 
    TreePtr Parent; 
}; 

Мой конструктор:

Tree::Tree() 
{ 
    Root = NULL; 
    Current = NULL; 
    Parent = NULL; 
} 

Есть ли способ вызвать деструктор рекурсивно? Если нет, как мне пройти через каждый узел, чтобы удалить его.

Answer 1

void Tree::DestroyRecursive(TreePtr node) 
{ 
    if (node) 
    { 
     DestroyRecursive(node->left); 
     DestroyRecursive(node->right); 
     delete node; 
    } 
} 

Tree::~Tree() 
{ 
    DestroyRecursive(Root); 
} 

Answer 2

Вам нужно два деструкторов:

Tree::~Tree() 
{ 
    delete Root; 
} 

и

Node::~Node() 
{ 
    delete Left; 
    delete Right; 
} 

Но вы на самом деле не нужны два класса здесь. Каждый Node - это дерево.

Answer 3

При вызове delete или ваш Tree идет до конца жизни (выход из блока, как пример в конце), вы должны delete в Tree детях Node с и оператор delete будет вызывать деструктор, смотрите пример в конце.

Это приведет к тому, что Дерево полностью исчезнет из памяти при вызове дрессировщика дерева.

Просто попробуйте это:

#include <iostream> 
using namespace std; 

class Node { 
    Node *left, *right; 
public: 
    Node(Node *l, Node *r); 
    ~Node(); 
}; 

class Tree { 
    Node *root; 
public: 
    Tree(Node *rt); 
    ~Tree(); 
}; 

Tree::Tree(Node *rt):root(rt) { 
    cout << "new Tree with root node at " << rt << endl; 
} 
Tree::~Tree() { 
    cout << "Destructor of Tree" << endl; 
    if (root) delete root; 
} 
Node::Node(Node *l, Node *r):left(l), right(r) { 
    cout << "Node@" 
     << this 
     << "(left:" << l 
     << ", right:" << r << ")" 
     << endl; 
} 
Node::~Node() { 
    cout << "~Node@" << this 
     << endl; 
    if (left) delete left; 
    if (right) delete right; 
} 

int main() { 
    Tree t(
     new Node(
      new Node(
       new Node(
        new Node(0, 0), 
        0), 
       0), 
      new Node(0, new Node(0, 0)))); 
}