December 8th, 2013, 05:34 PM

Binary trees visualization
I'm new to binary trees and am confused with how to do the following. If you could offer some advice or guidance (in the simplest way to understand), that would be appreciated greatly.
I have the following
20(10(5(*)(*))(17(*)(*)))(30(21(*)(*))(...
I want to write a program that reads in a binary tree in the above form and displays it in a 'friendlier' style
2030
 
1017 21

5
The binary tree is read in using argv[1](this is the string itself, NOT a filename), for example :
% treevis "20(*)(*)"
Could you explain what I have to do for this and how I should go about doing it. My knowledge of trees is very raw at the moment so any advice would be great. Thanks!
December 9th, 2013, 11:11 AM

Code:
20(10(5(*)(*))(17(*)(*)))(30(21(*)(*))
2030
 
1017 21

5
Asterisks represent terminals. Parenthesized groups represent branches. The first branch points down, second branch drawn to the right.
There are several problems to solve. You'll need an algorithm for drawing the tree, you'll need code to parse, store, and traverse the tree. (data structures and algorithms) Draw some trees on paper. What do they look like? How did you decide?
Using D to indicate "down" and R for "right", and hoping I understand your notation and have not made a mistake, draw
Root(D(*)(DR(*)(DRR(*)(*))))(R(RD(RDD(*)(*))(*))(*))
The horizontal or vertical representations are more familiar to me.
Code:
level
0 1 2 3 1 2 3
Root(D(*)(DR(*)(DRR(*)(*))))(R(RD(RDD(*)(*))(*))(*))
Height of tree 4 is, with 0 index origin shown here, one more than maximum level.
Breadth of tree is 2^(Height)1
*
*
*
R
*
RD
RDD
Root
DRR
DR
D
With this strategy and fixed width labels the tree depth determines the label positions. I've used variable length stems. I see your diagonal layout with positions chosen in local polar coordinate systems, halving angles at successive levels. The alternative layout avoids the uncomfortable problem of mapping transcendental numbers to integral character cell sized rectangular coordinates.
Other solutions. Consider the binary tree as a graph: convert the input to be appropriate for graphviz rendering; assign each node a charge, the links as springs, and solve the statics problem to place labels.
Last edited by b49P23TIvg; December 9th, 2013 at 12:40 PM.
[code]
Code tags[/code] are essential for python code and Makefiles!