Prolog，从有序列表重建 BST 树

Question

我们很清楚 inorder BST 树的实现。

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 的 Taming Left Recursion.

中有所描述

"... 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 系统的制表机制。

Answer 2

如果您喜欢我提出的技巧，唯一需要更改的可能是

:- use_module(carlo(snippets/when_)).

inorder(t(Root, L, R), List) -:- ...

现在

?- inorder(T,[1,2,3]).
T = t(1, nil, t(2, nil, t(3, nil, nil))) ;
T = t(1, nil, t(3, t(2, nil, nil), nil)) ;
T = t(2, t(1, nil, nil), t(3, nil, nil)) ;
T = t(3, t(1, nil, t(2, nil, nil)), nil) ;
T = t(3, t(2, t(1, nil, nil), nil), nil) ;
false.

Prolog，从有序列表重建 BST 树

Prolog, reconstruct BST trees from inorder list

prolog

dcg