|
|
Home My Faqts Contributors About Help |
| Entry | Add Entry Alert - Edit this Entry |
Oct 28th, 2003 14:43
----------------------------------------------------------------------
--- Knud van Eeden --- 25 October 2020 - 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