Tree traversal: Difference between revisions

=={{header|8080 Assembly}}==

<syntaxhighlight lang="asm8080"> org 100h

jmp demo

;;; Traverse tree at DE according to method at BC.

;;; Call routine at HL with DE=<value> for each value encounterd.

travrs: shld trvcb+1 ; Store routine pointer

xchg ; Tree in HL

push b ; Jump to method BC

ret

;;; Preorder traversal

preo: mov a,h

ora l

rz ; Null node = stop

mov e,m

inx h

mov d,m ; Load value

inx h

push h ; Handle value

call trvcb

pop h ; Left node

mov e,m

inx h

mov d,m

inx h

push h ; Save pointer

xchg

call preo

pop h

mov e,m

inx h ; Right node

mov d,m

xchg

jmp preo

;;; Inorder traversal

ino: mov a,h

ora l

rz ; Null node = stop

mov e,m

inx h

mov d,m ; Load value

inx h

push d ; Save value on stack

mov e,m

inx h

mov d,m

inx h ; Load left node

push h ; Save pointer on stack

xchg

call ino ; Traverse left node

pop h

pop d ; Get value

push h

call trvcb ; Handle value

pop h

mov e,m

inx h

mov d,m

xchg

jmp ino ; Traverse right node

;;; Postorder traversal

posto: mov a,h

ora l

rz ; Null node = stop

mov e,m

inx h

mov d,m ; Load value

inx h

push d ; Keep value on stack

mov e,m

inx h

mov d,m

inx h ; Load left node

push h

xchg

call posto ; Traverse left node

pop h

mov e,m

inx h

mov d,m ; Load right node

xchg

call posto ; Traverse right node

pop d ; Get value from stack

jmp trvcb ; Handle value

;;; Level-order traversal

lvlo: shld queue ; Store current node at beginning of queue

lxi h,queue ; HL = Queue start pointer

lxi b,queue+2 ; BC = Queue end pointer

lvllp: mov a,h ; When start == end, stop

cmp b

jnz lvlt ; Not equal

mov a,l

cmp c

rz ; Equal = stop

lvlt: mov e,m ; Load current node in DE

inx h

mov d,m

inx h

mov a,d ; Null node = ignore

ora e

jz lvllp

push h ; Keep queue start pointer

xchg ; HL = current node

mov e,m ; Load value into DE

inx h

mov d,m

inx h

push h ; Keep pointer to left and right nodes

push b ; And pointer to end of queue

call trvcb ; Handle value

pop b ; Restore pointer to end of queue

pop h ; Restore pointer to left and right nodes

mvi d,4 ; D = copy counter

lvlcp: mov a,m ; Copy left and right nodes to queue

stax b

inx h

inx b

dcr d

jnz lvlcp

pop h ; Restore queue stack pointer

jmp lvllp

trvcb: jmp 0 ; Callback pointer

;;; Run examples

demo: lhld 6 ; Move stack to top of memory

sphl

lxi h,0 ; So we can still RET out of the program

push h

lxi h,orders

order: mov e,m ; Get string

inx h

mov d,m

inx h

mov a,e ; 0 = done

ora d

rz

push h ; Print string

call print

pop h

mov c,m ; Load method in BC

inx h

mov b,m

inx h

push h

lxi d,tree ; Tree in DE

lxi h,cb ; Callback in HL

call travrs ; Traverse the tree

lxi d,nl

call print ; Newline

pop h ; Restore table pointer

jmp order

;;; Print the tree value. They're all <10 for the example, so we

;;; don't need multiple digits.

cb: mvi a,'0'

add e

sta nstr

lxi d,nstr

print: mvi c,9 ; CP/M print string call

jmp 5

nstr: db '* $'

nl: db 13,10,'$'

;;; Example tree

tree: dw 1, node2, node3

node2: dw 2, node4, node5

node3: dw 3, node6, 0

node4: dw 4, node7, 0

node5: dw 5, 0, 0

node6: dw 6, node8, node9

node7: dw 7, 0, 0

node8: dw 8, 0, 0

node9: dw 9, 0 ,0

;;; Table of names and orders

orders: dw spreo,preo

dw sino,ino

dw sposto,posto

dw slvlo,lvlo

dw 0

spreo: db 'Preorder: $'

sino: db 'Inorder: $'

sposto: db 'Postorder: $'

slvlo: db 'Level-order: $'

queue: equ $ ; Put level-order queue on heap</syntaxhighlight>

{{out}}

<pre>Preorder: 1 2 4 7 5 3 6 8 9

Inorder: 7 4 2 5 1 8 6 9 3

Postorder: 7 4 5 2 8 9 6 3 1

Level-order: 1 2 3 4 5 6 7 8 9</pre>