Binary Tree In Prolog

Question

A binary tree can be defined in terms of 2 predicates:

• emptyBT, the empty binary tree.

• BTTree(N,T1,T2) that is true if N is the root of a binary tree with left subtree T1 and right subtree T2, where all the items in T1 are less than or equal to N and all the items in T2 are greater than N.

Write a Prolog program that implements the following predicates:

• insert(I,T1,T2) is true if T2 is the binary tree resulting from I being inserted into binary tree T1.

• preorder(T,L) is true if L is a list of nodes generated by a preorder traversal of the binary tree T.

• inorder(T,L) is true if L is a list of nodes generated by a inorder traversal of the binary tree T.

• postorder(T,L) is true if L is a list of nodes generated by a postorder traversal of the binary tree T.

• search(T,I) is true if I is contained in the binary tree T.

• height(T,H) is true if H is the height of the binary tree T. An empty tree has height 0 and a tree with one item has height 1.

---

Here's my code so far: I have no idea if its right, any help or pointers would be greatly appreciated!

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)).

Solution

Just to be clear, I think that your code cannot work, and doesn't show any useful coding practice. Then I implemented using a compact notation, where - it's the empty tree, and a tree is t(LeftSubtree, Int, RightSubtree). As required, all ints in LeftSubtree are less than Int, etc...

ins(I, -, t(-, I, -)).
ins(I, t(L, X, R), t(P, Y, Q)) :-
    (   I < X
    ->  ins(I, L, U),
        (P, Y, Q) = (U, X, R)
    ;   I > X
    ->  ins(I, R, U),
        (P, Y, Q) = (L, X, U)
    ;   (P, Y, Q) = (L, X, R)  % already in, nothing to do
    ).

inl([N|Ns], T0, T) :-
    ins(N, T0, T1),
    inl(Ns, T1, T).
inl([], T, T).

inl/3 it's an utility that insert all the ints in a tree and 'returns' the result. Some test:

inl([3,6,1],-,X).
X = t(t(-, 1, -), 3, t(-, 6, -)) ;
false.

?- inl([3,6,1,1],-,X).
X = t(t(-, 1, -), 3, t(-, 6, -)) .

?- inl([3,6,1,1,4],-,X).
X = t(t(-, 1, -), 3, t(t(-, 4, -), 6, -)) ;
false.

Comments

[Danny]

I haven't looked at prolog in quite a while very rusty. Does your answer work? Thanks for taking the time to look at it.