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

use recursion to walk the tree....Instructions

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"

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.

What is a binary tree is it like a famaly tree






master2000 over and out

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

Forgot...

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!

gald to help :rose: