Листья из бинарного дерева

Question

У меня есть бинарное дерево, как это:

tree(T) :- 
    T = btree("classes", 
       [ 
       btree("class1", 
        [ 
        btree("thomas", []) 
        ] 
      ), 
       btree("class2", 
        [ 
        btree("peter", []), 
        btree("liz", []) 
        ] 
      ), 
       btree("class3", 
        [ 
        btree("anna", []), 
        btree("jack", []) 
        ] 
      )] 
     ). 

Я хочу сделать предикат tree_leaf (T, листьев), который дает мне все листья из бинарного дерева. Предикат должен работать для каждого двоичного дерева.

Answer 1

Вот моя реализация:

tree_leaf(btree(X,[]),btree(X,[])). 
tree_leaf(btree(_,L),Leaf):-loop(L,Leaf). 

loop([X|_],Leaf):-tree_leaf(X,Leaf). 
loop([_|T],Leaf):-loop(T,Leaf). 

Пример:

?- tree(T),tree_leaf(T,Leaf). 
T = btree("classes", [btree("class1", [btree("thomas", [])]), btree("class2", [btree("peter", []), btree("liz", [])]), btree("class3", [btree("anna", []), btree("jack", [])])]), 
Leaf = btree("thomas", []) ; 
T = btree("classes", [btree("class1", [btree("thomas", [])]), btree("class2", [btree("peter", []), btree("liz", [])]), btree("class3", [btree("anna", []), btree("jack", [])])]), 
Leaf = btree("peter", []) ; 
T = btree("classes", [btree("class1", [btree("thomas", [])]), btree("class2", [btree("peter", []), btree("liz", [])]), btree("class3", [btree("anna", []), btree("jack", [])])]), 
Leaf = btree("liz", []) ; 
T = btree("classes", [btree("class1", [btree("thomas", [])]), btree("class2", [btree("peter", []), btree("liz", [])]), btree("class3", [btree("anna", []), btree("jack", [])])]), 
Leaf = btree("anna", []) ; 
T = btree("classes", [btree("class1", [btree("thomas", [])]), btree("class2", [btree("peter", []), btree("liz", [])]), btree("class3", [btree("anna", []), btree("jack", [])])]), 
Leaf = btree("jack", []) ; 
false. 

Как вы можете видеть, что я использовал дерево предикат, чтобы не набирать все дерево каждый раз, так что это возвращает также дерево T.
Вышеупомянутая реализация останавливается, когда находит лист, и для каждого узла, который не является листом, он вызывает tree_leaf/2 для каждого дочернего узла.