Entry
Datastructure: Tree: Binary: Print: Upright: How to print a binary tree upright? Rotate right
Feb 5th, 2005 12:12
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 23 October 2003 - 11:31 pm --------------------
Datastructure: Tree: Binary: Print: Upright: How to print a binary
tree upright? Rotate right
---
Method: Rotate over 90 degrees: Worked out:
So one method would be to print the tree sideways
(which is just a vertical tree rotated 90 degrees
to the left), and when you are finished, you
rotate it 90 degree to the right (so that it is
upright).
---
So the key to easy upright printing is to make 2 passes.
1. The first pass determines the x, y position of the node
1. you store this x,y position e.g. in an array
x y value
2. The second pass reads the x, y coordinates and value from the array
and puts this in the correct 90 degrees anticlockwise rotated
position
---
---
Steps:
1. the easy sideways 'horizontal tree'
2. Use the 2D rotation transformation for anticlockwise rotation:
In general:
xnew = cos( rotationangle ) . xold + sin( rotationangle ) . yold
ynew = - sin( rotationangle ) . xold + cos ( rotationangle ) . yold
3. In the special case that the rotationangle is ninety degrees,
you have in that case that
rotationangle = 90 degrees
thus cos( 90 degrees ) = 0
sin( 90 degrees ) = 1
4. Fill in step 3. in step 2, that gives:
xnew = 0 . xold + 1 . yold
ynew = -1. xold + 0 . yold
5. So step 4. simplifies to:
xnew = yold
ynew = -xold
6. Thus to rotate the 'easy' tree upwards over 90 degrees,for each of
your
( xold, yold ) coordinates in that rectangle around the old tree,
you write it instead as ( yold, -xold ), and print that instead on
the screen.
7. Now working this idea out:
8. So that means that you could draw a rectangle around your old 'easy'
tree
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
| in this area your | |
+--+--+--+--+--+--+--+--+
| |easy tree is drawn |
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
9. You divide this rectangle in smaller rectangles with height 1 and
breadth 1.
xminI,yminI
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
| | | | | | | | |
+--+--+--+--+--+--+--+--+
xmaxI,ymaxI
10. Here an example of the binary tree for '3 + 4 * 5' sideways printed
1. the binary tree '3 + 4 * 5' put sideways in this rectangle:
xminI,yminI
+--+--+--+--+--+--+--+--+
| |5 | | | | | | |
+--+--+--+--+--+--+--+--+
|* | | | | | | | |
+--+--+--+--+--+--+--+--+
| | |4 | | | | | |
+--+--+--+--+--+--+--+--+
| |+ | | | | | | |
+--+--+--+--+--+--+--+--+
| | |3 | | | | | |
+--+--+--+--+--+--+--+--+
xmaxI,ymaxI
2. And here with the coordinates on the sides
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+--+--+--+
1 | |5 | | | | | | |
+--+--+--+--+--+--+--+--+
2 |* | | | | | | | |
+--+--+--+--+--+--+--+--+
3 | | |4 | | | | | |
+--+--+--+--+--+--+--+--+
4 | |+ | | | | | | |
+--+--+--+--+--+--+--+--+
5 | | |3 | | | | | |
+--+--+--+--+--+--+--+--+
|
v
y
3. Thus you could represent this rectangle with its
content by an array
xold yold value
---------------------
2 1 "5"
1 2 "*"
3 3 "4"
2 4 "+"
3 5 "3"
11. And then for each of this values, you rotate it to the right over
90 degrees:
For each of th values
take its x,y coordinate
show y, -x coordinate instead to rotate
Endfor
11. Thus this would become something like:
FOR xI = xminI TO maxI
Get information at xI, yI
Show instead at yI, -xI
ENDFOR
---
12. Thus the example list would become
(replace its x value by its old y value, and
replace its y value by its old -x value)
---
xnew ynew value
---------------------
1 -2 "5"
2 -1 "*"
3 -3 "4"
4 -2 "+"
5 -3 "3"
---
13. Now you see there is a little complication,
as the y values are negative.
This is because in a usual grid the
positive y-values go upwards.
So negative means they have to
go downwards.
But in our grid positive y-values
go DOWNwards.
So negative y values in a usual grid mean
positive y values in our grid.
Now you can easy fix this, by multiplying each y-value by -1 (this
is actually the rotate vertically over 180 degrees transformation,
that is xnew = xold, and ynew = -yold).
So after multiplying each y-value by -1,
the array becomes now:
xnew ynew value
---------------------
1 2 "5"
2 1 "*"
3 3 "4"
4 2 "+"
5 3 "3"
14. So to do this all at once, we should so
have used
xnew = yold
ynew = -1 . ( -xold )
or thus
xnew = yold
ynew = xold
15. Representing the array with its values
and new x,y coordinates again in the rectangle, using
this new x,y coordinates gives:
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+--+--+--+
1 | |* | | | | | | |
+--+--+--+--+--+--+--+--+
2 |5 | | |+ | | | | |
+--+--+--+--+--+--+--+--+
3 | | |4 | |3 | | | |
+--+--+--+--+--+--+--+--+
4 | | | | | | | | |
+--+--+--+--+--+--+--+--+
5 | | | | | | | | |
+--+--+--+--+--+--+--+--+
|
v
y
16. In other words the sideways tree has been rotated over
90 degrees to the left, and so this tree is now
shown upright
17. Sorting: But again there shows a little complication.
You want to print the tree in one pass, so going through the array
from the first to the last entry, and print the value on the
correct y-position.
That means the the lowest y-value should be taken first, the but
lowest y-value next, and so on, until you reach the last y-value
which should have the largest value
(This because your 'print head' can not go back upwards, but only
downwards, in this simplest possible case of controlling a 'print
head'. Of course there are languages where you could use 'PRINT
TAB( X, Y )' or 'GOTOXY' on the screen but here for the moment only
'PRINT' or WRITELINE statements are used).
That means the y-values should be ordered on the y value.
So you should sort the vertical y-values in the array first (so
that the smallest y comes first and the largest y comes last):
---
1. This sorting gives as a result:
xnew ynew value
---------------------
2 1 "*"
1 2 "5"
4 2 "+"
3 3 "4"
5 3 "3"
---
And after I tried this algorithm, it shows that also
you have to sort on the x column, which complicates
the matter further, because otherwise your printhead
might have to return back on the same line if you
printed a larger x-value first, and then have to return
on the same line to a smaller x-value. If you use e.g.
'PRINT' only this is usual not possible, the only result
of a new PRINT value will be that the 'printhead' will
go to the next line. So the x-values should be sorted
from small to large, so that the printhead does not
have to return.
2. To sub sort all given x-values for a given constant y-value,
you could solve this by going through the values
of the y column, then noting the equal values.
You note the first and last equal y value range.
Thus e.g. in the example in line two the y-value is 2,
and in line 3 the y-value is also 3.
You call then your sort routine again, which has
usually a parameter for the beginning position in the
array and the ending position in the array, thus the
range which it has to sort, with this found equal
begin y-value and equal end y-value.
And you sort on the x-array
---
3. So you find first that on line one only one
y-value with the equal value 1.
So you call your sort routine with this
range y-value range:
e.g. PROCQuickSortMain( firstI%, lastI% )
becomes here
PROCQuickSortMain( 1, 1 )
So you get after 'sorting' the first line
xnew ynew value
---------------------
2 1 "*"
1 2 "5"
4 2 "+"
3 3 "4"
5 3 "3"
3. So you find first that on line two and three
y-values with the equal value 2
So you call your sort routine with this
range y-value range:
e.g. PROCQuickSortMain( firstI%, lastI% )
becomes here
PROCQuickSortMain( 2, 3 )
So you get after 'sorting' the second and third line
xnew ynew value
---------------------
2 1 "*"
1 2 "5"
4 2 "+"
3 3 "4"
5 3 "3"
4. So you find first that on line four and five
y-values with the equal value 3
So you call your sort routine with this
range y-value range:
e.g. PROCQuickSortMain( firstI%, lastI% )
becomes here
PROCQuickSortMain( 4, 5 )
4. So you get after 'sorting' the fourth and fifth line:
xnew ynew value
---------------------
2 1 "*"
1 2 "5"
4 2 "+"
3 3 "4"
5 3 "3"
---
Actually, by incident this particular example was already
sorted, so there is no change. But the idea should be
clear. You have to sort on y and then to subsort on x.
---
18. So if you ask for NO random positioning of the 'printhead',
and so you print fluently by going from top to bottom,
and from left to right, with no returns, you get this
algorithm:
1. First pass to get the old x,y coordinates
1. print the tree sideways
1. store its x coordinate in an array
2. store its y coordinate in an array
3. store its value in an array
2. Second pass to print it on position new
x,y coordinates
1. for first to last value in the array
1. get its x coordinate, by taking its old y coordinate
2. get its y coordinate, by taking its old x coordinate
2. sort this array
1. sort on the y-column
2. sort on the x-column
3. for first to last value in the array
1. print the value:
1. first horizontally an amount of spaces proportional to
the x coordinate
2. then you print the value on that horizontal position
---
---
18. So if you can use random positioning e.g. using GotoXY() or
similar, your routine becomes much easier.
1. First pass to get the old x,y coordinates
1. print the tree sideways
1. store its xnew coordinate in an array
2. store its ynew coordinate in an array
3. store its value in an array
2. Second pass to print it on position new
x,y coordinates
1. for first to last value in the array
1. print the value:
1. Goto the position x,y
2. print the value on that position x,y
---
---
Internet: see also:
---
Datastructure: Link: Overview: Can you give an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/32054/fid/1264
----------------------------------------------------------------------
