tags:

views:

79

answers:

1

Hello,

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

+2  A: 

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.
Jon Rodriguez
Note that the part "After every print that is one less than a power of 2th time (starting from 0), also print a newline." is only correct if the tree is complete. If it is not complete, you need a different way to keep track of when you have finished a level.
Jon Rodriguez
@Jon: What about the requited amount of spaces/tabs, which was the essential part of the question, i guess?
Armen Tsirunyan
@Armen: Isn't that handled in the first sentence.
sbi
@sbi: yeah, after the edit, which happened 3 minutes ago, it is :)
Armen Tsirunyan
@Armen Tsirunyan: There ya go. :-)
Jon Rodriguez
@Armen: From what i can see the first sentence never changed.
sbi
@Jon: Why are you repeating the first part? Did you accidentally mess this up or am I missing something?
sbi
@Jon: (It was me who made this comment.) From here it looks like your answer has three parts, the first two of which are identical.
sbi
@sbi 1) Whoops 2) Whoops. Sorry Armen and thanks sbi. It's 3:18 am here so I must have misread and mistyped.
Jon Rodriguez
I don't understand how to do step 5 from the first portion of the comment...? Can you show me what you mean?
Y_Y
@Y_Y: Have a counter: `int oneMoreThanNNodesPrinted = 1`. In your tree traversal: `print(thisNode); oneMoreThanNNodesPrinted++; int copy = oneMoreThanNNodesPrinted; while(!(copy if (copy == 1) print(newline);`
Jon Rodriguez
@Y_Y: Btw, I just fixed a bug in line 5 by changing "starting from 0" to "starting from 1".
Jon Rodriguez
Thanks for your help.
Y_Y