prolog - 二叉树 T 的叶节点中的值列表

Question

List 是二叉树叶节点中的值列表，我试图弄清楚如何输出它。这给了我所有的节点，但我只需要叶子。

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

运行这个给我:

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

但是我需要

List = [d, e,g] 

是否可以。

Answer 1

让我们使用 DCG - 定语从句语法。我们从您的原始定义开始:

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

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

现在，我们需要将自己限制在那些 t/3那是叶子。一种可能性是枚举所有情况:

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

使用类似于 if_/3 的条件结构会更好、更有效。 .我想把这个留给感兴趣的人。