Binary trees

Ok I am starting to understand these things now. I read the tutorial on cprogramming.com and basically using their code to create a binary tree I wanted to make a function to print out the binary tree. I got as far as going down the leftmost branches (as far as I could tell since i was using random numbers) but then i got stumped. I can think of ways to do one left and right branch, but then i realize that both those could branch as well...heres a little code:

Code:

void btree:: out(node *leaf)

{

   cout<<"\n"<<"/"<<"\n"<<leaf->key_value;   //add a / above the value...values should decrease going down!

   if (leaf->left!=NULL)
   {
    out(leaf->left);
   }

}

...

 void btree:: out()
 {
 if (root!=NULL)
    out(root);
 else
     cout<<"Error-Must create binary tree first!";
 }


...and calling in main

int main()
{
 int key1=1;
 int cnt=1;
 btree bin1;
while (key1<500)
{
  key1=GetRand(1,500);
  if ((bin1.search(key1))==NULL&&(cnt<500))
     {
     bin1.insert(key1,cnt); //insert random numbers into the tree
     cnt+=1;
     }

}
bin1.out();

  
   getch();
  

return 0;
}

i think i understand this so far...the last output I got was :

Code:

/
468
/
362
/
256
/
242
/
35
/
11

Can someone give me an idea as to how to handle all the branches? Thanks!

You have the right idea. You should explore the right child after you explore the left. If you do that, you will have pre-order traversal implemented.

This site has a neat applet that demonstrates the different traversal orders - all of which can be implemented using recursion.

All the traversal methods will look very similiar, the difference between them will be in what order you explore left, explore right, and print.

gg

If when you print you want it to look like an actual tree (but don't want to use something like gotoxy() ), then you can try what I did. I used a queue that started with the root. From then on, you print the front of the queue while simultaneously pushing the two children of the front onto the back of the queue. If a child is empty, then you push NULL, and if the front of the queue is NULL then you print a blank and add two more NULLS to the end.