Home     My Faqts     Contributors     About     Help    

faqts : Computers : Programming : Algorithms : Datastructure : Graph : Tree : Binary tree

FAQTs repaired & updated!
Thanks for your patience...
Entry Add Entry Alert - Edit this Entry

Did You Find This Entry Useful?

5 of 5 people (100%) answered Yes
Recently 5 of 5 people (100%) answered Yes

Datastructure: Tree: Binary: Print: Upright: Pretty: How to pretty print a binary tree upright?

Oct 28th, 2003 14:43

Knud van Eeden


----------------------------------------------------------------------
--- Knud van Eeden --- 25 October 2003 - 07:56 am --------------------
Datastructure: Tree: Binary: Print: Upright: Pretty: How to pretty 
print a binary tree upright?
---
Method: Overview:
The preferred method is currently the following:
 1. given a binary tree
 2. this given binary tree will be printed in a rectangular area on
    your computer screen
 3. therefore you need to know the horizontal x and vertical y
    coordinate of each of the strings in the given binary tree, to be
    able to print that string on the correct position within that
    rectangular area on your screen (or paper).
 4. use 2 passes to pretty print this binary tree upright
 5. in the first pass you do an inorder traversal of the given binary
    tree
    1. While traversing, from left to right, you store a pointer to the
       current node, in a rectangular array
    2. While traversing, you store the current sum of the lengths of
       all the strings on the left of the current node, to be able to
       know the x-position later.
  6. in the second pass you go systematically row by row, and from left
     to right, through the rectangular array in which you stored your
     binary tree during inorder traversal.
     1. if you find a non empty element on that row it is per
        definition a parent of some childs on the row below
        1. then scan the row below for the children of this parents
           1. from left to right you go through the row below. If you
              find a non empty element, you get its pointer.
           2. to know if it is a child of the current parent in the row
              above, you check if the left pointer or right pointer of
              the current child element is equal to the pointer of that
              parent
              1. each parent has between 0, 1 and 2 children per
                 definition in a binary tree
              2. all children of parents on a given row, will be
                 situated on one and the same row below.
                 Thus if you scan 1 row from left to right you
                 will find all children.
              3. in a binary tree, children of a parent will be next to
                 each other on the row below.
              4. so you can systematically and independently of the
                 other (because the parent and the children are all on
                 the left together) from left to right, find the
                 parent, its 0, 1, 2 children, and draw connection
                 lines between them
              5. if a child is found, then draw some connection lines
                 between parent and child
        2. because of the printhead can not return, you have to work
           and repeat the steps for each single horizontal line you are
           printing with your printhead.
           This last step is currently still inefficient, as you have
           to search over and over again for the same information on
           the same row, so you might decide to use some storage
           structure to store this relationship of of parent, children
           and total amount of spaces
