在 Prolog 中基于遍历查找二叉搜索树

Question

我正在尝试编写一个Prolog谓词，根据给定的遍历顺序给出可能的二叉搜索树。我选择使用如下表示法来表示树：t(根节点, 左子树, 右子树)，叶子节点只是t(数字)，当子树不存在时其值为nil。

以下是我目前为止的代码（仅适用于后序遍历）：

post(nil, []).
post(t(X), [X]).
post(t(N, L, R), T) :-
    post(L, TL), post(R, TR),
    append([TL, TR, [N]], T).

这在某种程度上起到了不错的作用，但在另一方向上卡住了：

?- post(t(8, t(5, t(2), nil), t(12, t(9), t(16))), Trav).
Trav = [2, 5, 9, 16, 12, 8].

?- post(Tree, [2, 5, 9, 16, 12, 8]).
Tree = t(8, nil, t(12, nil, t(16, nil, t(9, nil, t(5, nil, t(2)))))) ;
Tree = t(8, nil, t(12, nil, t(16, nil, t(9, nil, t(5, nil, t(2, nil, nil)))))) ;
[execution hangs here]

---

我意识到post不需要二叉搜索树，也就是说没有要求左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点，所以我写了这个：

tree(t(_)).
tree(nil).
tree(t(N, L, R)) :-
    tree(L), tree(R),
    ( L = t(NL, _, _) -> NL < N ; true ),
    ( R = t(NR, _, _) -> NR > N ; true ).

我以为只需执行?- post(Tree, [...]), tree(Tree).就能让Prolog返回实际的二叉搜索树，但我似乎已经卡在了生成可能的树上。

我该如何改进我的代码？这可行吗？

- bp99

---

你的数据结构很不寻常。通常情况下，你要么有nil或者t(Value, Left, Right)，然后叶节点是t(Value, nil, nil)。 - TA_intern

所以你正在遍历一棵二叉搜索树，但列表没有排序，因为你正在使用后序遍历而不是中序遍历。是这样吗？你具体在做什么？ - TA_intern

这本教科书的这一章节为您提供了一些答案和代码：https://www.metalevel.at/prolog/dcg - TA_intern

Answer 1

我的建议是为不同的方向编写不同的代码。以下是将列表转换回树形结构的代码。与原始代码的主要区别在于，在重构树之前，我们对列表进行解构（使用last/3和append/3）。请注意，我在第三个子句中添加了用于搜索树的代码（两个maplist/2调用），但如果您想将其保留分开，则可以将其移除。

postlist_to_tree([],nil).
postlist_to_tree([X],t(X)).
postlist_to_tree(Xs,t(Last,LT,RT)):-
    last(Fore,Last,Xs),
    append(LL,RL,Fore),
    maplist('>='(Last),LL),
    maplist('=<'(Last),RL),
    postlist_to_tree(LL, LT),
    postlist_to_tree(RL, RT).

现在，如果要将其作为单个谓词，我建议这样做，使用非逻辑谓词（在此示例中为ground/1）来决定调用哪个版本，具体取决于调用时参数的实例化。

post2(Tree,List):-
    ground(List),
    !,
    postlist_to_tree(List,Tree).
post2(Tree,List):-
    post(Tree,List).

- jnmonette