Entry
BBCBASIC: Datastructure: Tree: Binary: Print: Upright: How to print a binary tree upright?: Rotate
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? Rotate
---
Steps: Overview:
1. -Open BBCBASIC
2. -Copy/paste this program in the program editor
--- cut here ---------------------------------------------------------
REM --- MAIN --- REM
PROCTreePrintBinaryUprightRotateMain( 1, -1, 10, 0 )
END
REM --- LIBRARY --- REM
:
REM library: tree: print: binary: upright main [kn, ri, fr, 24-10-
2003 3:16:08]-[kn, ni, fr, 24-10-2003 5:22:28]
REM e.g. PROCTreePrintBinaryUprightRotateMain( 1, -1, 10, 0 )
REM e.g. END
DEF PROCTreePrintBinaryUprightRotateMain( rootP%, nilP%, dimmaxI%,
depthminI% )
LOCAL yverticalminGI%
LOCAL yverticalmaxGI%
LOCAL nodetotalGI%
PROCTreePrintBinaryUprightRotateInit
PROCTreePrintBinaryUprightRotateInitDim( dimmaxI% )
PROCTreePrintBinaryUprightRotateStoreData
PROCTreePrintBinaryUprightRotateInitData( dimmaxI% )
PROCTreePrintBinaryUprightRotateSub( rootP%, depthminI% )
PROCTreePrintBinaryUprightRotateFinal( 1, dimmaxI%, depthminI% )
ENDPROC
:
DEF PROCTreePrintBinaryUprightRotateInit
yverticalminGI% = 1
yverticalmaxGI% = yverticalminGI% - 1
nodetotalGI% = 1 - 1
ENDPROC
:
DEF PROCTreePrintBinaryUprightRotateInitDim( maxI% )
DIM lP%( maxI% )
DIM rP%( maxI% )
DIM sold$( maxI% )
REM
DIM xnewI%( maxI% )
DIM ynewI%( maxI% )
DIM snew$( maxI% )
ENDPROC
:
DEF PROCTreePrintBinaryUprightRotateStoreData
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 PROCTreePrintBinaryUprightRotateInitData( maxI% )
LOCAL I%
LOCAL minI%
minI% = 1
FOR I% = minI% TO maxI%
READ lP%( I% )
READ rP%( I% )
READ sold$( I% )
NEXT I%
ENDPROC
:
DEF PROCTreePrintBinaryUprightRotateSub( P%, depthI% )
IF P% = nilP% THEN ENDPROC
REM
REM right first traversal, thus right has to come first
PROCTreePrintBinaryUprightRotateSub( rP%( P% ), depthI% + 1 )
REM
PROCTreePrintBinaryUprightRotateSubOutput( P% )
REM
PROCTreePrintBinaryUprightRotateSub( lP%( P% ), depthI% + 1 )
ENDPROC
:
REM library: tree: print: upright: 2nd pass [kn, ri, fr, 24-10-2003
4:56:00]
DEF PROCTreePrintBinaryUprightRotateFinal( minI%, maxI%, depthminI% )
LOCAL I%
LOCAL yI%
yoldI% = depthminI%
yI% = yoldI%
FOR I% = minI% TO maxI%
yI% = ynewI%( I% )
IF yI% >= depthminI% THEN PROCTreePrintBinaryUprightRotateFinalSub(
I% )
NEXT I%
ENDPROC
:
DEF PROCTreePrintBinaryUprightRotateSubOutput( P% )
PRINT
REM increase with 1 with each node coming in
yverticalmaxGI% = yverticalmaxGI% + 1
REM
REM PRINT; TAB( 2 * depthI% ); sold$( P% ); " ";
REM
REM increase the currently handled nodes with 1
nodetotalGI% = nodetotalGI% + 1
REM
REM store the current x,y coordinate and value in an array
REM
REM in the new x-coordinate store the old y-coordinate
xnewI%( nodetotalGI% ) = yverticalmaxGI%
REM
REM in the new y-coordinate store the old x-coordinate
ynewI%( nodetotalGI% ) = depthI%
REM
REM in the new value store the old value
snew$( nodetotalGI% ) = sold$( P% )
ENDPROC
:
DEF PROCTreePrintBinaryUprightRotateFinalSub( I% )
PRINT; TAB( 2 * xnewI%( I% ), yI% ); snew$( I% );
IF yI% <> yoldI% THEN yoldI% = yI% : PRINT
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
----------------------------------------------------------------------
