117 lines
2.6 KiB
Plaintext
117 lines
2.6 KiB
Plaintext
maxnodes%=100 ! set a limit to size of tree
|
|
content%=0 ! index of content field
|
|
left%=1 ! index of left tree
|
|
right%=2 ! index of right tree
|
|
DIM tree%(maxnodes%,3) ! create space for tree
|
|
'
|
|
OPENW 1
|
|
CLEARW 1
|
|
'
|
|
@create_tree
|
|
PRINT "Preorder: ";
|
|
@preorder_traversal(1)
|
|
PRINT ""
|
|
PRINT "Inorder: ";
|
|
@inorder_traversal(1)
|
|
PRINT ""
|
|
PRINT "Postorder: ";
|
|
@postorder_traversal(1)
|
|
PRINT ""
|
|
PRINT "Levelorder: ";
|
|
@levelorder_traversal(1)
|
|
PRINT ""
|
|
'
|
|
~INP(2)
|
|
CLOSEW 1
|
|
'
|
|
' Define the example tree
|
|
'
|
|
PROCEDURE create_tree
|
|
tree%(1,content%)=1
|
|
tree%(1,left%)=2
|
|
tree%(1,right%)=3
|
|
tree%(2,content%)=2
|
|
tree%(2,left%)=4
|
|
tree%(2,right%)=5
|
|
tree%(3,content%)=3
|
|
tree%(3,left%)=6
|
|
tree%(3,right%)=0 ! 0 is used for no subtree
|
|
tree%(4,content%)=4
|
|
tree%(4,left%)=7
|
|
tree%(4,right%)=0
|
|
tree%(5,content%)=5
|
|
tree%(5,left%)=0
|
|
tree%(5,right%)=0
|
|
tree%(6,content%)=6
|
|
tree%(6,left%)=8
|
|
tree%(6,right%)=9
|
|
tree%(7,content%)=7
|
|
tree%(7,left%)=0
|
|
tree%(7,right%)=0
|
|
tree%(8,content%)=8
|
|
tree%(8,left%)=0
|
|
tree%(8,right%)=0
|
|
tree%(9,content%)=9
|
|
tree%(9,left%)=0
|
|
tree%(9,right%)=0
|
|
RETURN
|
|
'
|
|
' Preorder traversal from given node
|
|
'
|
|
PROCEDURE preorder_traversal(node%)
|
|
IF node%<>0 ! 0 means there is no node
|
|
PRINT tree%(node%,content%);
|
|
preorder_traversal(tree%(node%,left%))
|
|
preorder_traversal(tree%(node%,right%))
|
|
ENDIF
|
|
RETURN
|
|
'
|
|
' Postorder traversal from given node
|
|
'
|
|
PROCEDURE postorder_traversal(node%)
|
|
IF node%<>0 ! 0 means there is no node
|
|
postorder_traversal(tree%(node%,left%))
|
|
postorder_traversal(tree%(node%,right%))
|
|
PRINT tree%(node%,content%);
|
|
ENDIF
|
|
RETURN
|
|
'
|
|
' Inorder traversal from given node
|
|
'
|
|
PROCEDURE inorder_traversal(node%)
|
|
IF node%<>0 ! 0 means there is no node
|
|
inorder_traversal(tree%(node%,left%))
|
|
PRINT tree%(node%,content%);
|
|
inorder_traversal(tree%(node%,right%))
|
|
ENDIF
|
|
RETURN
|
|
'
|
|
' Level order traversal from given node
|
|
'
|
|
PROCEDURE levelorder_traversal(node%)
|
|
LOCAL nodes%,first_free%,current%
|
|
'
|
|
' Set up initial queue of nodes
|
|
'
|
|
DIM nodes%(maxnodes%) ! some working space to store queue of nodes
|
|
current%=1
|
|
nodes%(current%)=node%
|
|
first_free%=current%+1
|
|
'
|
|
WHILE nodes%(current%)<>0
|
|
' add the children of current node onto queue
|
|
IF tree%(nodes%(current%),left%)<>0
|
|
nodes%(first_free%)=tree%(nodes%(current%),left%)
|
|
first_free%=first_free%+1
|
|
ENDIF
|
|
IF tree%(nodes%(current%),right%)<>0
|
|
nodes%(first_free%)=tree%(nodes%(current%),right%)
|
|
first_free%=first_free%+1
|
|
ENDIF
|
|
' print the current node content
|
|
PRINT tree%(nodes%(current%),content%);
|
|
' advance to next node
|
|
current%=current%+1
|
|
WEND
|
|
RETURN
|