deleting all nodes of a binary search tree...

This is a discussion on deleting all nodes of a binary search tree... within the C++ Programming forums, part of the General Programming Boards category; to delete all the nodes of a binary search tree (using the 'post order traversal") i have used the following ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    7

    deleting all nodes of a binary search tree...

    to delete all the nodes of a binary search tree (using the 'post order traversal") i have used the following coding...
    even though it does delete all the nodes of the binary search tree, it gives an error at the end...
    so i want to know if my coding is correct..

    void tree::deleteAll(Node* localRoot)
    {
    if(localRoot !=NULL)
    {
    deleteAll(localRoot->leftChild);
    deleteAll(localRoot->rightChild);
    delete localRoot;
    }
    }

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    what is the error that you are getting?

    edit:: you should also check if localRoot->(left or right)child is a null, before deleting it.
    Last edited by axon; 09-28-2004 at 11:43 PM.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    this is a pretty standard implementation of a recursive freeing of a BST:
    Code:
    freeBST( Node* t ) //get root
    {
     	if( t == NULL ) 
    		return;
    	if( t->leftChild != NULL )
    		freeBST( t->leftChild );
    	if( t->rightChild != NULL )
    		freeBST( t->rightChild );
    	
    	delete t; 		/* free(t) if c */
    	
    	return;
    }

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >edit:: you should also check if localRoot->(left or right)child is a null, before deleting it.
    He does, that is the base case for the recursion.

    >this is a pretty standard implementation of a recursive freeing of a BST
    Umm...not really.

    >freeBST( Node* t ) //get root
    You forgot the return value, and the comment is just obscure.

    >if( t->leftChild != NULL )
    >freeBST( t->leftChild );
    There's no need for this test if you return when t is a null pointer.

    >if( t->rightChild != NULL )
    >freeBST( t->rightChild );
    Ditto

    >delete t; /* free(t) if c */
    Free t if c? What is that supposed to mean?

    Recursive post order traversal usually takes one of these two forms:
    Code:
    void delete_all ( struct node *tree )
    {
      if ( tree == NULL )
        return;
    
      delete_all ( tree->left );
      delete_all ( tree->right );
      delete tree;
    }
    Code:
    void delete_all ( struct node *tree )
    {
      if ( tree != NULL ) {
        delete_all ( tree->left );
        delete_all ( tree->right );
        delete tree;
      }
    }
    The OP's code conforms to the second, so the function is correct and we can conclude that the problem is elsewhere.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Searching a binary search tree - doesn't work
    By Ariod in forum C Programming
    Replies: 1
    Last Post: 08-11-2005, 03:53 PM
  2. Binary Tree Search
    By nickname_changed in forum C++ Programming
    Replies: 7
    Last Post: 01-12-2004, 11:40 PM
  3. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 01:51 PM
  4. Inserting words into a binary search tree
    By lime in forum C Programming
    Replies: 9
    Last Post: 08-02-2003, 10:02 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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