Prolog,从inorder列表重建BST树

Question

我们很清楚inorderBST树的实现.

inorder(nil, []).
inorder(t(Root, L, R), List) :-
    inorder(L, ListLeft),
    inorder(R, ListRight),
    append(ListLeft, [Root|ListRight], List).

但是,它可以列表吗？我的意思是重建所有可能的BST树,例如:

inorder(X, [1,2,3]).
X = t(1, nil, t(2, nil, t(3, nil, nil))));
X = t(3, t(2, t(1, nil, nil), nil), nil), nil);
X = t(2, t(1, nil, nil), t(3, nil, nil));
false.

对我来说似乎不可能.

Answer 1

首先，让我们使用定语从句语法( dcg ) 将树与列表相关联：

中序（零）--> []。
中序（t（根，L，R））-->
    中序(L),
    [根]，
    有序（R）。

我现在要应用的技巧在 Ulrich Neumerkel 的论文Taming Left Recursion中有描述。

“...我们为新遇到的非终端可以使用的令牌数量添加了另一个状态。因此，提前保留了单个规则中终端将读取的令牌数量。”

在我们的例子中：

中序（零，Es，Es ) --> [].
inorder(t(根, L, R), [_|Es0] , Es ) -->
    中序（L，Es0，Es1），
    [根]，
    中序（R，Es1，Es）。

示例查询（Ls省略）：

?- Ls = [1,2,3], 短语(inorder(Tree, Ls, _), Ls)。
树 = t(1, nil, t(2, nil, t(3, nil, nil))) ;
树 = t(1, nil, t(3, t(2, nil, nil), nil)) ;
树 = t(2, t(1, nil, nil), t(3, nil, nil)) ;
树 = t(3, t(1, nil, t(2, nil, nil)), nil) ;
树 = t(3, t(2, t(1, nil, nil), nil), nil) ;
错误的。

解决此类问题的另一种方法是使用 Prolog 系统的制表机制。