Binary Search Tree Help

[cn2105]

For class we have to create a program that prints a binary tree in vertical, horizontal, and symmetrically based on the given inorder and postorder sequence.

For example given:
Preor. seq.: root thisisverylong short 34 longer aaaaaaaaa bbbbbbb c
Inor. seq. : thisisverylong short root aaaaaaaaa longer bbbbbbb 34 c

Null nodes print
Symmetrical would print something like:

                   _root_
                 /       \
  thisisverylong        _34_
 /              \      /    \
x             short  longer c
                     /   \
              aaaaaaaaa bbbbbbb 

I was just wondering if anyone knew how to add the dashes/lines to the printed output.

[dhayden]

Printing exactly how you've represented it would be hard because line 7 overlaps what is on line 5. But if that isn't needed then it gets a lot easier. The first thing is a separate function that determines the width and height of a printed subtree. Conceptually, every subtree prints inside a rectangle. How wide/tall is that? Next you could create a 2D array of characters for the rectangle that holds the entire printed tree. maybe a vector of strings where each one is initialized to the width of the full printed tree. Finally, call a recursive function that prints a subtree, given the top left corner of the rectangle where it should be printed.