Entry

BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How to print a binary tree upright? Array

Jul 16th, 2006 05:35
Knud van Eeden,

----------------------------------------------------------------------
--- Knud van Eeden --- 24 October 2003 - 03:02 am --------------------

BBCBASIC: Data structure: Tree: Binary: Print: Upright: How to print a 
binary tree upright? Array

---

Steps: Overview:

 1. -Open BBCBASIC

 2. -Copy/paste this program in the program editor

--- cut here ---------------------------------------------------------

REM --- MAIN --- REM

PROCTreePrintBinaryUprightSimpleMain( 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, sa, 25-10-2003  6:25:06]
REM e.g. PROCTreePrintBinaryUprightSimpleMain( 1, -1, 10, 0 )
REM e.g. END
DEF PROCTreePrintBinaryUprightSimpleMain( rootP%, nilP%, dimmaxI%, 
depthminI% )
LOCAL xhorizontalGI%
LOCAL xhorizontalminGI%
LOCAL yverticalminGI%
LOCAL yverticalmaxGI%
PROCTreePrintBinaryUprightSimpleInit
PROCTreePrintBinaryUprightSimpleInitDim( dimmaxI% )
PROCTreePrintBinaryUprightSimpleStoreData
PROCTreePrintBinaryUprightSimpleInitData( dimmaxI% )
PROCTreePrintBinaryUprightSimpleSub( rootP%, depthminI% )
PROCTreePrintBinaryUprightSimpleFinal( xhorizontalminGI%, 
xhorizontalGI%, yverticalminGI%, yverticalmaxGI% )
ENDPROC
:
DEF PROCTreePrintBinaryUprightSimpleInit
xhorizontalminGI% = depthminI%
xhorizontalGI% = xhorizontalminGI% - 1
yverticalminGI% = depthminI%
yverticalmaxGI% = yverticalminGI% - 1
ENDPROC
:
DEF PROCTreePrintBinaryUprightSimpleInitDim( maxI% )
DIM lP%( maxI% )
DIM rP%( maxI% )
DIM s$( maxI% )
REM
DIM arraytemporaryS$( maxI%, maxI% )
ENDPROC
:
DEF PROCTreePrintBinaryUprightSimpleStoreData
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, "5"
DATA -1, -1, "3"
DATA -1, -1, "4"
DATA -1, -1,  ""
DATA -1, -1,  ""
DATA -1, -1,  ""
DATA -1, -1,  ""
DATA -1, -1,  ""
ENDPROC
:
DEF PROCTreePrintBinaryUprightSimpleInitData( 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 PROCTreePrintBinaryUprightSimpleSub( P%, depthI% )
IF P% = nilP% THEN ENDPROC
REM
REM left first traversal, thus left has to come first
PROCTreePrintBinaryUprightSimpleSub( lP%( P% ), depthI% + 1 )
REM
PROCTreePrintBinaryUprightSimpleSubOutput( P%, depthI% )
REM
PROCTreePrintBinaryUprightSimpleSub( rP%( P% ), depthI% + 1 )
ENDPROC
:
DEF PROCTreePrintBinaryUprightSimpleSubOutput( 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
arraytemporaryS$( xhorizontalGI%, depthI% ) = s$( 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%
ENDPROC
:
REM library: tree: print: upright: 2nd pass [kn, ri, sa, 25-10-2003  
6:54:23]
DEF PROCTreePrintBinaryUprightSimpleFinal( columnminI%, columnmaxI%, 
rowminI%, rowmaxI% )
LOCAL rowI%
LOCAL columnI%
FOR rowI% = rowminI% TO rowmaxI%
  FOR columnI% = columnminI% TO columnmaxI%
    PROCTreePrintBinaryUprightSimpleFinalSub( columnI%, rowI% )
  NEXT columnI%
NEXT rowI%
ENDPROC
:
DEF PROCTreePrintBinaryUprightSimpleFinalSub( xI%, yI% )
s$ = arraytemporaryS$( xI%, yI% )
IF s$ = "" THEN ENDPROC
PRINT; TAB( xI% ); s$;
ENDPROC
:

--- cut here ---------------------------------------------------------

 3. -Run the program

 4. -That will show for this example the binary tree
     for '3 + 4 * 5' upright:


                *
            +      5
          4   3

===

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

----------------------------------------------------------------------