list of the values in the leaf nodes of binary tree T

Question

List is the list of values in leaf nodes of a binary tree and I am trying to figure out how to output just that. This is giving me all the nodes but I need just the leaves.

lea(nil,[]).
lea(t(X,L,R),[X|L]) :-
   lea(L,L1), 
   lea(R,L2), 
   append(L1,L2,L).

Running this gives me:

?- lea(t(a,t(b,t(d,nil,nil),t(e,nil,nil)),t(c,nil,t(f,t(g,nil,nil),nil))),
       List). 
List = [a, b, d, e, c, f, g]

but I need

List = [d, e,g] 

Is it possible.

Afire

Answer 1

Let's use a DCG - a Definite Clause Grammar. We start with your original definition:

lea(T, L) :-
   phrase(values(T), L).

values(nil) -->
   [].
values(t(X,L,R)) -->
   [X],
   values(L),
   values(R).

Now, we need to restrict ourselves to those t/3 that are leaves. One possibility is to enumerate all cases:

lea2(T, L) :-
   phrase(leaves(T), L).

leaves(nil) -->
   [].
leaves(t(X,nil,nil)) -->
   [X].
leaves(t(_,L,R)) -->
   { dif(L+R,nil+nil) },
   leaves(L),
   leaves(R).

It would be even better and more efficient to use a conditional construct similar to if_/3. I want to leave this to someone interested.

Thibeault

Answer 2

First, we extend if_/3 to work with DCG's:

if_(C_1, Then_0, Else_0) -->                    % if_//3
   { call(C_1, Truth) },
   { functor(Truth, _, 0) },                    % safety check
   (  { Truth == true  } -> phrase(Then_0)
   ;  { Truth == false },   phrase(Else_0)
   ).

Using if_//3 and (=)/3 we can handle non-nil tree nodes with one clause (instead of two):

lea3(T, Ls) :-
   phrase(leaves(T), Ls).

leaves(nil) --> [].
leaves(t(X,L,R)) -->
   if_(L-R = nil-nil, [X], []),
   leaves(L),
   leaves(R).

Lustreware

not sure, but I think that (at least) in SWI-Prolog you can use (->)/2 construct directly – Saphra

No. (->)/2 commits immediately and may cut away part of the solution set. – Lustreware

Shouldn't call(Then_0) read phrase(Then_0)? Then you would no longer need add//1 and empty//0. And (=)/3 is more compact than equal_truth/3. Ergo if_(L-R = nil-nil, [X], []). – Thibeault

Answer 3

The same solution, not so far from first implementation, can be expressed as:

lea(nil, []).
lea(t(X, nil, nil), [X]).
lea(t(_, A, B), L) :-
    lea(A, L1),
    lea(B, L2),
    append(L1, L2, L)
    L \= [].

The last row (L \= []) can be removed (if you accept the possibility of find every solution).

Grangerize