---
---
Method: Overview:
The preferred method is currently the following:
 1. given a binary tree
    e.g. 'red + black * blue'
    or thus
                      *
              +         blue
          red   black
    or thus pretty printed
                      *
                      |
              +-------+--+
              |          |
              +         blue
              |
           +--+---+
           |      |
          red   black
 2. this given binary tree will be printed in a rectangular area on
    your computer screen
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | |b|l|u|e|
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        5| | | ||| | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        6| |+|-|+|-|-|+| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        7| ||| | | | ||| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        8|r|e|d| |b|l|a|c|k| | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 3. therefore you need to know the horizontal x and vertical y
    coordinate of each of the strings in the given binary tree, to be
    able to print that string on the correct position within that
    rectangular area on your screen (or paper).
 4. use 2 passes to pretty print this binary tree upright
                      *
                      |
              +-------+--+
              |          |
              +         blue
              |
           +--+---+
           |      |
          red   black
 5. in the FIRST PASS you do an inorder traversal of the given binary
    tree
    An inorder traversal is used because you want here to show the tree
    upright. That means so that you want to see the leftmost node on
    the most left part of the screen, the but leftmost node on the
    butmost left part of the screen, and so on.
                      * 4
                      |
              +-------+--+
              |          |
              + 2       blue 5
              |
           +--+---+
           |      |
        1 red   black 3
    An inorder traversal will visit the nodes in the order:
     1. red -> 2. + -> 3. black -> 4. * -> 5. blue
    During this inorder traversal
    1. Store the found nodes in an array
       1. It is advised not to store the string value of a given node,
          like here:
             node max
             ----------->
           | +-+-+-+-+-+
           | | | | |*| |
           | +-+-+-+-+-+
           | | |+| | |b|
           | +-+-+-+-+-+
           | |r| |b| | |
           | +-+-+-+-+-+
           v
           depth max
          ---
          but instead store a pointer to that node in that array.
          This because if you store only the string, you throw
          information away. In the beginning I only stored the string.
          That works fine for the simplest casess (e.g. when you print
          a binary tree with only 1 character strings inside, but as
          soon as you get longer strings to pretty print, you might
          find out that more information is needed). So soon I realized
          to solve this problem in a general way, so handling mosts
          cases, that I needed more information than that. If you know
          the pointer, you now also which string, you know its left
          child, by checking the left pointer, you know its right
          child, by checking its right pointer and so on.
          So you might find out that you will need that pointer anyhow
          to determine later which the childs of this node are, in
          order to draw connection lines +----+---+ between the parent
          and its 0, 1 or 2 childs.
          ---
          If you have chosen the metod of storing your binary tree in
          an array, so using an array presentation of pointers, you
          might store the given binary tree initially in an array like
          this:
          ---
          Given the binary tree with a pointer at each node showing its
          position in the initial storage array:
                                 * [1]
                                 |
                  +--------------+------+
                  |                     |
                  + [2]                blue [3]
                  |
           +------+------+
           |             |
         red [4]       black [5]
         ---
         Then here is its equivalent representation in the array
         'binary tree as an array representation':
         ---
          +----+-------------+---------+---------------+
          | nr | leftpointer | string  |  rightpointer |
          +----+-------------+---------+---------------+
          +----+-------------+---------+---------------+
          |  1 |       2     | "*"     |         3     |
          +----+-------------+---------+---------------+
          |  2 |       4     | "+"     |         5     |
          +----+-------------+---------+---------------+
          |  3 |      -1     | "blue"  |        -1     |
          +----+-------------+---------+---------------+
          |  4 |      -1     | "red"   |        -1     |
          +----+-------------+---------+---------------+
          |  5 |      -1     | "black" |        -1     |
          +----+-------------+---------+---------------+
         ---
         So in the temporary printing storage array, you do not store
         the string itself (e.g. 'blue, red, black, ...), but so its
         pointer (or thus in an array representation of the pointers, 
you
         store the ROW number of the initial storage array here).
         That gives you much more information which is needed later
         when you have to print out the binary tree in the second pass.
         ---
         While traversing, from left to right, you store a pointer to 
the
         current node, in a rectangular array
         So store the tree during the inorder traversal like this,
         by looking at the position of that given node in the
         array 'binary tree as an array representation' above,
         and putting that number (e.g. 1 for '*', 2 for '+',
         3 for 'blue', 4 for 'red', 5 for 'black') in the correct
         x position (as determined by a counter for the total amount of
         nodes currently processed), and y position as determined by
         the current depth of the tree currently processed) encountered
         during inorder traversal in the temporary print storage array
           node max
           ----------->
         | +-+-+-+-+-+
         | | | | |1| |
         | +-+-+-+-+-+
         | | |2| | |3|
         | +-+-+-+-+-+
         | |4| |5| | |
         v +-+-+-+-+-+
         depth max
      2. To get the vertical y position of the string to be printed
         Its vertical y position is determined by the depth of the
         given tree.
         And this information you store in the temporary array, as you
         store the information of that node precisely on that vertical
         row.
         So by going through that temporary storage array later using
         e.g. a double for next loop (for row=rowmin to rowmax, for
         column=columnmin to columnmax), you know for each element in
         that array its y position, and so you know on which line on
         the screen you have to print that node.
      3. To get the horizontal x position of the string to be printed
         Use the observation that an inorder traversal gives as an
         endresult the vertical projection of the given nodes of the
         given binary tree on an horizontal line. And this in the
         order from left to right. So also the strings of that binary
         tree are so projected on that horizontal line. So each node
         has all proceding strings projected before it on that
         horizontal line.
         1. To know the x-position of the string on the screen while
            printing, you need to know how much spaces you totally have
            to print on the left of it.
            Therefore you need to know the total length of all the
            strings on the left of a given string in a node.
            The easiest is if you store this information while
            doing this inorder traversal.
         2. While traversing, you store the current sum of the lengths
            of all the strings on the left of the current node, to be
            able to know the x-position later.
         ---
            1. If you store during inorder traversal the sum of the
               lengths of all string before a given node in some global
               variable sum, which is updated during the inorder
               traversal with its current value plus the length of the
               string of the current node.
                 sum = sum + Length( string in current node )
               Because you go during the inorder traversal, per
               definition, through all the nodes from left to right,
               and with no skipping, in the given binary tree, then so
               does this sum variable contain the sum of the lengths of
               all strings in front of that given node.
               And that is exactly what you want to be able to know the
               xposition of any given string in the given binary tree
               on the screen.
         ---
         So given the final output of the upright tree (without the
         connection lines) you determine the x-coordinate of any
         string:
          - by counting the sum of the lengths of all strings on the
            left before it
         ---
         So this will be the final output for the given example:
            0 1 2 3 4 5 6 7 8 9 0 1 2 3
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
           | | | | | | | | | |*| | | | |
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
           | | | |+| | | | | | |b|l|u|e|
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
           |r|e|d| |b|l|a|c|k| | | | | |
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         So,
         the horizontal x-position of the string 'red' is 0
         (or thus the sum of the length of all strings on the left
          of 'red', which is none, thus "", with a length of 0, thus
          totally 0)
         the horizontal x-position of the string '+' is 3
         (or thus the sum of the length of all strings on the left
          of '+', which is 'red', with a length of 3, thus totally 3)
         the horizontal x-position of the string 'black' is 4
         (or thus the sum of the length of all strings on the left
          of 'black', which is 'red', and '+', with a length of 3 and
          1, thus totally 4)
         the horizontal x-position of the string '*' is 9 (or thus the
         sum of the length of all strings on the left of '*', which is
         'red', and '+' and 'black', with a length of 3, 1, and 5 thus
         totally 9)
         the horizontal x-position of the string 'blue' is 10 (or thus
         the sum of the length of all strings on the left of '*', which
         is 'red', and '+' and 'black' and '*', with a length of 3, 1,
         5, and 1 thus totally 10)
         ---
         You will find out that you can do that easy during the
         left to right inorder traversal of the binary tree.
         As you work during an inorder traversal systematically from
         left to right, through all nodes, you meet so first all nodes
         on the left of any given node first. So you can store the
         inbetween sum of the lengths of the strings of that nodes in a
         global variable.
         So you can store for later use this x-position for
         all the nodes in another array
          +----+----------------------------------------------------+
          | nr | sum length of all strings to the left current node |
          +----+----------------------------------------------------+
          +----+----------------------------------------------------+
          |  1 | 9        (=total amount of spaces before '*')      |
          +----+----------------------------------------------------+
          |  2 | 3        (=total amount of spaces before '+')      |
          +----+----------------------------------------------------+
          |  3 | 10       (=total amount of spaces before 'blue')   |
          +----+----------------------------------------------------+
          |  4 | 0        (=total amount of spaces before 'red')    |
          +----+----------------------------------------------------+
          |  5 | 4        (=total amount of spaces before 'black')  |
          +----+----------------------------------------------------+
  6. in the SECOND PASS you go systematically row by row, and from left
     to right, through the rectangular array in which you stored your
     binary tree during inorder traversal.
           node max
           ----------->
         | +-+-+-+-+-+
         | | | | |1| |
         | +-+-+-+-+-+
         | | |2| | |3|
         | +-+-+-+-+-+
         | |4| |5| | |
         v +-+-+-+-+-+
         depth max
     1. if you find a non empty element on that row it is per
        definition a parent of some childs on the row below
             node max
             ----------->
           | +-+-+-+-+-+
           | | | | |1| |
           | +-+-+-+-+-+
             +-+-+-+-+-+
           | | |2| | |3|
           | +-+-+-+-+-+
           | |4| |5| | |
           v +-+-+-+-+-+
           depth max
           For example node 1 is the parent of the children 2 and 3
           in the row below.
        1. then scan the row below for the children of this parents
           1. to know if it is a child of the current parent in the row
              above, you check if the left pointer or right pointer of
              the current child element is equal to the pointer of that
              parent
              1. each parent has between 0, 1 and 2 children per
                 definition in a binary tree
              2. all children of parents on a given row, will be
                 situated on one and the same row below, by definition
                 in this rectangular array representation.
                 Thus if you scan 1 row below, from left to right, you
                 are sure you will find all children that given parent.
                 That comes handy for drawing the connection lines.
                 Because that asks for the x coordinate of the parent,
                 the x coordinate of the left child and the x
                 coordinate of the right child.
              3. in a binary tree, children of a parent will be next to
                 each other on the row below.
              4. so you can systematically and independently of the
                 other (because the parent and the children are all on
                 the left together) from left to right, find the
                 parent, its 0, 1, 2 children, and draw connection
                 lines between them
              5. if a child is found, then draw some connection lines
                 between parent and child
           2. from left to right you go through the row below. If you
              find a non empty element, you get its pointer.
              For example:
                  +-+-+-+-+-+
                  | | | |1| |
                  +-+-+-+-+-+
              Starting with node 1 on the first row.
              You determine its up to 2 children, by noting
              the value of the left pointer of parent node 1.
              That gives the pointer to the left child.
              And the value of the right pointer of node 1.
              That gives the pointer to the right child.
              Here these values are 2 and 3.
              You then check the non empty cells in the row below,
              working from left to right horizontally.
              First you find 2. Is that a child of that parent 1?
              Yes, because the left pointer of that parent equals 2.
              Then you find 3. Is that a child of that parent 1?
              Yes, because the right pointer of that parent equals 3.
                  +-+-+-+-+-+
                  | |2| | |3|
                  +-+-+-+-+-+
                  |4| |5| | |
                  +-+-+-+-+-+
        2. Now printing the found results, using the found x-
