Recursive calls to the binary tree destructor
from my understanding, this code for the binary search tree destructor works:
~tree(){
remove(root);
}
void remove(node* root)
{
if (root == NULL) return;
remove(root->left);
remove(root->right);
delete root;
}
However, I would like to know if the following destructor call works?
~node(){
delete left;
delete right;
}
~tree(){
delete root;
}
My understanding is that deleting the root will automatically call the child nodes and remove them. Is this a correct assumption? If this is indeed correct, then what's a simple approach to check if the destructor is working?
{{This part of the message was added later}}
I am using the second method here. While checking the output expression, the code below doesn't work because I am getting the only delete output (which is apparently for the root node)
struct node{
~node(){
delete left;
delete right;
}
};
class tree {
node* root;
public:
tree(){
root=NULL;
}
~tree(){
cout<<"Deleting: "<<endl;
delete root;
}
void insert (int x){};
}
int main(){
A.insert(12);A.insert(13);A.insert(10);
return 0;
}
Here is the output I get:
Deleting:
Ideally there should be 3 such expressions, but I only get 1.
source to share
Yes, it will work assuming the leaf nodes have left and right values equal to nullptr.
As per C ++ standard (5.3.5 Delete)
6 If the operand value of the delete-expression is not a null pointer value , the expression-expression will call the destructor (if any) on the object or elements of the array to be deleted. In the case of an array, the elements will be destroyed in order (that is, in the reverse order of completion of their constructor; see 12.6.2).
Thus, the destructor of node will only be called if node is not a null pointer value.
If you want to check that the destructor actually works, just insert the output statement into the body of the destructor.
Here is a demo program
#include <iostream>
struct node
{
node *next;
int x;
~node()
{
std::cout << "inside node: " << x << std::endl;
delete next;
}
};
void push_front( node **tree, int x )
{
node *n = new node;
n->x = x;
n->next = *tree;
*tree = n;
}
void clear( node **tree )
{
delete *tree;
*tree = nullptr;
}
int main()
{
node *tree = nullptr;
for ( int i = 0; i < 10; i++ ) push_front( &tree, i );
clear( &tree );
}
Output signal
Compiled with /EHsc /nologo /W4
main.cpp
Compilation successful!
Total compilation time: 187ms
inside node: 9
inside node: 8
inside node: 7
inside node: 6
inside node: 5
inside node: 4
inside node: 3
inside node: 2
inside node: 1
inside node: 0
Total execution time: 734ms
source to share