Binary Tree In Prolog

Binäre Baum definiert werden können, in Bezug auf die 2 Prädikate:

• emptyBT, der leere binäre Baum.
• BTTree(N,T1,T2) das ist wahr, wenn N ist die Wurzel eines binären Baumes mit linkem Teilbaum T1 und rechten Teilbaum T2, wo alle Elemente in T1 sind weniger als oder gleich N und alle Elemente in T2 sind größer als N.

Schreiben Sie ein Prolog-Programm implementiert, dass die folgenden Prädikate:

• insert(I,T1,T2) ist wahr, wenn T2 ist die binäre Struktur, die aus, die ich eingefügt in binärer Baum T1.
• preorder(T,L) ist wahr, wenn L ist eine Liste von Knoten erzeugt, indem eine preorder-Traversierung des binären Baums T.
• inorder(T,L) ist wahr, wenn L ist eine Liste von Knoten erzeugt, die durch eine inorder-Traversierung des binären Baums T.
• postorder(T,L) ist wahr, wenn L ist eine Liste von Knoten erzeugt, die durch eine postorder-Traversierung des binären Baums T.
• search(T,I) ist wahr, wenn I enthalten ist, in den binären Baum T.
• height(T,H) ist wahr, wenn H ist die Höhe des binären Baumes T. Ein leerer Baum hat die Höhe 0 und ein Baum mit einem Element hat die Höhe 1.

---

Hier mein code bisher: ich habe keine Ahnung, ob sein Recht, jede Hilfe oder Hinweise würde
sehr geschätzt werden!

isempty(nil) :- !.
isempty(tree(nil,nil,nil)).

bTTree(tree(_,nil,nil)).
bTTree(tree(N,Left,nil)) :- Left@=<N.
bTTree(tree(N,nil,Right)) :- N@<Right.
bTTree(tree(_,Left,Right)) :- bTTree(Left), bTTree(Right).
bTTree(tree(N,Left,Right)) :- Left@=<N, N@<Right.

%traversals.
%preorder -- N,Left,Right

preorder(t,L) :- bTTree(t),
bTTree(t(N,Left,Right)),
append(N,[Left|Right],L).
preorder(t,L) :- bTTree(t(_,Left,_),
preorder(Left,L).
preorder(t,L) :- bTTree(t(_,_,Right),
preorder(Right,L).


%inorder -- Left,N,Right.

inorder(t,L) :- bTTree(t),
bTTree(t(N,Left,Right)),
append(Left,[N|Right],L).
inorder(t,L) :- bTTree(t(N,_,_)), inorder(N,L).
inorder(t,L) :- bTTree(t(_,_,Right)), inorder(Right,L).


%postorder -- Left,Right,N

postorder(t,L) :- bTTree(t),
bTTree(t(N,Left,Right)),
append(Left,[Right|N],L).
postorder(t,L) :- bTTree(t(_,_,Right)),
inorder(Right,L).
postorder(t,L) :- bTTree(t(N,_,_)),
append(_,[_|N],L).

search(t,I) :- bTTree(t(I,_,_)). %searches each node for I
search(t,I) :- bTTree(t(_,I,_)).
search(t,I) :- bTTree(t(_,_,I)).
search(t,I) :- bTTree(t(_,N,_)), search(N,I).%recursive method to search left branch for I
search(t,I) :- bTTree(t(_,_,N)), search(N,I).%recursive  " " " right branch for I

height(t,H) :- bTTree(t(nil,nil,nil)), H is 0.   %height of empty tree is 0
height(t,H) :- bTTree(t(_,nil,nil)), H is 1.     %height of single node Btree is 1
height(t,H) :-
   bTTree(t(_,Left,Right)),  %otherwise height of bTree is the max
   height(Left, H1),     %height of left or right branch plus 1
   height(Right, H2),
   H is max(H1,H2) + 1.

insert(I,t1,t2) :-
   bTTree(t1(X,L,_)),
   bTTree(t2(X,L,I)).
insert(I,t1,t2) :-
   bTTree(t1(nil,nil,nil)),
   bTTree(t2(I,nil,nil)).
insert(I,t1,t2) :-
   bTTree(t1(X,L,_)),
   bTTree(t2(X,L,I)).

InformationsquelleAutor Danny | 2013-07-30