How can I print a Binary Tree Search class Vertically?

Question

I've been learning how to program Binary Tree Search using Linked Lists in C++. Everything works fine and I understand how the Binary Tree works however I would like to be able to print the tree with the head on top and all the nodes following bellow as I try to demonstrate here:

                                     [root or head]
                            [left]                    [right]

                      [left]      [right]       [left]       [right]

I am using the Console to print the tree, therefore feel free to use 'cout' or 'printf'. I believe I need to set the width of the console but I'm not sure how to start.

Thanks, Y_Y

Answer 1

As sbi mentioned, making a left-aligned version is easier than a center-aligned one. But whichever alignment you choose your fundamental algorithmic approach should be:

Traverse the tree breadth-first. Do this by using a queue with the following algorithm:

1. Declare a queue
2. Add the root node to the queue
3. While the queue contains more nodes, do 4 - 6:
4. Dequeue a node
5. Print the node. After every print that is one less than a power of 2th time (starting from 1), also print a newline.
6. Enqueue the node's children

(See http://www.cs.bu.edu/teaching/c/tree/breadth-first/ )

In order to print a center-aligned tree, also do the following (only works if the tree is complete. If it's not complete, the easiest thing to do is make a complete copy where every place that should have a node gets some kind of a null node):

• Instead of printing to the screen, "print" each line into a string in an array of strings.
• As you go, keep track of the length in characters of the longest element you print. Let's call this maxElemLen.
• Whenever you print an element, print one tab character before it and one tab character after it.
• At the very end, go back, and in every line in the array, replace each tab character with 2^(nLines - lineNum) tab characters.
• Then expand each tab that comes after a tab or newline to maxElemLen+1 spaces, and expand each tab that comes after anything else (i.e., after a printed elem) to (maxElemLen + 1 - (the number of characters elapsed since the last tab)) spaces.
• Finally, print each line of your array, in order.