Delete all from a Binary Tree

This is a discussion on Delete all from a Binary Tree within the C Programming forums, part of the General Programming Boards category; Hi to all. I'm new to this board (and to C code) but have gone through some of the tutorials ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Location
    Sunny, Malta in the Mediterranean
    Posts
    9

    Unhappy 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.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    void freetree( struct node *tree )
    {
        if( tree )
        {
            if( tree->left )
            {
                freetree( tree->left )
            }
            if( tree->right )
            {
                freetree( tree->right )
            }
            free( tree );
        }
    }
    You should always check a pointer for NULL before you start fiddling with it. Not at the end.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Apr 2009
    Location
    Sunny, Malta in the Mediterranean
    Posts
    9
    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.

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    7
    Try doing this,

    tree = NULL;

    immediately after the free(tree); statment

  5. #5
    Registered User
    Join Date
    Apr 2009
    Location
    Sunny, Malta in the Mediterranean
    Posts
    9
    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);
        }
    }

  6. #6
    Registered User
    Join Date
    Apr 2009
    Location
    Sunny, Malta in the Mediterranean
    Posts
    9
    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);
        }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Binary Search Tree Delete Method
    By pobri19 in forum C# Programming
    Replies: 2
    Last Post: 09-26-2008, 09:43 AM
  3. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  4. delete node for a binary tree
    By AmazingRando in forum C Programming
    Replies: 4
    Last Post: 10-27-2003, 09:45 PM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21