Entry
Datastructure: Tree: Binary: Print: Upright: How to print a binary tree upright?
Feb 5th, 2005 12:19
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 23 October 2003 - 11:31 pm --------------------
Datastructure: Tree: Binary: Print: Upright: How to print a binary
tree upright?
---
Printing trees
---
When you debug code that works with binary trees, it is useful to
print the
trees with the structure of the tree clearly shown.
---
You can in general print sideways or you can print upright.
---
Printing sideways is a method quite often used, and leads to the least
amount
of source code, as it involves only one pass of going through the
binary tree, and some printing.
You do a right to left traversal of the binary
tree, and then printing enough spaces horizontally depending
on the depth of the tree at that moment.
---
Knud's method:
In printing upright the easiest method is to use two passes.
The first pass traverses the tree from the left to the right,
while storing the current x,y position of that node in an array.
In the second pass you read that array from left to right and
from top to bottom. If you find a non-empty cell on that position,
you print the node there.
---
---
Method of printing upright:
1. Method: Traverse left to right, store result in array,
then read this array from left to right
and from top to bottom, and print that result.
This should be by far the easiest method,
as it asks only for a few steps and also
easy algorithms and datastructures
(binary tree and a temporary array, and
2 loops which go from left to right and
top to bottom through the array).
2. Method: Print sideways, then rotate right over 90 degrees
3. Method: Traverse left to right, store result in tree, traverse
this resulting tree in breadth first
---
---
1. Method: Traverse left to right, store result in array,
then read this array from top to bottom
and from left to right, and print that
result.
This should be by far the easiest method.
Because the least steps are involved.
1. Traverse binary tree first from left to right, that will give
each node an x-value equal to its distance from the most left
node.
*
+ 5
3 4
2. You store that result in an array
in position x,y
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+--+--+--+
1 | | | |* | | | | |
+--+--+--+--+--+--+--+--+
2 | |+ | | |5 | | | |
+--+--+--+--+--+--+--+--+
3 |3 | |4 | | | | | |
+--+--+--+--+--+--+--+--+
4 | | | | | | | | |
+--+--+--+--+--+--+--+--+
5 | | | | | | | | |
+--+--+--+--+--+--+--+--+
|
v
y
3. You then traverse this array from left to
right and from top to bottom
=====> go from left to right
|
|
|
V
and from top to bottom
through the array.
and if you meet a non
empty cell, you print it.
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+--+--+--+
1 | | | |* | | | | |
+--+--+--+--+--+--+--+--+
2 | |+ | | |5 | | | |
+--+--+--+--+--+--+--+--+
3 |3 | |4 | | | | | |
+--+--+--+--+--+--+--+--+
4 | | | | | | | | |
+--+--+--+--+--+--+--+--+
5 | | | | | | | | |
+--+--+--+--+--+--+--+--+
|
v
y
---
---
2. Method: Print sideways, then rotate right over 90 degrees
Print binary tree first sideways (traverse tree from right to left,
then the x value is equal to the depth, and the y value is equal to
the position of that node as seen from the most right node),
then rotate it over 90 degrees to the
left, so that it becomes upright (using a rotation transformation)
1. Step 1 print the binary tree for '3 + 4 * 5' sideways first
1 2 3 4 5 6 7 8 -> x
1 +--+--+--+--+--+--+--+--+
| |5 | | | | | | |
2 +--+--+--+--+--+--+--+--+
|* | | | | | | | |
3 +--+--+--+--+--+--+--+--+
| | |4 | | | | | |
4 +--+--+--+--+--+--+--+--+
| |+ | | | | | | |
5 +--+--+--+--+--+--+--+--+
| | |3 | | | | | |
| +--+--+--+--+--+--+--+--+
v
y
1. Step 2 rotate the binary tree for '3 + 4 * 5' ninety degrees to
the right
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+
1 | |* | | | |
+--+--+--+--+--+
2 |5 | | |+ | |
+--+--+--+--+--+
3 | | |4 | |3 |
+--+--+--+--+--+
4 | | | | | |
+--+--+--+--+--+
5 | | | | | |
+--+--+--+--+--+
6 | | | | | |
+--+--+--+--+--+
7 | | | | | |
+--+--+--+--+--+
8 | | | | | |
+--+--+--+--+--+
|
v
y
---
---
3. Method: Traverse left to right, store result in tree, traverse
this resulting tree in breadth first
---
This method looks after some further thinking to be unnecessary
involved.
You better use an array to store the result,
instead of say a tree, because that rectangular structure is more
like the movement of the 'printhead', so leads to a simpler
situation.
---
Traverse binary tree first from left to right, that will
give each node an x-value equal to its distance from the most
left node.
You store that result in another temporary tree,
then use a breadth first traversal horizontally
of that result tree to print the values.
For that usually an extra queue is needed.
1. Step 1. Traverse the binary tree first from left to right to
determine
the x-value
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+--+--+--+
1 | | | |* | | | | |
+--+--+--+--+--+--+--+--+
2 | |+ | | |5 | | | |
+--+--+--+--+--+--+--+--+
3 |3 | |4 | | | | | |
+--+--+--+--+--+--+--+--+
4 | | | | | | | | |
+--+--+--+--+--+--+--+--+
5 | | | | | | | | |
+--+--+--+--+--+--+--+--+
|
v
y
If you agree to put each node in its own column,
in other words each node has a different x-value.
Further is its y value equal to its depth, that
is the distance of that node with respect to the
root.
then:
That will give node '3'
the horizontal x-value of 1
the vertical y-value of 3
That will give node '+'
the horizontal x-value of 2
the vertical y-value of 2
That will give node '4'
the horizontal x-value of 3
the vertical y-value of 3
That will give node '*'
the horizontal x-value of 4
the vertical y-value of 1
That will give node '5'
the horizontal x-value of 5
the vertical y-value of 2
2. Step 2. You store this results in another tree, while traversing
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+--+--+--+
1 | | | |* | | | | |
| | | | | | | | |
| | | |4 | | | | |
| | | |1 | | | | |
+--+--+--+--+--+--+--+--+
2 | |+ | | |5 | | | |
| | | | | | | | |
| |2 | | |5 | | | |
| |2 | | |2 | | | |
+--+--+--+--+--+--+--+--+
3 |3 | |4 | | | | | |
| | | | | | | | |
|1 | |3 | | | | | |
|3 | |3 | | | | | |
+--+--+--+--+--+--+--+--+
4 | | | | | | | | |
+--+--+--+--+--+--+--+--+
5 | | | | | | | | |
+--+--+--+--+--+--+--+--+
|
v
y
Here you see that each x-value and y-value for each of that
nodes is stored in a temporary tree, together with the value of
that node itself. E.g. you see '+ 2 2' which means that the '+'
node has a horizontal x-value of 2, and a vertical y-value of 2
3. Step 3. You traverse now horizontally, using thus inorder
traversel,
this temporary tree, thus going from top to bottom,
from left to right horizontally through the tree.
And print the results in the same go.
That will print upright.
Your 'printhead' has not to return to a previous
position, so you do not have to use random positioning.
1 2 3 4 5 6 7 8 -> x
+--+--+--+--+--+--+--+--+
1 | | | |* | | | | |
| | | | | | | | |
| | | |4 | | | | |
| | | |1 | | | | |
+--+--+--+--+--+--+--+--+
2 | |+ | | |5 | | | |
| | | | | | | | |
| |2 | | |5 | | | |
| |2 | | |2 | | | |
+--+--+--+--+--+--+--+--+
3 |3 | |4 | | | | | |
| | | | | | | | |
|1 | |3 | | | | | |
|3 | |3 | | | | | |
+--+--+--+--+--+--+--+--+
4 | | | | | | | | |
+--+--+--+--+--+--+--+--+
5 | | | | | | | | |
+--+--+--+--+--+--+--+--+
|
v
y
---
---
Book: see also:
---
[book: Flamig, Bryan - practical datastructures in C++ - p. 296 -
'Printing trees' -
http://search.barnesandnoble.com/booksearch/isbnInquiry.asp?
userid=2TFIGCDXI3&isbn=0471009555&itm=1]
---
---
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
----------------------------------------------------------------------
