#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2013
    Posts
    9
    Rep Power
    0

    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

    20----30
    | |
    10-17 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!
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,960
    Rep Power
    481
    Code:
    20(10(5(*)(*))(17(*)(*)))(30(21(*)(*))
    
    20----30
    |     |
    10-17 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!

IMN logo majestic logo threadwatch logo seochat tools logo