%%  Datei:  baumtraversierung.pl
%%
%%  Programmierkurs Prolog (Sommersemester 2002),
%%  Material fuer Uebungsblatt 5, Aufgabe 5.2
%%
%%  Baumtraversierung
%%
%%  (Beispiel von den Folien vom Programmierkurs Prolog im 
%%  Sommersemster 1998 von Thorsten)
%%
%%  Repraesentation von Baeumen durch Listen, rekursive
%%  Definition binaerer Baeume:
%%  * Ein binaerer Baum B ist entweder leer:   B = []
%%    oder
%%  * besteht aus einer Wurzel und zwei Teilbaeumen:
%%    B = [WurzelInhalt,LinkerTeilbaum,RechterTeilbaum]
%%
%%  Beispiel:
%%    [a,[b,[d,[h,[],[]],[i,[],[]]],
%%          [e,[j,[],[]],[k,[],[]]]],
%%       [c,[f,[l,[],[]],[m,[],[]]],
%%          [g,[n,[],[]],[o,[],[]]]]]

beispielBaum(B) :-
    B = [a,[b,[d,[h,[],[]],[i,[],[]]],
              [e,[j,[],[]],[k,[],[]]]],
           [c,[f,[l,[],[]],[m,[],[]]],
              [g,[n,[],[]],[o,[],[]]]]].


%%  Algorithmus zur Baumtraversierung:

operate(X) :- write(X), write(' ').

prefix([]).
prefix([Value,Left,Right]) :-
    operate(Value),
    prefix(Left),
    prefix(Right).

infix([]).
infix([Value,Left,Right]) :-
    infix(Left),
    operate(Value),
    infix(Right).

postfix([]).
postfix([Value,Left,Right]) :-
    postfix(Left),
    postfix(Right),
    operate(Value).

traverse(prefix,Tree):- 
    prefix(Tree).
traverse(infix,Tree) :-
    infix(Tree).
traverse(postfix,Tree) :-
    postfix(Tree).


%%  Beispielaufrufe:
%%  (a) beispielBaum(B), traverse(prefix,B).
%%      liefert 'a b d h i e j k c f l m g n o '.
%%  (b) beispielBaum(B), traverse(infix,B).
%%      liefert 'h d i b j e k a l f m c n g o '.
%%  (c) beispielBaum(B), traverse(postfix,B).
%%      liefert 'h i d j k e b l m f n o g c a '.