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（树，[…]），树（树）使Prolog只返回实际的二进制搜索树。然而，我似乎已经被困在生成可能的树上了。

如何改进代码？这可行吗？

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).