coordinates
           of the parent and the x-coordinates of the left child and
           the right child
           There is some complication, and also limitation built in,
           because of the 'printhead' can not return, you have to work
           and repeat the steps for each single horizontal line you are
           printing with your printhead.
           As the arbitrary constraint is used that the printhead can
           only move from the left to the right and from top to bottom,
           but can not move backwards in order to be as general as
           possible, you will have to do the actions for all children
           and parents AT ONCE, from left to right, while you are
           on a given row.
           This last step is currently still inefficient, as you have
           to search over and over again (here 3 times, for each
           vertical connection line you draw) for the same information
           on the same row, to find the x-position of the parents, so
           you might decide to use some storage structure to store this
           relationship of of parent, children and total amount of
           spaces
           1. You draw some arbitrary connection lines between 1
              given parent and up 2 childs.
              Here is chosen a connection like the following:
                              |
                       +------+---+
                       |          |
              You analyze drawing this structure, by breaking it
              in 3 parts vertically, that is one part for each
              of the 3 horizontal lines:
              On each vertical line, you can draw this figure with
              minimal input:
              1. the x-coordinate of the parent
              2. the x-coordinate of the left child
              3. the x-coordinate of the right child
              In order to be able to make the connection in say
              the symmetric middle of any given string, you will
              also need the length of this string.
              4. the length of the string of the parent
              2. the length of the string of the left child
              3. the length of the string of the right child
              So in this simplest case of showing a nice pretty print
              result, you can draw the connection
                              |
                       +------+---+
                       |          |
              like this below:             .
                                           ..............>
                      .                    . length parent
                      .                    .
                      .                    .
                      .....................>[stringparent]
                      . x-parent                   |
                      .                    +-------+-----------+
                      .                    |                   |
                      ...............>[stringleft]       [stringright]
                      . x-left child .                   .
                      .              ............>       ............>
                      .               length left        .length right
                      .                                  .
                      ..................................>.
                      . x-right child
                      .
               So to draw this structure,
                              |
                       +------+---+
                       |          |
               you can split it in 3 steps, by going through this 
