TITLE   "Traversing a tree"

        USE     "hawk.macs"
        USE     "monitor.h"

        S       START

;  fields of a tree node
LEFT    =       0
RIGHT   =       4
TEXT    =       8

        COMMON  STACK,#1000
PSTACK: W       STACK

; the program starts here!
START:  LOAD    R2,PSTACK       ; set up the stack

        LOAD    R1,PDSPINI
        JSRS    R1,R1           ; dspini()

        LEA     R3,ATREE
        JSR     R1,TRAVERSE     ; traverse ( ATREE )

        LOAD    R1,PEXIT        ; exit ()
        JSRS    R1,R1

        SUBTITLE "A binary tree to traverse"

        ALIGN   4
ATREE:  W       TLEFT           ; the root node
        W       TRIGHT
        W       TTXT
TTXT:   ASCII   '+',0

        ALIGN   4
TLEFT:  W       0               ; left child
        W       0
        W       TLTXT
TLTXT:  ASCII   '55',0

        ALIGN   4
TRIGHT: W       TRLEFT          ; right child
        W       TRRIGHT
        W       TRTXT
TRTXT:  ASCII   '*',0

        ALIGN   4
TRLEFT: W       TRLLEFT         ; left child of right child
        W       TRLRIGHT
        W       TTXT

TRLLEFT:W       0               ; left child of left child of right child
        W       0
        W       TRLLTXT
TRLLTXT:ASCII   '6',0

        ALIGN   4
TRLRIGHT:                       ; right child of left child of right child
        W       0
        W       0
        W       TRLRTXT
TRLRTXT:ASCII   '7',0

        ALIGN   4
TRRIGHT:W       0               ; right child of right child
        W       0
        W       TRRTXT
TRRTXT: ASCII   '8',0

        SUBTITLE "traversal routine"

; activation record structure for traversal
RETAD   =       0
NODE    =       4
ARSIZE  =       8

TRAVERSE:
        ;       R1 = return address
        ;       R3 = pointer to node
        ;       R3-7 may be wiped out
        ;       R8-15 will be restored
        STORES  R1,R2
        STORE   R3,R2,NODE

        TESTR   R3              ; if (node != null) {
        BZS     TRAVQUIT

        LIS     R3,'('
        ADDI    R2,R2,ARSIZE    ;   push my AR
        LOAD    R1,PDSPCH
        JSRS    R1,R1           ;   dspch( '(' )
        ADDI    R2,R2,-ARSIZE   ;   pop my AR

        LOAD    R3,R2,NODE
        LOAD    R3,R3,LEFT
        ADDI    R2,R2,ARSIZE    ;   push my AR
        JSR     R1,TRAVERSE     ;   traverse( node->left )
        ADDI    R2,R2,-ARSIZE   ;   pop my AR

        LOAD    R3,R2,NODE
        LOAD    R3,R3,TEXT
        ADDI    R2,R2,ARSIZE    ;   push my AR
        LOAD    R1,PDSPST
        JSRS    R1,R1           ;   dspst( node->text )
        ADDI    R2,R2,-ARSIZE   ;   pop my AR

        LOAD    R3,R2,NODE
        LOAD    R3,R3,RIGHT
        ADDI    R2,R2,ARSIZE    ;   push my AR
        JSR     R1,TRAVERSE     ;   traverse( node->right )
        ADDI    R2,R2,-ARSIZE   ;   pop my AR

        LIS     R3,')'
        ADDI    R2,R2,ARSIZE    ;   push my AR
        LOAD    R1,PDSPCH
        JSRS    R1,R1           ;   dspch( ')' )
        ADDI    R2,R2,-ARSIZE   ;   pop my AR

TRAVQUIT:                       ; }

        LOADS   R1,R2
        JUMPS   R1              ; return

        END