prolog - lista de los valores en los nodos hoja del árbol binario T

binary-tree dcg

Question

Lista es la lista de valores en los nodos de hoja de un árbol binario y estoy tratando de descubrir cómo generar exactamente eso. Esto me está dando todos los nodos pero solo necesito las hojas.

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

Ejecutar esto me da:

?- 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]

Pero yo necesito

List = [d, e,g] 

Es posible.

Answer 1

La misma solución, no muy lejos de la primera implementación, se puede expresar como:

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

La última fila ( L /= [] ) se puede eliminar (si acepta la posibilidad de encontrar todas las soluciones).

Answer 2

Primero, ampliamos if_/3 para trabajar con DCG:

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

Usando if_//3 y if_/3 podemos manejar nodos de árbol no nulos con una cláusula (en lugar de dos):

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

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

Answer 3

Usemos un DCG: una gramática de cláusula definida. Comenzamos con su definición original:

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

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

Ahora, necesitamos restringirnos a esos t/3 que son hojas. Una posibilidad es enumerar todos los casos:

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

Sería aún mejor y más eficiente usar una construcción condicional similar a if_/3 . Quiero dejar esto a alguien interesado.