Thread: 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...

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"

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...

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!