Binary trees

This is a discussion on Binary trees within the C++ Programming forums, part of the General Programming Boards category; Ok I am starting to understand these things now. I read the tutorial on cprogramming.com and basically using their code ...

  1. #1
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972

    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!
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,668
    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

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 PM
  2. Binary Trees
    By wvu2005 in forum C Programming
    Replies: 7
    Last Post: 10-15-2005, 04:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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