Thread: Delete all from a Binary Tree

Hi to all.
I'm new to this board (and to C code) but have gone through some of the tutorials of the site and searched the board for relevant tips to my problem.

I'm trying to write an implemenation of an unbalanced binary search tree. I have most of the basic functions working like create tree, attach new nodes, search and tree traversal in pre-order form. I'm trying to write a delete function that deletes all nodes including the root if necessary. The same function will be used to delete whole branches of the tree also. I am passing the killTree function a node and the code is something like this:

Code:

typedef struct Node NODE;

// Global variables.
HANDLE gHeap;
NODE* gRoot; // the root node
NODE* tempN;

// Node is a Struct containing 3 members.
struct Node
{
    int    valKey;            // holds the node's data or key
    struct Node* Left;   // pointer to left subtree
    struct Node* Right; // pointer to left subtree
};

other code.......

void killTree(NODE* kNode)
{
   if (kNode->Left != NULL)
         {
         killTree(kNode->Left);
         }
   if (kNode->Right != NULL)
         {
         killTree(kNode->Right);
         }
   if (kNode != NULL)
         {
         HeapFree(gHeap, 0, kNode);
         }
}

void destroyMemory()
{
    HeapDestroy(gHeap);
    gHeap = NULL;
    gRoot = NULL;
} 

void PrintRoot(NODE* gRoot)
{
    if (gRoot == NULL)
    {
    printf ("The root of the tree is:%i\n",gRoot->valKey);
    }
}

When debugging with line by line I get an access violation error with Dev-C++ and a SIGSEV with Code::Blocks after running through all the code and try to print the root again to see if the funciton has worked. I tried the latter as I was noticing the CPU going to 98% after a few runs of the program and thought it could be some problem due to the awful code I'm writing.

I am calling the deleteTree function with deleteTree(gRoot) and then destroyMemory().
This code will be sort of temporary as in the end it will be compiled as a DLL exposing the functions to a C# "frontend".

Any form of help or tips of how to go about doing this would be greatly appreciated. Thanks.

Thanks Quzah for your reply.

I tried the code and still came up with a Windows error. Compiling all the code is ok but when it is Run I get a **.exe has stopped working error with the usual Vista messages to check online fo a solution, close the program etc.

I called the freeTree function with gRoot (the global variable holding the root node). When I followed the execution line by line in debug the execution stopped when the line of free(tree) was executed. Am I passing the wrong parameter to the freetree function by giving it the gRoot variable? Thanks again for any tips you may provide.

Try doing this,

tree = NULL;

immediately after the free(tree); statment

Thanks but I had tried that already and I still got that error.

I changed a little the freetree function and instead of using free(tree) I used Heapfree. Now the code runs ok but when I try to print the root to check if it's empty (a needed option in the assignment I have) I get a large number (for example 3278912).

This is what the functon looks like now

Code:

void freeTree (struct Node *tree)
{
    if (tree)
    {
        if (tree->Left)
        {
            freeTree (tree->Left);
        }
        if (tree->Right)
        {
            freeTree (tree->Right);
        }
        
        HeapFree (gHeap, 0, tree);
    }
}

I am calling the function from Main with freeTree(gRoot);

This is the printRoot function:

Code:

// Prints the root 0
void PrintRoot(NODE* gRoot)
{
    if (gHeap == NULL)
    //if (gRoot == NULL)
    {
    printf ("The tree is empty\n");
    }
    else
    {
    printf ("The root is %d\n",gRoot->valKey);
    }
}

I have edited the printRoot function and now it gives the required output.

Code:

void PrintRoot (NODE* pNode)
{
    pNode = gRoot;
    if (pNode == NULL)
    {
    printf ("\nThe tree is empty\n");
    }
    else
    {
    printf ("\nThe root is %d\n",pNode->valKey);
    }
}