Looking for some guidelines to traverse a binary tree and delete the nodes

[Edward1966]

Hello my name is Edward and I am currently working my final project for Data Structures. I have incorporated linked lists, stacks, queues and binary trees all into one project with a basic theme of procedural and function calls while doing some basic features of each type. My problem is that queues, stacks and linked lists were easy to figure out how to show the calls that were made during the program run like clearing the screen was assigned a "0" for menuCall and then I used for linked lists - menuCallList.insert(menuCall); then I added 1 to the counter for that call (intCount0) then when I was printing out the report it said by cout << "Clearing the screen was called " << intCount0;. Ok now I programmed the function for the report to get the total number of calls for each call like this - if(tempList.front->data == 0) //add 1 to counter then remove the node. Now when I am trying to do something similar for binary trees I have become stumped and can't think of any way to do this. Anyone have some suggestions on how I might do this? If you need to see my code let me know and I'll post it or send it your way. Any help will greatly be appreciated.

[Corpus]

Slow down...what are you trying to do? Do you wish to print the number of function calls you make when traversing your tree?

I'll be happy to help, but I do not understand your question..

/Troels

[helios]

Well, I lost myself in a sea of words, so I'm going to answer the title of the thread.
There are two ways to traverse trees (that I know of, anyway): depth-first, and breadth-first.
Depth-first goes like this:

void df(
		/*
		Your paramenters here. For example, if you want to put the nodes in a
		linear structure, you could pass a pointer to a vector.
		*/
		){
	if (this->branchA)
		this->branchA->df(/*params*/);
	if (this->branchB)
		this->branchB->df(/*params*/);
}

I can't remember breadth-first very well. You can find some pseud-code on Wikipedia: http://en.wikipedia.org/wiki/Breadth-first_search

[Corpus]

helios: I think you are mixing graph traversal (BFS and DFS) and tree traversal. Yes, a tree is a graph, but generally there are three (very closely related) ways to traverse a tree: pre-order, in-order, and post-order. They differ only in when you do your node processing, if any.

Edward: If you wish to traverse a tree and delete the nodes on the way, my best bet is to do a post-order traversal and delete the nodes from the bottom up. Something like:

// PRECOND: node points to a node in a binary tree
// POSTCOND: all nodes "below" node and node itself have been deleted (deallocated)
void deleteTree(Node* node)
{
  if(node==null) return;
  deleteTree(node->left);
  deleteTree(node->right);
  // INVARIANT: node now has no children - we may delete it.
  delete this;
}

Hope this makes sense to you, otherwise repost

/Troels

[Edward1966]

Corpus:

Yes I am trying to print the calls that are made from the tree part of my program. This is a segment of code from the tree function call of my program:

  cin >> number;
						
  menuCall = 38;                    //this is a call to get user's response
							
  menuCallQueue.addQueue(menuCall); //add this to the queue 
							
  menuCallTree.insert(menuCall);    //add this to the menuCallTree  
                                                                      //tree   

Then this is from the call from the show call function of the tree:

    while(!tempTree.isEmpty())        //the calls stops here due to calculating 
                                                       //frequency of calls
   {
							
           if(tempTree.root->info == 0 )				
           {
	countCall0++;             //add 1 to the call 0 counter 
                tempTree.deleteNode();  //delete the first element of the tree
						
            }//end if 

This is for each counter for each call made during the program run. My problem as I was thinking last night was how to delete the nodes after I read them should I traverse the left side first all the way to the bottom of left tree side starting with the leaf nodes (if(tempTree.current->llink == NULL)) then delete that specific node and then start to work upwards towards the root node. then do the right side and finally the node or should I use the calls for post and preorder traversal and follow the paths as those functions are defined. I don't know if I am coming across clear enough. Sorry for the code snippits because I don't know how to do the tags. Also with my project, I don't allow for duplicates in the tree so the counter would have to be set up like if(intCount0 >= 1) then print call to clear the screen was called x times and similar to other calls made.

I am using root because that was declared in the beginning of my main as this statement says:

//set up a tree node to use in the binary tree sub menu

    nodeTypeTree<int> *root = new nodeTypeTree<int>;
    nodeTypeTree<int> *curr = new nodeTypeTree<int>;

then I was going to set curr equal to root by saying curr = root;

then call to delete the node that curr points to. Would this work?

[Edward1966]

Corpus or anyone who might be able to help. I posted some of the code that is giving me some problems to a free site where you can , if you want to , download it or otherwise just browse the code. The link is http://pastebin.com/m4dc62f4e. What I am trying to do is count the number of times a bunch of calls are made and then print them out as a report (as seen by the submenu call to 'G' in this link above).

[Corpus]

Hi Edward

Sorry, been hung up. I have looked at your referenced code on pastebin. First off, here is some advice to make your code a little more reusable - it is not necessary for it to work, but please consider it.

(1) Put your call counters in an array. In this way, lines 84-764 in your program can be replaced by

countCall[tempTree.current->info]++;
tempTree.deleteTree(root);//delete the first element of the queue 

(2) Use named constants instead of magic numbers in your code.

I don't mean to flame you, this is hard-earned experience! If you come back to this program in 6 months you will have no idea what the program is doing and it is very hard to extend.

Now, for the question:

My problem as I was thinking last night was how to delete the nodes after I read them should I traverse the left side first all the way to the bottom of left tree side starting with the leaf nodes (if(tempTree.current->llink == NULL)) then delete that specific node and then start to work upwards towards the root node. then do the right side and finally the node...

Yes. Exactly. Work your way down the left branch with recursive calls. Delete on the way back. Repeat for the right subtree. Then, finally, delete the node itself.

The rationale is: Leaf nodes are safe to delete. When you find a leaf node you will know that it is safe to delete. When you have deleted both the left and right subtrees of a node you will know that the node is now a leaf and hence safe to delete.

Take a look at
the code snippet in my 2nd posting above. It does exactly that :)

/Corpus

[Edward1966]

Thanks Corpus for all your help, your advice really helped. As for using the array I will incorporate it over the break. I have a Linux project to work on and finish by Sunday. Thanks again for your help and hope you have a Merry Christmas and a safe holiday.