Entry
Datastructure: Tree: Binary: Print: Upright: How print binary tree with strings different lengths?
Feb 5th, 2005 12:22
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 27 October 2003 - 02:40 am --------------------
Datastructure: Tree: Binary: Print: Upright: How print binary tree
with strings different lengths?
---
Two situations:
1. Printing the tree sideways
2. Printing the tree upright
---
---
If printing the tree sideways, the length of the strings has usually
not
to be taken in account.
But it will in general be more difficult to see the structure of the
tree.
---
---
If printing the tree upright:
The resulting tree will in the simplest case be printed inside a
rectangle with as sides:
1. sum of the total length of all strings
2. the depth
---
---
The simplest case is when all nodes are single characters.
e.g. '3 + 4 * 5'
*
|
+----+--+
| |
+ 5
|
+--+--+
| |
3 4
---
The simplest case of printing the binary tree is again here
printing the tree sideways, because as each string in each
node gets a whole row for itself, it can be printed on
that line without overwriting or interfering with other
strings.
For example:
Given the binary tree 'red + black * blue' becomes
printed sideways:
red
*
black
+
blue
---
---
Now printing the binary tree upright.
---
If general if you print a tree upright, it will be put in a rectangle
with side lengths:
-horizontally node max
and
-vertically depth max
---
---------------> node max
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
v +--+--+--+--+--+
depth max
---
This because each depth gets exactly 1 row assigned.
and also
each node gets exactly 1 column assigned.
---
So here you have totally
nodemax times a breadth of 1 character, or thus a horizontal side of
nodemax
and
depthmax times 1, or thus a vertical side of depthmax
---
Note:
So here the scalefactor for depthmax in the above is thus equal to
1, so here is chosen for the simplest possible case, that is
no scaling at all (you could otherwise arbitrarily also choose a
scalefactor of 2, 3, ..., 3.14, ... and so on).
---
Thus in the special case of choosing the binary tree for '3 + 4 * 5',
what will be the total length of the sides of the resulting rectangle?
---
You have totally '3', '+', '4', '*', '5', or thus 5 nodes.
Thus the horizontal side of your rectangle will be 5 times 1, or thus
5.
---
The depth (e.g. after drawing the tree and counting it), is totally 3.
Thus the vertical side of your rectangle will be 3 times 1, or thus 5.
---
Thus you will see your binary tree here drawn in a rectangle with
sides equal to horizontally 5, and vertically 3.
---
---------------> node max = 5
| +--+--+--+--+--+
| | | | |* | |
| +--+--+--+--+--+
| | |+ | | |5 |
| +--+--+--+--+--+
| |3 | |4 | | |
V +--+--+--+--+--+
depth max = 3
---
---
Now what happens with the total sides of the rectangle, if we choose
instead of single characters, thus strings of length 1, some strings
with a length greater than 1?
---
Suppose you choose as your binary tree 'red + black * blue'.
---
Or thus this binary tree printed upright:
*
+ blue
red black
---
What will be the vertical and horizontal dimensions of your rectangle?
---
Now you know horizontally each string gets a separate column for
itself.
So its string length should fit inside this column.
---
So the breadth of each column should be at least equal to the
total length of each string.
---
This, as each character of the string needs thus at least a a
horizontal breadth of 1.
---
Thus all the characters of that string together need thus
(total characters in that string) times 1
Or thus
(total characters in that string)
Or thus
in other words the Length of that string.
---
Now what is the length of the string 'red'? That is 3.
And what is the length of the string '+'? That is 1.
And what is the length of the string 'black'? That is 5.
And what is the length of the string '*'? That is 1.
And what is the length of the string 'blue'? That is 4.
---
So adding this all together, you need so for your horizontal side
of your triangle:
3 + 1 + 5 + 1 + 4
or thus a horizontal side of
14
---
Your vertical side is not influenced. So you keep this the same
as before.
The depth is totally 3.
Thus your vertical side is totally 3.
---
Thus you now that the rectangle is going to be 14 horizontally
and 3 vertically.
---
sum of the length of all the strings
------------------------------------------>
| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | |* | | | | |
| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | |+ | | | | | | |b |l |u |e |
| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| |r |e |d | |b |l |a |c |k | | | | | |
V +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
depth max = 3
---
---
As this is a special case of a scaling transformation,
you can further generalize it, by saying that you scaled
in this example each column horizontally with a scale factor of 1.
In that case each column has a breadth equal to
(total length of the string in this column) times 1.
Of course you can choose other (larger) numbers than 1, say
2, 3, 3.14, ...4.
---
So in general you get for 1 column.
(total length of the string in this column) times (some scalefactor)
---
So in general you get for all columns
(total length of the string1 in column1) times (some scalefactor) +
(total length of the string2 in column2) times (some scalefactor) +
(total length of the string3 in column3) times (some scalefactor) +
...
(total length of the string3 in columnlast) times (some scalefactor) +
---
Or thus:
( SUM of all lengths of the strings ) times (some scalefactor).
---
The simplest case, no scaling, is thus choosing this scalefactor equal
to 1.
---
You get then:
( SUM of all lengths of the strings ) times (1)
---
Or thus:
( SUM of all lengths of the strings )
---
---
So in order to get on beforehand this total horizontal length of the
printing rectangle, you get all the strings, calculate their total
lengths, and add this. The final sum will then give the horizontal
length.
---
You could use e.g. a for next loop, similar to the following:
horizontalscalefactor = 1
sumstringlengthtotal = 0
FOR first to last node
read the string
stringlength = length of string
sumstringlengthtotal =
sumstringlengthtotal + ( stringlength * horizontalscalefactor )
ENDFOR
return the sumstringlengthtotal
---
---
To further generalize it, say that you want to put extra characters
around your strings, e.g. something like this:
*
+ [ blue ]
[ red ] [ black ]
---
How does this change the total length of the horizontal side?
---
Well, you can say that adding characters just makes the original
total string length of each node bigger.
So you just add the length of this extra characters to the original
string length for each string.
So you get
new string length =
( old string length ) plus ( string length extra characters )
---
So finally you get for the total horizontal length:
( SUM all (lengths of the strings) + (length string extra characters))
times
(some scalefactor)
---
---
But similarly you can say the same for the vertical side, in the
case you want some extra characters in between.
The total amount of rows is equal to the total amount of nodes
in the usual case.
So now each node gets some extra characters added to it.
e.g.
Instead of using the simplest case vertically, that is no
extra characters, like here:
+
red blue
---
Now you add some extra characters horizontally to show the tree
structure it more clearly:
+
|
+--+--+
| |
red blue
---
So in this case you add 3 characters VERTICALLY.
---
If you should do this consequently for each node then each node
gets 3 extra characters.
---
So instead of a vertical side of totally node max, you have
now a total side of
( node max ) times ( 1 + ( total extra characters vertically ) )
---
A bit more general would be to multiply this with some scale factor,
in order to be able to further stretch or shrink the distance
vertically.
---
So in general, if each node gets the same amount of extra characters
assigned, then this total vertical length of the rectangle in which you
shall print the binary tree will become:
Instead of ( node max ) times 1,
you get now:
( node max ) times ( 1 + ( total extra characters vertically ) )
times (some vertical scalefactor)
---
---
Suppose in the most primitive case that your 'printhead' can only move
from top to bottom and from left to right (but thus not return to an
earlier position, backwards or upwards).
---
In other words you can not randomly position your printhead.
---
Now the question, how to print the binary
tree upright, when the nodes contain strings of length between
zero, one, and more than one?
---
Now if giving this simple example:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | |* | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | |+ | | | | | | |b |l |u |e |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|r |e |d | |b |l |a |c |k | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
and remembering that you will print this from top
to bottom and from left to right,
thus like this:
---
First this row from left to right
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | |* | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
---
Then this row from left to right
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | |+ | | | | | | |b |l |u |e |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
---
Finally this row from left to right
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|r |e |d | |b |l |a |c |k | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
---
The question is now how many spaces totally to print before
each string.
---
After making a drawing and looking at the total amount of
columns before each string, you can possibly make the following
observation:
---
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | |* | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | |+ | | | | | | |b |l |u |e |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|r |e |d | |b |l |a |c |k | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
---
In the simplest case, you get the total amount of columns
BEFORE each string, by adding the total length of
all the strings before it horizontally.
---
So for example the '*' has this strings 'before' it:
+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | *
+--+--+--+--+--+--+--+--+--+
| | | |+ | | | | | |
+--+--+--+--+--+--+--+--+--+
|r |e |d | |b |l |a |c |k |
+--+--+--+--+--+--+--+--+--+
<--total amount of spaces-->
---
So the total amount of spaces before the string '*'
equals
(length of string 'red') +
(length of string '+') +
(length of string 'black')
or thus
3 + 1 + 5
or thus
9
spaces totally before it.
---
and 'blue' has this strings before it:
---
+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | |* |
+--+--+--+--+--+--+--+--+--+--+
| | | |+ | | | | | | | blue
+--+--+--+--+--+--+--+--+--+--+
|r |e |d | |b |l |a |c |k | |
+--+--+--+--+--+--+--+--+--+--+
<--total amount of spaces----->
---
So the total amount of spaces before the string 'blue'
equals
(length of string 'red') +
(length of string '+') +
(length of string 'black') +
(length of string '*')
or thus
3 + 1 + 5 + 1
or thus
10
spaces totally before it.
---
---
So how to simple count this amount of spaces?
---
method 1: check the part of the array before a given string
Note:
This will be the preferred and used method here,
as the other method gives too many extra complications,
so making it less simple.
And the simplest method is were we are looking for.
---
Checking in the array before this character
if you find a non empty cell containing a string.
In that case add the length of this string to the
total.
+--+--+--+--+--+--+--+--+--+
| | | | | | | | | |
+--+--+--+--+--+--+--+--+--+
| | | |+ | | | | | |
+--+--+--+--+--+--+--+--+--+
|r |e |d | |b |l |a |c |k |
+--+--+--+--+--+--+--+--+--+
So basically to count the amount of characters before e.g. the
'*', you go from top to bottom and from left to right trough
this subarray, and check if you find non empty cells containing
a string. In that case you add the length of that string
to the total.
So here you go through the array from top to bottom, and
from left to right.
While moving from top to bottom and from left to right,
first you meet the '+'. Its length is 1. So you add that
to the sum. That sum will become 1.
Then you meet 'red'. Its length equals 3. So you add that
to the sum. That sum will become 4.
Then you meet 'black'. Its length is 5. So you add that to
the sum. That sum will become 9.
So you know that you minimally must print 9 spaces in front
of the '*' on the first line.
---
I think currently this method should be the simplest.
---
As you just go through a rectangular array, so you get something
like
FOR rowcounter = first to last row
FOR columncounter = first to last column before that string
Read cell at position rowcounter, columncounter
IF cell not empty then
get string
add length of string to the sum
ENDIF
ENDFOR
---
Conlusion:
But there will be some repetition of the scanning through the arrays,
as you in the simplest case do not store any of the previous results,
so you possibly scan again and again the same subarrays, so it is a bit
of a brute force method.
---
Trying this method and idea:
---
For example in BBCBASIC, you could use the following,
in combination with the print upright program.
See also: BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How
print binary tree upright? Array: String
[Internet: see also:
http://www.faqts.com/knowledge_base/view.phtml/aid/26033/fid/768]
---
sumstringlengthI% = FNTreeBinaryGetSpacesI( xhorizontalminGI%, xI% -
1, yverticalminGI%, yverticalmaxGI% )
...
:
DEF FNTreeBinaryGetSpacesI( columnminI%, columnmaxI%, rowminI%,
rowmaxI% )
LOCAL sumstringlengthI%
LOCAL rowI%
LOCAL columnI%
LOCAL s$
sumstringlengthI% = 0
IF ( columnmaxI% < columnminI% ) THEN = sumstringlengthI% : REM if
first column then for sure 0
FOR rowI% = rowminI% TO rowmaxI%
FOR columnI% = columnminI% TO columnmaxI%
s$ = arraytemporaryS$( columnI%, rowI% )
IF s$ <> "" THEN sumstringlengthI% = sumstringlengthI% + LEN( s$ )
NEXT columnI%
NEXT rowI%
= sumstringlengthI%
:
---
---
method 2: do an INORDER traversal of the original binary tree.
counting the length of all the strings until a given node
---
Because you are basically counting by doing a
'vertical level order' traversal:
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
| | | | | | | | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
| | -> | | -> | | -> |+ | -> | | -> | | -> | | -> | | -> | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
|r | |e | |d | | | |b | |l | |a | |c | |k |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
---
and this instead of a 'horizontal level order', or 'breadth first'
traversal.
->
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | |* | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
then
->
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | |+ | | | | | | |b |l |u |e |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
then
->
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|r |e |d | |b |l |a |c |k | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
---
so you can ask yourself how to do this 'vertical level order'
traversal?
---
Well, you can make the observation that an INORDER traversal of a
binary
tree does exactly that.
---
The result of an inorder traversal is as if all the nodes
were 'projected'
down onto a single horizontal line.
---
For example the inorder traversal of
*
+ blue
red black
will give as a result:
red + black * blue
---
In other words you just have to project the nodes of the tree,
(for example here 'red', '+', 'black', '*', 'blue')
on a horizontal line, to quickly see and find the result of
any INORDER traversal.
*
|
+ | blue
red | black | |
| | | | |
v v v v v
-------------------
---
[book: see also: Knuth, Donald - the art of computer programming
(fundamental algorithms) / volume 1 - p. 319 'traversing binary
trees' - http://www.amazon.com/exec/obidos/tg/detail/-
/0201485419/qid=1067231270/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]
---
But that is exactly what you want, as you need to get the sum of all
this projected string lengths BEFORE that given node.
---
So to get the total length of the strings before say the '*', you do
each time an inorder traversal UNTIL that node, in the given binary
tree. At each of that nodes before, you get the string lengths, and add
this to the total.
---
So thus in the example of '*', doing an inorder traversal, will
first give 'red'. This has a string length of 3. So you add 3 to
the sum. So the sum becomes 3.
---
Then you meet during the inorder traversal the '+'
This string has a length of 1. So you add 1 to the sum. So the sum
becomes now 3 + 1 or 4.
---
Then you meet during the inorder traversal the 'black'
This string has a length of 5. So you add 5 to the sum. So the sum
becomes now 4 + 5 or 9.
---
So your source code might become something like this:
---
INTEGER FNbinarygetspacesI( pointer P, string S, integer
sumstringlengthI )
//
IF P == nill
RETURN( sumstringlengthI )
ENDIF
//
// you reached the wanted string (e.g. '*')
IF ( P.infoS == S )
RETURN( sumstringlengthI )
ENDIF
//
// 3 possibilities: PREFIX, INFIX, or SUFFIX print order
//
// Here the INORDER print order is used
//
FNbinarygetspacesI( P.leftP, S, sumstringlengthI + Length( P.infoS ) )
//
PROCbinaryresult( P, S, sumstringlengthI )
//
FNbinarygetspacesI( P.rightP, S, sumstringlengthI + Length( P.infoS ) )
//
END
PROCbinaryresult( pointer P, string S, integer sumstringlengthI )
sumstringlengthI = sumstringlengthI + Length( P.infoS )
END
PROC Main()
Message( FNbinarygetspacesI( rootP, "*", 0 )
END
---
Conclusion:
But there will be some repetition of the scanning through the binary
tree, during inorder traversal, as you in the simplest case do not
store any of the previous results, so you possibly scan again and again
in parts of the same tree, so it is a bit of a brute force method.
---
---
But when trying this method and idea, it showed there were some
complications:
---
For example in BBCBASIC, you could use the following:
DEF FNTreeBinaryGetSpacesI( P%, nilP%, s$, sumstringlengthI% )
REM e.g. PRINT FNTreeBinaryGetSpacesI( 1, -1, "*", 0, FALSE )
REM e.g. END
REM you reached a nil pointer at that position in the tree
IF P% = nilP% THEN = sumstringlengthI%
REM you reached the wanted string (e.g. '*')
IF s$( P% ) = s$ THEN = sumstringlengthI%
REM
REM 3 possibilities: PREFIX, INFIX, or SUFFIX print order
REM
REM Here the INORDER print order is used
REM
= FNTreeBinaryGetSpacesI( lP%( P% ), nilP%, s$, sumstringlengthI% + LEN
( s$( P% ) ) )
REM
PROCTreeBinaryGetResult( P%, sumstringlengthI% )
REM
= FNTreeBinaryGetSpacesI( rP%( P% ), nilP%, s$, sumstringlengthI% + LEN
( s$( P% ) ) )
REM
END
:
DEF PROCTreeBinaryGetResult( P%, sumstringlengthI% )
sumstringlengthI% = sumstringlengthI% + LEN( s$( P% ) )
END
:
---
---
But after trying this working program with the binary tree '3 + 4 * 5',
to keep it simple, or thus
*
+ 5
3 4
there was a little complication.
Which became clear when running it with the example string '*'.
In the routine you need to stop only when you have visited all the
nodes on the left, before this given string.
But how do you know that?
My idea was to test if the current string was equal to the given
string.
E.g. test if P.info = "*" and if so return.
So in this case it immediately stopped at the root. As the root
was '*'.
You might circumvent this by e.g. storing intermediate results.
But anyhow this would further complicate the matter.
And you are looking for the simplest method here.
---
Conclusion:
The array method above is the easiest and most promising method
currently.
---
---
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
----------------------------------------------------------------------