structure
               from row to row vertically down:
               First you draw one the first horizontal line
                             '|'
               Then you go one line down, and you draw
                      '+------+---+'
               Then you go one line down, and you draw
                      '|          |'
               ---
               Working this out:
               1. First print a character '|' at x-position middle of 
the parent string,
               or thus at x-position xparent + half of the (length 
parent string)
               2. Then print a string '+------+---+'
                  1. starting by printing a '+' followed by a number of
                     hyphens '-', and a '+' at the end, thus '+------+'
                     and print this at x-position middle of the left
                     string, or thus at x-position xchild + half of the
                     (length left child string)
                     until you reach the middle of the parent string
                  2. continue with printing a '+', followed by a 
number of
                     hyphens '-', thus '+---+'
                     starting at x-position middle of the parent,
                     or thus at x-position xchild + half of the (length
                     left child string)
  7. Working all this ideas out for the given example:
     1. Given an expression
         e.g. 'red + black * blue'
     2. This expression shown as a binary tree
                        *
                +         blue
            red   black
     3, This binary tree is represented in memory in the following
        datastructure
           +----+-------------+---------+---------------+
           | nr | leftpointer | string  |  rightpointer |
           +----+-------------+---------+---------------+
         | +----+-------------+---------+---------------+
         | |  1 |       2     | "*"     |         3     |
         | +----+-------------+---------+---------------+
         | |  2 |       4     | "+"     |         5     |
         | +----+-------------+---------+---------------+
         | |  3 |      -1     | "blue"  |        -1     |
         | +----+-------------+---------+---------------+
         | |  4 |      -1     | "red"   |        -1     |
         | +----+-------------+---------+---------------+
         | |  5 |      -1     | "black" |        -1     |
         | +----+-------------+---------+---------------+
         V  node max
     3. After doing the inorder traversal, pointers to your binary
        tree are stored in a temporary array
           node max
           ----------->
         | +-+-+-+-+-+
         | | | | |1| |
         | +-+-+-+-+-+
         | | |2| | |3|
         | +-+-+-+-+-+
         | |4| |5| | |
         | +-+-+-+-+-+
         V depth max
     4. Also stored are the x-positions of each node
          +----+----------------------------------------------------+
          | nr | sum length of all strings to the left current node |
          +----+----------------------------------------------------+
          +----+----------------------------------------------------+
        | |  1 | 9        (=total amount of spaces before '*')      |
        | +----+----------------------------------------------------+
        | |  2 | 3        (=total amount of spaces before '+')      |
        | +----+----------------------------------------------------+
        | |  3 | 10       (=total amount of spaces before 'blue')   |
        | +----+----------------------------------------------------+
        | |  4 | 0        (=total amount of spaces before 'red')    |
        | +----+----------------------------------------------------+
        | |  5 | 4        (=total amount of spaces before 'black')  |
        | +----+----------------------------------------------------+
        V  node max
      5. Using the temporary array as a guide
           node max
           ----------->
         | +-+-+-+-+-+
         | | | | |1| |
         | +-+-+-+-+-+
         | | |2| | |3|
         | +-+-+-+-+-+
         | |4| |5| | |
         | +-+-+-+-+-+
         V depth max
        You start building the final to be printed rectangular array:
        First row one
           +-+-+-+-+-+
           | | | |1| |
           +-+-+-+-+-+
        You find pointer 1.
        You get the xposition of this node, by looking in step 4 in row
        1. That shows 9 spaces to be printed.
        Get also the string belonging to pointer 1.
        You get that by using pointer 1, and going to row 1
        in table in step 3, and taking the string out there.
        That gives you '*'.
        So print this '*' on x-position 9
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        As you are completely finished with the current horizontal
        line, you can move your 'printhead' to the next line below.
        Now for each of all of the parents of this line, draw a
        connection line '|' (while staying on the same horizontal line)
        between the parents and its childs.
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        As you are completely finished with the current horizontal
        line, you can move your 'printhead' to the next line below.
        Now for each of all of the parents of this line, draw a
        connection line '+---+--+' (while staying on the same
        horizontal line) between the parents and its childs
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        As you are completely finished with the current horizontal
        line, you can move your 'printhead' to the next line below.
        Now for each of all of the parents of this line, draw a
        connection line '|' (while staying on the same
        horizontal line) between the parents and its childs
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        ---
        You are finished with row 1 in the temporary array.
        So goto row 2. in the temporary array
         +-+-+-+-+-+
         | |2| | |3|
         +-+-+-+-+-+
        You find first pointer 2.
        You get the xposition of this node, by looking in step 4 in
        row 2. That shows 3 spaces to be printed.
        Get also the string belonging to pointer 2.
        You get that by using pointer 2, and going to row 2
        in table in step 3, and taking the string out there.
        That gives you '+'.
        So print this '+' on x-position 3
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        Then you find pointer 2.
        You get the xposition of this node, by looking in step 4 in
        row 3. That shows 10 spaces to be printed.
        Get also the string belonging to pointer 3.
        You get that by using pointer 3, and going to row 3
        in table in step 3, and taking the string out there.
        That gives you 'blue'.
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | |b|l|u|e|
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        Now you are finished with this horizontal line,
        you can move your 'printhead' to the next line
        Now for each of all of the parents of this line, draw a
        connection line '|' (while staying on the same horizontal line)
        between the parents and its childs.
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | |b|l|u|e|
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        5| | | ||| | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        As you are completely finished with the current horizontal
        line, you can move your 'printhead' to the next line below.
        Now for each of all of the parents of this line, draw a
        connection line '+---+--+' (while staying on the same
        horizontal line) between the parents and its childs
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | |b|l|u|e|
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        5| | | ||| | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        6| |+|-|+|-|-|+| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        As you are completely finished with the current horizontal
        line, you can move your 'printhead' to the next line below.
        Now for each of all of the parents of this line, draw a
        connection line '|' (while staying on the same
        horizontal line) between the parents and its childs
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | |b|l|u|e|
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        5| | | ||| | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        6| |+|-|+|-|-|+| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        7| ||| | | | ||| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        ---
        You are finished with row 2 in the temporary array.
        So goto row 3. in the temporary array
           +-+-+-+-+-+
           |4| |5| | |
           +-+-+-+-+-+
        You find first pointer 4.
        You get the xposition of this node, by looking in step 4 in
        row 4. That shows 0 spaces to be printed.
        Get also the string belonging to pointer 24.
        You get that by using pointer 4, and going to row 4
        in table in step 3, and taking the string out there.
        That gives you 'red'.
        So print this 'red' on x-position 0
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | |b|l|u|e|
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        5| | | ||| | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        6| |+|-|+|-|-|+| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        7| ||| | | | ||| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        8|r|e|d| | | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        Then you find pointer 5.
        You get the xposition of this node, by looking in step 4 in
        row 5. That shows 4 spaces to be printed.
        Get also the string belonging to pointer 5.
        You get that by using pointer 5, and going to row 5
        in table in step 3, and taking the string out there.
        That gives you 'black'.
          0 1 2 3 4 5 6 7 8 9 0 1 2 3
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        0| | | | | | | | | |*| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        1| | | | | | | | | ||| | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        2| | | |+|-|-|-|-|-|+|-|+| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        3| | | ||| | | | | | | ||| | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        4| | | |+| | | | | | |b|l|u|e|
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        5| | | ||| | | | | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        6| |+|-|+|-|-|+| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        7| ||| | | | ||| | | | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        8|r|e|d| |b|l|a|c|k| | | | | |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        Now you are finished with this horizontal line,
        you can move your 'printhead' to the next line
        As you are on the last line, so
        per definition you have no more
        lines below, thus no more childs
        to check for, you are ready.
      or thus pretty printed
                     *
                     |
               +-----+-+
               |       |
               +      blue
               |
             +-+--+
             |    |
            red black
