Printing binary trees

This is a discussion on Printing binary trees within the C++ Programming forums, part of the General Programming Boards category; I'm planning on writing a program that will display a binary tree of a small height like so: Code: 5 ...

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Printing binary trees

    I'm planning on writing a program that will display a binary tree of a small height like so:
    Code:
                  5
            /            \
          10              11
        /    \          /    \
      3       4        5      1
     / \     / \      / \    / \
    2   6   1   9    6   8  7   6
    The best way I could think of was to place the root in a queue, then loop until the queue is empty placing the left and right children at the end of the queue and then printing and popping the front. Something like:
    Code:
    queue.push(root);
    while (!queue.empty());
    {
        queue.push(front.left);
        queue.push(front.right);
        print front;
        pop front;
    }
    The problem with this idea though is that it doesn't account for empty spots, so would mess up with something like:
    Code:
                  5
            /            \
          10              11
         /                  \
        3                    1
    Any ideas how to get around this? My brain is kinda fried at the moment unfortunately...

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    use recursion to walk the tree....Instructions
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Thanks, I thought about recursion but I don't think it will work to print out the tree like above, since I need to print by height. This means I need to print height 1, then height 2, etc while I figured recursion will print from the bottom up (and I don't want to use gotoxy() ). I want the output to look like a binary tree, not like "1 9 10 6 4 1 16"

  4. #4
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Perhaps you can make a function that adds 'empty' nodes where there aren't be any, then print it in level-order using queues. This may be a workaround though, and probably not the best solution.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  5. #5
    Neoseeker's master master2000's Avatar
    Join Date
    Dec 2002
    Posts
    101

    Unhappy

    What is a binary tree is it like a famaly tree






    master2000 over and out
    missles on metriods

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by master2000
    What is a binary tree is it like a famaly tree
    A binary tree is a tree (cluster of nodes attached to each other in a hiearchical way) where every node has 0, 1 or 2 children (outgoing paths). Not more. The first node is called the root (marked red), the 'last' nodes (the ones who doesn't have any children) are called leaves (marked blue).

    A binary tree is full if all nodes have 0 or 2 children (not 1).

    A binary tree is perfect if all levels are filled with nodes, which is that there are 2^n nodes on the nth's level.

    A binary tree is complete if it is perfect, or perfect on all levels except the last one (and the nodes on the last level is filled from the left or right, not scattered).
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Forgot...
    Attached Images Attached Images  
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Cool Magos, thanks. Maybe instead of using a function, I could push pointers on to the queue, and push NULL if the child doesn't exist and push two NULLS if the front of the queue is NULL. You're right though, this does feel a little hackish, but hey if it works...

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    It worked! I've been learning a lot about how to program binary trees lately (red/black, max heaps, binary search, etc) and it was so hard to see if my functions and tree classes were working properly without being able to see them in tree format. But now its easy!

  10. #10
    Neoseeker's master master2000's Avatar
    Join Date
    Dec 2002
    Posts
    101
    gald to help :rose:
    missles on metriods

Popular pages Recent additions subscribe to a feed

Similar Threads

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

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