Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

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



See also

   Wikipedia article:   Tree traversal.


 
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
 