---
---
Note: This 2 pass process is also a kind of a pattern, as you use the
same method to run through the data of creating a graph to determine
the minimum and maximum values, after which you can  scale that graph
correctly in the second pass.
---
So you might generalize this idea in saying:
Given any graphical representation which needs some kind of a
transformation (e.g. scaling) might need 2 passes,
one first pass for determining its scaling information (position,
minimum, maximum, ...),
and the second pass for showing the result of it.
---
---
Internet: see also:
---
BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How print 
binary tree upright? Array: Pretty
http://www.faqts.com/knowledge_base/view.phtml/aid/26049/fid/768
---
BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How print 
binary tree upright? Array: String
http://www.faqts.com/knowledge_base/view.phtml/aid/26033/fid/768
---
Datastructure: Tree: Binary: Print: Upright: How print binary tree 
with strings different lengths?
http://www.faqts.com/knowledge_base/view.phtml/aid/26017/fid/1266
---
Datastructure: Tree: Binary: Print: Upright: How to print a binary 
tree upright?
http://www.faqts.com/knowledge_base/view.phtml/aid/25819/fid/1266
---
Datastructure: Tree: Binary: Traversal: Walk: Order: How to walk in 
order a binary tree?
http://www.faqts.com/knowledge_base/view.phtml/aid/25844/fid/1266
----------------------------------------------------------------------



© 1999-2004 Synop Pty Ltd