Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Destructor for Binary Search Tree

Tags:

c++

destructor

I am trying to write the destructor for my Binary Search Tree and I know how to recursively loop through the tree, but I do not know how to do that in the destructor so that every node is deleted.

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

My constructor is:

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

Is there a way to call the destructor recursively? If not, how do I traverse through every node to delete it.

like image 424
Matthew S. Avatar asked Dec 09 '15 03:12

Matthew S.


People also ask

Can a binary search tree be degenerate?

Most Binary Search Trees are not degenerate: in most of them Height is proportional to LOG(# nodes), and we get efficient search. For example, the book cites a theorem (page 267) that if you start with an empty BST and add to it N randomly generated values, the expected Height of the tree is 1.4(log(N+1)).

What is destructor explain its use in C++ with the help of an example?

A destructor is a member function that is invoked automatically when the object goes out of scope or is explicitly destroyed by a call to delete . A destructor has the same name as the class, preceded by a tilde ( ~ ). For example, the destructor for class String is declared: ~String() .


1 Answers

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

Tree::~Tree()
{
    DestroyRecursive(Root);
}
like image 140
John Zwinck Avatar answered Oct 02 '22 23:10

John Zwinck