Need Help deleting a binary search tree class

[Jonsauce]

Here's my code:

///////////////////////////////////////////////////////////
// Name: ~node
// Purpose: Basic Destructor; Calls DeleteTree which traverses the tree and
// deletes all of the nodes
// Recieve: NOTHING
// Return: NOTHING
///////////////////////////////////////////////////////////
node::~node()
{
DeleteTree(Root); //Passing a Ptr to the root node
}

///////////////////////////////////////////////////////////
// Name: DeleteTree
// Purpose: Called by the destructor, traverses the tree and deletes all of the nodes
// Recieve: Node, which is the root node the first time the function is called
// Return: NOTHING
///////////////////////////////////////////////////////////

void node:eleteTree(NODE * Node)
{
if(Node->Left != NULL)
DeleteTree(Node->Left);
if(Node->Right != NULL)
DeleteTree(Node->Right);
delete Node;
Node = NULL;
}

// END OF CODE


My problem is that by the time the Root is passed into my recursive function it is already deleted by the destructor. (The Root is set to NULL before it is passed in). As far as I know this will cause memory leaks because Ive lost access to all the spots in memory that the Root node gave me access to. Please Help if you can! Criticism of my coding style is welcome as long as you can help me out
I do know that my delete function works because I've tested it in other cases such as when I want to clear all the nodes and build a new tree.
Thanks!

Jonathan

 

[dds82]

At the beginning of DeleteTree, you might want to try the line

if (Node==NULL) return;

This way, the first node that is deleted will trigger the destruction of the entire tree, and subsequent calls made by the destruction of the child nodes will not cause a crash.

 

[Jonsauce]

That definately works and keeps my program from crashing But does it actually delete all of the other node's when the destructor is called?
My class stores only the pointer to the root node, so all of the other stuff is hanging out there in memory once it is deleted.
Thanks for your help, it gets me by for now.

 

[Zyrenthian]

Recursion is the way to go in my opinion

void Delete(node* n)
{
if(!n)
return;

Delete(n->Right);
Delete(n->Left);
delete n;
}

Matt

 

[Zyrenthian]

Ya know... I should really fully read the posts before I post

However, I dont know why it is not deleteing properly for you. Is "Root" a pointer?

 

[Jonsauce]

Okay. I think i went a bit overboard to make sure everything is deleted now, but it definately is.
My naming conventions are REALLY confusing, but here it goes. (Just remember NODE is different than node) node should have actually been named Tree because its a class that constructs and evaluates Expression Trees; eventually Ill change it.

I changed my
struct NODE
{
NODE * Left;
NODE * Right;
char Info;
};

to

class NODE
{
public:
NODE * Left;
NODE * Right;
char Info;
Node()
{
Right = NULL;
Left = NULL;
Info = '\0';
}
~Node()
{
delete Left;
delete Right;
}

}; //end class NODE

I assume that it will go through and delete the right and left nodes, causing the next nodes to also be deleted, though I might run into the problem I had in my -node- class where the root was already deleted by the time i passed it to a function. Ill have to run through some watches in debug mode to check on this.

Then I added a line to my node:eleteTree(NODE * node) function

void node:eleteTree(NODE * Node)
{
if(Node == NULL) //added
return ; //added

if(Node->Left != NULL)
DeleteTree(Node->Left);
if(Node->Right != NULL)
DeleteTree(Node->Right);
delete Node;
Node = NULL;
}

I dont get a memory access violation anymore, but Im not 100% sure that its cleaning out all the spots. Ill have to run through some more debugging stuff before I get it for sure. I probably wouldnt have ever thought of this w/ out your guys' help, so thanks!