algorithm - Prolog のコードは、n 個のノードを持つ構造的に異なる完全なバイナリ ツリーをすべて生成します。

Question

Prolog で n 個の葉を持つ構造的に異なる完全二分木をすべて生成します。問題は葉の数が与えられ、すべての完全な二分木を出力します。ここで「フル」とは、内部ノードが左右に 2 つの子を持つ必要があることを意味します。

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

この再帰プロシージャには、2 番目の引数を「.」で統一する基本ケースがあります。葉の数が 1 の場合。葉の数が 1 より大きい場合、再帰的なステップが適用されます。この数は、葉の数を合計するゼロ以外の 2 つの新しい数に分割され、左と右の分岐を構築するために自身を呼び出します。

次に、この手順はすべてのツリーをコンソールにダンプします。

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