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.
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)).
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() .
void Tree::DestroyRecursive(TreePtr node)
{
if (node)
{
DestroyRecursive(node->left);
DestroyRecursive(node->right);
delete node;
}
}
Tree::~Tree()
{
DestroyRecursive(Root);
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With