Destructor voor binaire zoekboom

Ik probeer de destructor voor mijn binaire zoekboom te schrijven en ik weet hoe ik recursief door de boom moet lopen, maar ik weet niet hoe ik dat in de destructor moet doen, zodat elk knooppunt wordt verwijderd.

Mijn kop is:

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;
};

Mijn constructor is:

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

Is er een manier om de destructor recursief aan te roepen? Zo niet, hoe doorloop ik elk knooppunt om het te verwijderen.

Antwoord 1, autoriteit 100%

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

Antwoord 2, autoriteit 30%

Je hebt twee destructors nodig:

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

en

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

Maar je hebt hier niet echt twee klassen nodig. Elke Nodeis een boom.

Antwoord 3, autoriteit 10%

Als je deleteaanroept of je Treegaat naar het einde van de levensduur (een blok verlaten, zoals het voorbeeld aan het einde), moet je deletede Treekinderen Nodes en de deleteoperator zullen de destructor aanroepen, zie voorbeeld aan het einde.

Hierdoor verdwijnt de Boom volledig uit het geheugen wanneer de Boomvernietiger wordt aangeroepen.

Probeer dit eens:

#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))));
}

Antwoord 4

Hier is mijn implementatie. Een Tree is gelijk aan een TreeNode.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    ~TreeNode() {
        delete left;
        delete right;
    }
    ...
};

Verwijder eenvoudigweg het wortelknooppunt van de boom, dan wordt de hele boom recursief verwijderd.

TreeNode* root = new TreeNode(2);
delete root;

Misschien weet je al wat een verwijderendoet.

Als delete wordt gebruikt om de toewijzing van geheugen voor een C++-klasseobject ongedaan te maken, wordt de
de destructor van het object wordt aangeroepen voordat het geheugen van het object is
ongedaan gemaakt (als het object een destructor heeft).

Dus in de destructor van een treeNode hoeft u alleen de linker- en rechterwijzers te vernietigen die handmatig door u zijn toegewezen. U hoeft zich geen zorgen te maken over de deallocatie van de node zelf.