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.


MODE VALUE = INT;
PROC value repr = (VALUE value)STRING: whole(value, 0);
 
MODE NODES = STRUCT ( VALUE value, REF NODES left, right);
MODE NODE = REF NODES;
 
PROC tree = (VALUE value, NODE left, right)NODE:
  HEAP NODES := (value, left, right);
 
PROC preorder = (NODE node, PROC (VALUE)VOID action)VOID:
  IF node ISNT NODE(NIL) THEN
    action(value OF node);
    preorder(left OF node, action);
    preorder(right OF node, action)
  FI;
 
PROC inorder = (NODE node, PROC (VALUE)VOID action)VOID:
  IF node ISNT NODE(NIL) THEN
    inorder(left OF node, action);
    action(value OF node);
    inorder(right OF node, action)
  FI;
 
PROC postorder = (NODE node, PROC (VALUE)VOID action)VOID:
  IF node ISNT NODE(NIL) THEN
    postorder(left OF node, action);
    postorder(right OF node, action);
    action(value OF node)
  FI;
 
PROC destroy tree = (NODE node)VOID: 
  postorder(node, (VALUE skip)VOID: 
  # free(node) - PR garbage collect hint PR #
    node := (SKIP, NIL, NIL)
  );
 
# helper queue for level order #
MODE QNODES = STRUCT (REF QNODES next, NODE value);
MODE QNODE = REF QNODES;
 
 
MODE QUEUES = STRUCT (QNODE begin, end);
MODE QUEUE = REF QUEUES;
 
PROC enqueue = (QUEUE queue, NODE node)VOID:
(
  HEAP QNODES qnode := (NIL, node);
  IF end OF queue ISNT QNODE(NIL) THEN
    next OF end OF queue
  ELSE
    begin OF queue
  FI := end OF queue := qnode
);
 
PROC queue empty = (QUEUE queue)BOOL:
  begin OF queue IS QNODE(NIL);
 
PROC dequeue = (QUEUE queue)NODE:
(
  NODE out := value OF begin OF queue;
  QNODE second := next OF begin OF queue;
# free(begin OF queue); PR garbage collect hint PR #
  QNODE(begin OF queue) := (NIL, NIL);
  begin OF queue := second;
  IF queue empty(queue) THEN
    end OF queue := begin OF queue
  FI;
  out
);
 
PROC level order = (NODE node, PROC (VALUE)VOID action)VOID:
(
  HEAP QUEUES queue := (QNODE(NIL), QNODE(NIL));
  enqueue(queue, node);
  WHILE NOT queue empty(queue)
  DO
    NODE next := dequeue(queue);
    IF next ISNT NODE(NIL) THEN
      action(value OF next);
      enqueue(queue, left OF next);
      enqueue(queue, right OF next)
    FI
  OD
);
 
PROC print node = (VALUE value)VOID:
  print((" ",value repr(value)));
 
main: (
  NODE node := tree(1,
                tree(2,
                     tree(4,
                          tree(7, NIL, NIL),
                          NIL),
                     tree(5, NIL, NIL)),
                tree(3,
                     tree(6,
                          tree(8, NIL, NIL),
                          tree(9, NIL, NIL)),
                     NIL));
 
  MODE TEST = STRUCT(
    STRING name, 
    PROC(NODE,PROC(VALUE)VOID)VOID order
  );
 
  PROC test = (TEST test)VOID:(
    STRING pad=" "*(12-UPB name OF test);
    print((name OF test,pad,": "));
    (order OF test)(node, print node);
    print(new line)
  );
 
  []TEST test list = (
    ("preorder",preorder),
    ("inorder",inorder),
    ("postorder",postorder),
    ("level order",level order)
  );
 
  FOR i TO UPB test list DO test(test list[i]) OD;
 
  destroy tree(node)
)