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.


 
component BinaryTreeTraversals (Tree, Element);
type Tree;
type Node = Tree;
     Tree (LeftTree = Tree, Element, RightTree = Tree) -> Tree;
     Leaf (Element)                                    -> Node;
     Node (Tree)                                       -> Node;
     Item (Node)                                       -> Element;
 
     Preorder (Tree)                                   -> multi (Node);
     Inorder (Tree)                                    -> multi (Node);
     Postorder (Tree)                                  -> multi (Node);
     Level_order(Tree) 		                       -> multi (Node);
begin
     Tree (Lefttree, Item, Righttree) = Tree: [ Lefttree; Item; Righttree ];
     Leaf (anItem) = Tree (null(Tree), anItem, null(Tree) );
     Node (aTree) = aTree;
     Item (aNode) = aNode.Item;
 
     Preorder (=null(Tree)) = no(Tree);
     Preorder (T) = ( T, Preorder (T.Lefttree), Preorder (T.Righttree));
 
     Inorder (=null(Tree)) = no(Tree);
     Inorder (T) = ( Inorder (T.Lefttree), T, Inorder (T.Righttree));
 
     Postorder (=null(Tree)) = no(Tree);
     Postorder (T) = ( Postorder (T.Lefttree), Postorder (T.Righttree), T);	
 
     Level_order(T) = [ Queue = {T};
			 node = Tree:items(Queue);
			   [ result(node);
			     add(Queue, node.Lefttree) when valid(node.Lefttree); 	
 			     add(Queue, node.Righttree) when valid(node.Righttree); 	
			   ];
			 no(Tree);
		       ];
end component BinaryTreeTraversals;
 