Entry
BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How print binary tree upright? Array: Pretty
Jul 16th, 2006 05:31
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 24 October 2003 - 03:02 am --------------------
BBCBASIC: Data structure: Tree: Binary: Print: Upright: How print
binary tree upright? Array: Pretty
---
Steps: Overview:
1. -Open BBCBASIC
2. -Copy/paste this program in the program editor
--- cut here ---------------------------------------------------------
REM --- MAIN --- REM
PROCTreePrintBinaryUprightStringPrettySimpleMain( 1, -1, 10, 0 )
END
REM --- LIBRARY --- REM
:
REM library: tree: print: binary: upright main: left to right tree
traversal + array method, no random access of screen necessary [kn,
ni, mo, 27-10-2003 11:12:24]
REM e.g. PROCTreePrintBinaryUprightStringPrettySimpleMain( 1, -1, 10,
0 )
REM e.g. END
DEF PROCTreePrintBinaryUprightStringPrettySimpleMain( rootP%, nilP%,
dimmaxI%, depthminI% )
LOCAL xhorizontalGI%
LOCAL xhorizontalminGI%
LOCAL yverticalminGI%
LOCAL yverticalmaxGI%
LOCAL spaceleftGI%
PROCTreePrintBinaryUprightStringPrettySimpleInit
PROCTreePrintBinaryUprightStringPrettySimpleInitDim( dimmaxI% )
PROCTreePrintBinaryUprightStringPrettySimpleStoreData
PROCTreePrintBinaryUprightStringPrettySimpleInitData( dimmaxI% )
PROCTreePrintBinaryUprightStringPrettySimpleSub( rootP%, depthminI%,
rootP% )
PROCTreePrintBinaryUprightStringPrettySimpleFinal( xhorizontalminGI%,
xhorizontalGI%, yverticalminGI%, yverticalmaxGI% )
ENDPROC
ENDPROC
:
DEF PROCTreePrintBinaryUprightStringPrettySimpleInit
xhorizontalminGI% = depthminI%
xhorizontalGI% = xhorizontalminGI% - 1
yverticalminGI% = depthminI%
yverticalmaxGI% = yverticalminGI% - 1
spaceleftGI% = 0
ENDPROC
:
DEF PROCTreePrintBinaryUprightStringPrettySimpleInitDim( maxI% )
DIM lP%( maxI% )
DIM rP%( maxI% )
DIM s$( maxI% )
REM
DIM arraytemporaryP%( maxI%, maxI% )
REM
REM store total space before each node
DIM spaceI%( maxI% )
ENDPROC
:
DEF PROCTreePrintBinaryUprightStringPrettySimpleStoreData
REM
REM here 3 + 4 * 5 is stored in a binary tree
REM
REM ---
REM
REM the binary tree is represented by arrays
REM
REM ---
REM
REM format:
REM
REM leftpointer, rightpointer, value
REM
REM ---
REM
DATA 2, 3, "*"
DATA 4, 5, "+"
DATA -1, -1, "gamma"
DATA -1, -1, "alpha"
DATA -1, -1, "beta"
DATA -1, -1, ""
DATA -1, -1, ""
DATA -1, -1, ""
DATA -1, -1, ""
DATA -1, -1, ""
:
REM
REM * [1]
REM |
REM +--------------+------+
REM | |
REM + [2] gamma [3]
REM |
REM +------+------+
REM | |
REM alpha [4] beta [5]
REM
:
ENDPROC
:
DEF PROCTreePrintBinaryUprightStringPrettySimpleInitData( maxI% )
LOCAL I%
LOCAL minI%
minI% = 1
FOR I% = minI% TO maxI%
READ lP%( I% )
READ rP%( I% )
READ s$( I% )
NEXT I%
ENDPROC
:
REM library: tree: print: upright: 1st pass
DEF PROCTreePrintBinaryUprightStringPrettySimpleSub( P%, depthI%,
parentP% )
IF P% = nilP% THEN ENDPROC
REM
REM left first (=inorder) traversal, thus left has to come first
PROCTreePrintBinaryUprightStringPrettySimpleSub( lP%( P% ), depthI% +
1, P% )
REM
PROCTreePrintBinaryUprightStringPrettySimpleSubOutput( P%, depthI% )
REM
PROCTreePrintBinaryUprightStringPrettySimpleSub( rP%( P% ), depthI% +
1, P% )
ENDPROC
:
REM library: tree: print: upright: 2nd pass [kn, ri, sa, 25-10-2003
6:54:23]
DEF PROCTreePrintBinaryUprightStringPrettySimpleFinal( columnminI%,
columnmaxI%, rowminI%, rowmaxI% )
LOCAL rowI%
LOCAL columnI%
FOR rowI% = rowminI% TO rowmaxI%
FOR columnI% = columnminI% TO columnmaxI%
PROCTreePrintBinaryUprightStringPrettySimpleConnectionSub(
columnI%, rowI% )
NEXT columnI%
PROCTreePrintBinaryUprightStringPrettySimpleConnectionParentChild(
columnminI%, columnmaxI%, rowI%, rowmaxI% )
NEXT rowI%
ENDPROC
:
DEF PROCTreePrintBinaryUprightStringPrettySimpleSubOutput( P%,
depthI% )
REM
REM increase with 1 for each node,
REM as each node has a separate column per definition
REM
xhorizontalGI% = xhorizontalGI% + 1
REM
REM store the current x,y coordinate and value in a rectangular array
REM
arraytemporaryP%( xhorizontalGI%, depthI% ) = P%
REM
REM because you need to traverse the array later, you need
REM to know its maximum column value
REM
IF yverticalmaxGI% < depthI% THEN yverticalmaxGI% = depthI%
REM
REM store the total of spaces before this node
spaceI%( P% ) = spaceleftGI%
spaceleftGI% = spaceleftGI% + LEN( s$( P% ) )
ENDPROC
:
DEF PROCTreePrintBinaryUprightStringPrettySimpleConnectionSub( xI%,
yI% )
LOCAL sumstringlengthI%
LOCAL P%
P% = arraytemporaryP%( xI%, yI% )
s$ = s$( P% )
IF s$ = "" THEN ENDPROC
sumstringlengthI% = spaceI%( P% )
PRINT; TAB( sumstringlengthI% + 1 ); s$;
ENDPROC
:
DEF PROCTreePrintBinaryUprightStringPrettySimpleConnectionParentChild(
xminI%, xmaxI%, yI%, ymaxI% )
LOCAL xI%
REM
REM last row? Because the last row has per definition no children, so
you can quit
IF yI% >= ymaxI% THEN ENDPROC
REM
REM you must finish here a complete line first, because of the
printhead
FOR xI% = xminI% TO xmaxI%
PROCTreePrintBinaryUprightStringPrettySimpleConnectionParentChildSub(
xI%, xminI%, xmaxI%, yI%, 1 )
NEXT xI%
REM you must finish here a complete line first, because of the
printhead
FOR xI% = xminI% TO xmaxI%
PROCTreePrintBinaryUprightStringPrettySimpleConnectionParentChildSub(
xI%, xminI%, xmaxI%, yI%, 2 )
NEXT xI%
REM you must finish here a complete line first, because of the
printhead
FOR xI% = xminI% TO xmaxI%
PROCTreePrintBinaryUprightStringPrettySimpleConnectionParentChildSub(
xI%, xminI%, xmaxI%, yI%, 3 )
NEXT xI%
ENDPROC
:
DEF
PROCTreePrintBinaryUprightStringPrettySimpleConnectionParentChildSub(
xparentI%, xminI%, xmaxI%, yI%, I% )
LOCAL xI%
LOCAL parentP%
LOCAL childrightP%
LOCAL childleftP%
LOCAL xchildleftI%
LOCAL xchildrightI%
LOCAL s$
LOCAL childleft$
LOCAL childright$
LOCAL parentstringlengthI%
LOCAL childleftstringlengthI%
LOCAL childrightstringlengthI%
LOCAL xmiddleparentI%
LOCAL xmiddlechildleftI%
LOCAL xmiddlechildrightI%
REM
parentP% = arraytemporaryP%( xparentI%, yI% )
s$ = s$( parentP% )
REM
REM empty cell?
IF s$ = "" THEN ENDPROC
REM
childleftP% = lP%( parentP% )
childrightP% = rP%( parentP% )
IF childleftP% = nilP% AND childrightP% = nilP% THEN ENDPROC
IF childleftP% <> nilP% THEN childleft$ = s$( childleftP% ) :
xchildleftI% = spaceI%( childleftP% )
IF childrightP% <> nilP% THEN childright$ = s$( childrightP% ) :
xchildrightI% = spaceI%( childrightP% )
xI% = spaceI%( parentP% )
parentstringlengthI% = LEN s$
childleftstringlengthI% = LEN childleft$
childrightstringlengthI% = LEN childright$
REM
REM calculate the middle position of each string
xmiddleparentI% = xI% + ( parentstringlengthI% / 2 ) + 1
xmiddlechildleftI% = xchildleftI% + ( childleftstringlengthI% / 2 ) + 1
xmiddlechildrightI% = xchildrightI% + ( childrightstringlengthI% / 2 )
+ 1
REM
IF I% = 1 THEN PROCTreeBinaryParentChildConnectionPrint1(
xmiddleparentI%, xmiddlechildleftI%, xmiddlechildrightI%, childleftP%,
childrightP% )
IF I% = 2 THEN PROCTreeBinaryParentChildConnectionPrint2(
xmiddleparentI%, xmiddlechildleftI%, xmiddlechildrightI%, childleftP%,
childrightP% )
IF I% = 3 THEN PROCTreeBinaryParentChildConnectionPrint3(
xmiddleparentI%, xmiddlechildleftI%, xmiddlechildrightI%, childleftP%,
childrightP% )
ENDPROC
:
DEF PROCTreeBinaryParentChildConnectionPrint1( xmiddleparentI%,
xmiddlechildleftI%, xmiddlechildrightI%, childleftP%, childrightP% )
PRINT; TAB( xmiddleparentI% ); "|";
ENDPROC
:
DEF PROCTreeBinaryParentChildConnectionPrint2( xmiddleparentI%,
xmiddlechildleftI%, xmiddlechildrightI%, childleftP%, childrightP% )
IF childleftP% <> nilP% THEN PRINT TAB( xmiddlechildleftI% ); "+";
STRING$( xmiddleparentI% - xmiddlechildleftI% - 1, "-" ); "+";
IF childrightP% <> nilP% THEN PRINT; STRING$( xmiddlechildrightI% -
xmiddleparentI% - 1, "-" ); "+";
ENDPROC
:
DEF PROCTreeBinaryParentChildConnectionPrint3( xmiddleparentI%,
xmiddlechildleftI%, xmiddlechildrightI%, childleftP%, childrightP% )
IF childleftP% <> nilP% THEN PRINT TAB( xmiddlechildleftI% ); "|";
IF childrightP% <> nilP% THEN PRINT TAB( xmiddlechildrightI% ); "|";
ENDPROC
:
--- cut here ---------------------------------------------------------
3. -Run the program
4. -That will show for this example the binary tree
for 'alpha + beta * gamma'
as the following below:
*
|
+--------------+------+
| |
+ gamma
|
+------+------+
| |
alpha beta
---
---
Internet: see also:
---
BBCBASIC: Windows: Data structure: Link: Overview: Can you give an
overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/41639/fid/768
----------------------------------------------------------------------
