% Präfix-Prädikat aus Übungsaufgabe 20 b)
prefix([], _).
prefix([H|T], [H|Ys]) :- prefix(T, Ys).

% Reverse-Prädikat des Prolog-Systems
reverse([], []).
reverse([H|T], R) :- reverse(T, RT), append(RT, [H], R).

% Postfix-Prädikat
postfix(Xs, Ys) :-
    reverse(Xs, RXs),
    reverse(Ys, RYs),
    prefix(RXs, RYs).

% Postfix mit append
postfix(Xs, Ys) :-
    append(_, Xs, Ys).

% ----------------------------------------------------%

% Definition eines Binärbaums
% Ein leerer Baum ist ein leerer Baum
tree(empty).
tree(node(_, Left, Right)) :- tree(Left), tree(Right).

% Überprüfung, ob ein Element im Baum enthalten ist
membertree(X, node(X, _, _)).
membertree(X, node(_, Left, _)) :- membertree(X, Left).
membertree(X, node(_, _, Right)) :- membertree(X, Right).

% ----------------------------------------------------%

% Preorder
preorder(empty, []).
preorder(node(X, Left, Right), Ys) :-
    preorder(Left, Ls),
    preorder(Right, Rs),
    append([X|Ls], Rs, Ys).

% Postorder
postorder(empty, []).
postorder(node(X, Left, Right), Ys) :-
    postorder(Left, Ls),
    postorder(Right, Rs),
    append(Ls, Rs, Temp),
    append(Temp, [X], Ys).

% Roots
roots([], []).
roots([empty|Xbs], Ys) :- roots(Xbs, Ys).
roots([node(X, _, _)|Xbs], [X|Ys]) :- roots(Xbs, Ys).