prolog - 使用 Prolog 获取所有可能的二叉树？

Question

我知道有很多关于定义二叉树来检查某物是否是二叉树的问题，但我找不到在“相反方向”解决这个问题的线程。

Why does your definition of binary tree not return all possible binary trees when called as "es_arbol(X)"? Explain in detail and try to implement a different definition that does return all possible binary tree structures.

好吧，基本上我陷入了作业的这一部分。在定义我的二叉树验证函数后，我注意到当不带参数调用时，它只返回通过其右侧节点“生长”的树，或者在至少这就是我解释 swi-prolog 输出的方式。我没有得到的是，假设我的定义是正确的，Prolog 应该能够以两种方式构造它们。如果没有，我希望有人能指出我的正确方向制定二叉树的更通用定义的方向，或者解释为什么我的定义不够充分。

这是我的定义:

es_arbol(nil).
es_arbol(arbol(_,I,D)) :- es_arbol(I), es_arbol(D).

Answer 1

你的谓词沿着一个分支生成无限数量的树的原因是因为你有多个递归，并且像任何语言一样，Prolog将继续进行它找到的第一个递归调用，直到它返回，在这种情况下，永不。所以你总是在树的一条腿上递归。换句话说，每棵树(左子树和右子树)中至少有两个变量，它们具有无限种可能性。

二叉树在二维上有无限数量的递归可能性。您需要一种使用单维指标对树进行排序的方法。其中一种指标可能是树中的节点数。如果按节点计数对树进行排序，从节点计数 0 开始，则对于每个节点计数，可以枚举有限数量的树。这是一般的工作方式:

1. Nodes 是有效的节点数量
2. nil 是具有 0 个节点的有效二叉树
3. arbol(_, TL, TR) 是一个有效的二叉树，如果 NL 和 NR2 则具有 N 个节点> 和 N-1 和 TL 相加是一个由 NL 节点组成的有效二叉树，TR 是一个NR 节点的有效二叉树。由于Prolog会在回溯到该点之前找到给定点的所有解决方案，因此它将首先搜索具有给定节点数的所有树，然后回溯到新的有效节点数。

在 Prolog 中，它看起来像这样。

:- use_module(library(clpfd)).

es_arbol(Tree) :-
    length(_, Nodes),
    es_arbol(Tree, Nodes).

我使用 length/2 来“生成”Nodes 0、1、2 等值。es_arbol(Tree)将从 0 开始的连续节点数的二叉树成功。对于给定的节点数 Nodes，它将找到之前的 es_arbol(Tree, Nodes) 的所有解决方案最终失败并再次回溯到 length(_, Nodes)，这将在 Node 的下一个值上成功。

es_arbol(nil, 0).
es_arbol(arbol(_,TreeL,TreeR), N) :-
    N #> 0,
    NL + NR #= N - 1,
    NL #>= 0, NR #>= 0,
    es_arbol(TreeL, NL),
    es_arbol(TreeR, NR).

基本情况很简单。 nil 是具有 0 个节点的树。递归情况表示，arbol(_,L,R) 是一个具有 N 个节点的二叉树，如果 N > 0，NL 和NR是非负整数，加起来为N，TL和TR是长度分别为 NL 和 NR 的二叉树。

运行上述代码的结果是:

?- es_arbol(Tree).
Tree = nil ;
Tree = arbol(_G258, nil, nil) ;
Tree = arbol(_G17, nil, arbol(_G157, nil, nil)) ;
Tree = arbol(_G17, arbol(_G200, nil, nil), nil) ;
Tree = arbol(_G14, nil, arbol(_G154, nil, arbol(_G593, nil, nil))) ;
Tree = arbol(_G14, nil, arbol(_G154, arbol(_G603, nil, nil), nil)) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, nil, nil)) ;
Tree = arbol(_G14, arbol(_G53, nil, arbol(_G193, nil, nil)), nil) ;
Tree = arbol(_G14, arbol(_G53, arbol(_G236, nil, nil), nil), nil) ;
Tree = arbol(_G14, nil, arbol(_G100, nil, arbol(_G214, nil, arbol(_G354, nil, nil)))) ;
Tree = arbol(_G14, nil, arbol(_G100, nil, arbol(_G214, arbol(_G397, nil, nil), nil))) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G216, nil, nil), arbol(_G277, nil, nil))) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G139, nil, arbol(_G279, nil, nil)), nil)) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G139, arbol(_G322, nil, nil), nil), nil)) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, nil, arbol(_G664, nil, nil))) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, arbol(_G674, nil, nil), nil)) ;
Tree = arbol(_G14, arbol(_G132, nil, arbol(_G272, nil, nil)), arbol(_G676, nil, nil)) .
...

<小时/>正如 @false 在评论中指出的那样，在应用枚举约束的情况下，使用 CLP(FD) 并不是最有效的方法。另一种更有效的方法是使用 Between/3 :

es_arbol(nil, 0).
es_arbol(arbol(_,TreeL,TreeR), N) :-
    N > 0,
    N1 is N - 1,
    between(0, N1, NL),
    NR is N1 - NL,
    es_arbol(TreeL, NL),
    es_arbol(TreeR, NR).