Prolog，从有序列表重建 BST 树

Question

我们熟知 BST 树的 inorder 实现。

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

但是，可以对 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 ) 将树与列表相关联:

inorder(nil) --> [].
inorder(t(Root, L, R)) -->
    inorder(L),
    [Root],
    inorder(R).

Ulrich Neumerkel 的 dissertation 中描述了我现在要应用的技巧。 驯服左递归。

"... we add another state for the number of tokens that can be used by newly encountered nonterminals. The number of tokens that will be read by the terminals within a single rule are therefore reserved in advance."

在我们的例子中:

inorder(nil, Es, Es) --> [].
inorder(t(Root, L, R), [_|Es0], Es) -->
    inorder(L, Es0, Es1),
    [Root],
    inorder(R, Es1, Es).

示例查询(Ls 省略):

?- Ls = [1,2,3], phrase(inorder(Tree, Ls, _), Ls).
Tree = t(1, nil, t(2, nil, t(3, nil, nil))) ;
Tree = t(1, nil, t(3, t(2, nil, nil), nil)) ;
Tree = t(2, t(1, nil, nil), t(3, nil, nil)) ;
Tree = t(3, t(1, nil, t(2, nil, nil)), nil) ;
Tree = t(3, t(2, t(1, nil, nil), nil), nil) ;
false.

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