Search code examples
listprologbinary-treedcg

Find the elements on even level of a binary tree in Prolog

I'm trying to find all the elements that are placed on even level in a binary tree and place them in a list. This is what i tried:

concat([],L,L).
concat([H|T], L, [L|LRez]) :- concat(T,L,LRez).

find(R, t(_, R, _), 0).
find(X, t(S, R, D),P) :- X < R, find(X, S, P1), P is P1+1.
find(X, t(S, R, D),P) :- X >= R,find(X, D, P2), P is P2+1.

level(T, LRrez):- lvl(T, T, LRez).
lvl(nil, nil, []).
lvl(T, t(S,R,D),[R|LRez] ) :- find(R,T,P), even(P), lvl(T, S, LRez1), lvl(T,D,LRez2), 
                        concat(LRez1,LRez2,Lrez).
lvl(T,t(S,R,D),LRez) :- find(R,T,P), \+even(P), lvl(T, S, LRez1), lvl(T, D,LRez2), 
                        concat(LRez1,LRez2,Lrez).

I use find to find the level of the number in the tree and i defined even previously. This is not working. Thanks in advance.

Solution

  • Use !

    If DCGs are new to you, jumpstart by reading Markus Triska's informative yet concise DCG Primer.

    take_even(nil)      --> [].
take_even(t(L,M,R)) --> [M], skip_odd(L), skip_odd(R).

skip_odd(nil)      --> [].
skip_odd(t(L,_,R)) --> take_even(L), take_even(R).

    Sample query:

    ?- phrase(take_even(t(nil,0,t(nil,1,t(nil,2,nil)))), Es).
Es = [0, 2].