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.


tree :-
	Tree= [1,
	        [2,
		   [4,
		     [7, nil, nil],
		     nil], 
		   [5, nil, nil]],
	        [3,
		 [6,
		   [8, nil, nil], 
		   [9,nil, nil]], 
		 nil]],
 
	write('preorder    : '), preorder(Tree), nl,
	write('inorder     : '), inorder(Tree), nl,
	write('postorder   : '), postorder(Tree), nl,
	write('level-order : '), level_order([Tree]).
 
preorder(nil).
preorder([Node, FG, FD]) :-
	format('~w ', [Node]),
	preorder(FG),
	preorder(FD).
 
 
inorder(nil).
inorder([Node, FG, FD]) :-
	inorder(FG),
	format('~w ', [Node]),
	inorder(FD).
 
postorder(nil).
postorder([Node, FG, FD]) :-
	postorder(FG),
	postorder(FD),
	format('~w ', [Node]).
 
 
level_order([]).
 
level_order(A) :-
	level_order_(A, U-U, S),
	level_order(S).
 
level_order_([], S-[],S).
 
level_order_([[Node, FG, FD] | T], CS, FS) :-
	format('~w ', [Node]),
	append_dl(CS, [FG, FD|U]-U, CS1),
	level_order_(T, CS1, FS).
 
level_order_([nil | T], CS, FS) :-
	level_order_(T, CS, FS).
 
 
append_dl(X-Y, Y-Z, X-Z).
 