Код в Прологе генерирует все структурно отличные полные двоичные деревья с n узлом

Question

Генерировать все структурно отличные полные двоичные деревья с n листьями в Прологе. Задача задается количеством листьев, выводятся все отдельные полные двоичные деревья. "Полный" здесь означает, что любой внутренний узел должен иметь двух дочерних элементов, левого и правого.

Answer 1

Чтобы построить все деревья через возвратный путь:

full_tree(Leaves, [LTree, RTree]):-
  Leaves > 1,
  TLeaves is Leaves-1,
  between(1, TLeaves, LLeaves),
  RLeaves is Leaves-LLeaves,
  full_tree(LLeaves, LTree),
  full_tree(RLeaves, RTree).
full_tree(1, '.').

Эта рекурсивная процедура имеет базовый случай, который объединяет второй аргумент с "." когда число листьев равно 1. Рекурсивный шаг применяется, когда число листьев больше 1. Он делит это число на два ненулевых новых числа, которые суммируют количество листьев, и вызывает себя для построения левой и правой ветвей.

Затем эта процедура выведет все деревья на консоль:

dump_all_trees(Leaves):-
  full_tree(Leaves, Tree),
  dump_full_tree(Tree),
  nl,
  fail.
dump_all_trees(_).

dump_full_tree([LTree, RTree]):-
  write('('),
    dump_full_tree(LTree),
    dump_full_tree(RTree),
  write(')'),
  !.
dump_full_tree(Leaf):- write(Leaf).

Прецедент:

?- dump_all_trees(4).
(.(.(..)))
(.((..).))
((..)(..))
((.(..)).)
(((..).).)