Prolog中的代码生成具有n个节点的所有结构不同的完整二叉树 [英] Code in Prolog generate all structurally distinct full binary trees with n node

问题描述

在Prolog中用n个叶子生成所有结构上不同的完整二叉树。
问题是给定叶数，输出所有不同的完整二叉树。
完整在这里意味着任何内部节点都必须有左右两个孩子。

generate all structurally distinct full binary trees with n leaves in Prolog. The problem is given the number of leaves, output all distinct full binary trees. 'Full' here means any internal node must have two children, left and right.

推荐答案

要构建所有通过回溯的树木：

To build all the trees through backtracking:

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时，将执行递归步骤。它将此数字分为两个非零的新数字，这些数字将叶子的数量相加，并自行建立左右分支。

This recursive procedure has a base case that unifies the second argument with '.' when number of leaves is 1. The recursive step applies when the number of leaves is greater than 1. It splits this number in two non-zero new numbers which sum the number of leaves and calls itself to build the left and right branches.

然后此过程会将所有树转储到控制台：

Then this procedure will dump all trees to console:

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

这篇关于Prolog中的代码生成具有n个节点的所有结构不同的完整二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！