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

List es la lista de valores en nodos hoja de un árbol binario y estoy tratando de encontrar la forma de generar solo eso. Esto me está dando todos los nodos pero necesito solo 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.

Usemos un DCG – una Gramática de Clave Definitiva. 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, tenemos que 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.

Primero, ampliamos if_/3 para que funcione con los 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 (=)/3 podemos manejar nodos de árboles 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_(LR = nil-nil, [X], []), leaves(L), leaves(R). 

La misma solución, no tan lejos de la primera implementación, se puede express 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).