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.


 
:- object(tree_traversal).
 
    :- public(orders/1).
    orders(Tree) :-
        write('Pre-order:   '), pre_order(Tree), nl,
        write('In-order:    '), in_order(Tree), nl,
        write('Post-order:  '), post_order(Tree), nl,
        write('Level-order: '), level_order(Tree).
 
    :- public(orders/0).
    orders :-
        tree(Tree),
        orders(Tree).
 
    tree(
        t(1,
            t(2,
                t(4,
                    t(7, t, t),
                    t
                ),
                t(5, t, t)
            ),
            t(3,
                t(6,
                    t(8, t, t),
                    t(9, t, t)
                ),
                t
            )
        )
    ).
 
    pre_order(t).
    pre_order(t(Value, Left, Right)) :-
        write(Value), write(' '),
        pre_order(Left),
        pre_order(Right).
 
    in_order(t).
    in_order(t(Value, Left, Right)) :-
        in_order(Left),
        write(Value), write(' '),
        in_order(Right).
 
    post_order(t).
    post_order(t(Value, Left, Right)) :-
        post_order(Left),
        post_order(Right),
        write(Value), write(' ').
 
    level_order(t).
    level_order(t(Value, Left, Right)) :-
        % write tree root value
        write(Value), write(' '),
        % write rest of the tree
        level_order([Left, Right], Tail-Tail).
 
    level_order([], Trees-[]) :-
        (   Trees \= [] ->
            % print next level
            level_order(Trees, Tail-Tail)
        ;   % no more levels
            true
        ).
    level_order([Tree| Trees], Rest0) :-
        (   Tree = t(Value, Left, Right) ->
            write(Value), write(' '),
            % collect the subtrees to print the next level
            append(Rest0, [Left, Right| Tail]-Tail, Rest1),
            % continue printing the current level 
            level_order(Trees, Rest1)
        ;   % continue printing the current level
            level_order(Trees, Rest0)
        ).
 
    % use difference-lists for constant time append
    append(List1-Tail1, Tail1-Tail2, List1-Tail2).
 
:- end_object.
 