prolog - Prolog 中枚举二叉树

Question

我正在尝试创建 Prolog 规则以在 Prolog 中以列表形式枚举“二叉树”。我是 Prolog 新手。

具有 0 个节点的树是一个空列表:

[]

具有 1 个节点的树是:

[[],[]]

具有 2 个节点的树有 2 种可能性:

[[],[[],[]]]

[[[],[]],[]]

等等。

这是我的规则:

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N,[Lc,Rc]) :-
  N > 1,
  bintree(N1,Lc),
  bintree(N2,Rc),
  N1 >= 0,
  N2 >= 0,
  N3 is N1+N2+1,
  N==N3.

对于 0 和 1 的查询显然是有效的。对于 N=2，它打印一种可能性，但在我输入分号以获得另一种可能性后给出错误。N>2的查询直接报错。错误总是相同的:

ERROR: >/2: Arguments are not sufficiently instantiated

我在一些网站上读到了此错误，但我无法弄清楚是什么导致了此错误。

感谢您提前提供的帮助。

Answer 1

使用 CLPFD 库将有助于提供一个干净的解决方案来生成尺寸。那么你就不需要一个奇怪的 (;)) integer/1 谓词，这可能会产生问题:

:- use_module(library(clpfd)).

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N, [L, R]) :-
    N #> 1,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

或更简单(感谢@repeat的建议):

bintree(0,[]).
bintree(N, [L, R]) :-
    N #> 0,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

?- bintree(4, L).
L = [[], [[], [[], [[], []]]]] ;
L = [[], [[], [[[], []], []]]] ;
L = [[], [[[], []], [[], []]]] ;
L = [[], [[[], [[], []]], []]] ;
L = [[], [[[[], []], []], []]] ;
L = [[[], []], [[], [[], []]]] ;
L = [[[], []], [[[], []], []]] ;
L = [[[], [[], []]], [[], []]] ;
L = [[[], [[], [[], []]]], []] ;
L = [[[], [[[], []], []]], []] ;
L = [[[[], []], []], [[], []]] ;
L = [[[[], []], [[], []]], []] ;
L = [[[[], [[], []]], []], []] ;
L = [[[[[], []], []], []], []] ;
false.

?-

CLPFD 是表达数字约束的一种很好的声明性方式。