algorithm - Prolog 中的代码生成所有结构不同的具有 n 个节点的完整二叉树

Question

在 Prolog 中生成所有具有 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).
(.(.(..)))
(.((..).))
((..)(..))
((.(..)).)
(((..).).)