TITLE	"Tree demo with traversal"
	USE	"hawk.h"
	USE	"stdio.h"

; displacements into the record structure of a tree node
LEFT	=	0	; children
RIGHT	=	4
VALUE	=	8	; integer value of this node
NODESIZE=	12

; tool for statically construct tree nodes
MACRO	TREENODE left,right,value
 W left
 W right
 W value
ENDMAC

; a tree to traverse
N1:	TREENODE NULL,NULL,1
N2:	TREENODE N1  ,NULL,2
N3:	TREENODE N2  ,N5  ,3
N4:	TREENODE NULL,NULL,4
N5:	TREENODE N4  ,N6  ,5
N6:	TREENODE NULL,NULL,6

ROOT	=	N3

	SUBTITLE "traverse -- recursive tree traversal"

; traverse( root ) -- does an inorder traversal, printing each node's value

; AR for traverse
RETAD	=	0
NODE	=	4
ARSIZE	=	8

TRAVERSE:
	; expects: r3 = root tree or subtree to traverse
	STORES	R1,R2
	STORE	R3,R2,NODE	; node = parameter
	ADDSI	R2,ARSIZE

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

	LOAD	R3,R3,LEFT	;   -- parameter
	JSR	R1,TRAVERSE	;   traverse( node->left )

	LOAD	R3,R2,NODE-ARSIZE
	LOAD	R3,R3,VALUE	;   -- parameter
	LIS	R4,3		;   -- parameter
	LIL	R1,PUTDEC
	JSRS	R1,R1		;   putdec( node->value, 3 )

	LOAD	R3,R2,NODE-ARSIZE
	LOAD	R3,R3,RIGHT	;   -- parameter
	JSR	R1,TRAVERSE	;   traverse( node->right )

TRAVQT:				; }
	ADDSI	R2,-ARSIZE
	LOADS	PC,R2

	SUBTITLE "main program"
	INT	MAIN
	S	MAIN

; AR for main
RETAD	=	0
ARSIZE	=	4

MAIN:
	STORES	R1,R2
	ADDSI	R2,ARSIZE

	LEA	R3,ROOT		; -- param
	JSR	R1,TRAVERSE	; call traverse( root )

	ADDSI	R2,-ARSIZE
	LOADS	PC,R2

	END