Entry
Datastructure: Tree: Binary: Print: How to print binary tree sideways?
Feb 5th, 2005 12:17
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 23 October 2003 - 10:40 pm --------------------
Datastructure: Tree: Binary: Print: Sideways: How to print binary tree
sideways?
---
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 the easiest method as it involves only
printing enough spaces horizontally.
---
The procedures use the treewalk or tree traversal procedures
prefix
infix
suffix
order
or similarly
preorder
inorder
postorder
or similarly
traverse right first
traverse left first
traverse middle first.
---
To print, all that is needed is the ability to print spaces
horizontally.
---
For example in BBCBASIC 'PRINT' can be used to print.
For example in C 'printf' can be used to print.
For example in C++ 'cout' can be used to print.
For example in C# 'Console.WriteLine( "" );' can be used to print.
For example in Java 'System.out.println( "" );' can be used to print.
For example in TSE 'InsertText()', 'WriteLine()', 'Message' can be
used to print.
---
---
Steps: overview:
1. Print sideways
2. Print upright
---
---
1. Print sideways
---
Method: 1. do a tree walk traversal from the right to the left, and
2. use the depth to print spaces horizontally
---
The following procedure will print a tree sideways,
with the root of the tree to the left and
the rightmost node on the first line.
---
Your tree will always be printed inside a rectangle, with
the following sides:
1. with the horizontal side equal to the depth of the binary tree,
2. and the vertical side equal to the total amount of nodes
of the binary tree. This because per definition each
node is put on a new row, and there will be no other
nodes be put on that row further.
If you should choose to print sideways:
------------------------> depth max
| +--+--+--+--+--+--+--+--+
| | | | | | | | | |
| +--+--+--+--+--+--+--+--+
| | | | | | | | | |
| +--+--+--+--+--+--+--+--+
| | | | | | | | | |
| +--+--+--+--+--+--+--+--+
| | | | | | | | | |
| +--+--+--+--+--+--+--+--+
| | | | | | | | | |
v +--+--+--+--+--+--+--+--+
node max
or similarly:
If you should choose to print upright:
---------------> node max
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
| +--+--+--+--+--+
| | | | | | |
v +--+--+--+--+--+
depth max
---
So the depth will be used as a scalefactor for the amount of spaces.
---
For example, here the depth scalefactor is 2.
So it will stretch your rectangle horizontally.
---
----------------------------------------> 2 . depth max
| +----+----+----+----+----+----+----+----+
| | | | | | | | | |
| +----+----+----+----+----+----+----+----+
| | | | | | | | | |
| +----+----+----+----+----+----+----+----+
| | | | | | | | | |
| +----+----+----+----+----+----+----+----+
| | | | | | | | | |
| +----+----+----+----+----+----+----+----+
| | | | | | | | | |
v +----+----+----+----+----+----+----+----+
node max
---
So this method is just a special case of a scaling transformation.
---
PROC binaryprintsideways( pointer P, integer depthI, string spaceS )
//
IF P == nill
RETURN()
ENDIF
//
// 3 possibilities: PREFIX, INFIX, or SUFFIX print order
//
// Here the PREFIX print order is used
//
binaryprint( P.leftP, depthI + 1, spaceS + " " )
//
//
binaryprint( P.rightP, depthI + 1, spaceS + " " )
//
//
binaryprintresult( P, depthI, spaceS )
//
END
PROC binaryprintresult( pointer P, integer depthI, string spaceS )
Message( spaceS + P.infoS )
END
PROC Main()
binaryprint( rootP, 0, " " )
END
---
---
Book: see also:
[book: Flamig, Bryan - practical datastructures in C++ -
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
----------------------------------------------------------------------
