data-structures - 在序言中根据遍历查找二叉搜索树

Question

我正在尝试编写一个 Prolog 谓词，为给定的遍历提供一个可能的二叉搜索树。我选择用 t(Root, Left Subtree, Right Subtree) 来表示树，叶子只是 t(Number)，当子树不存在时，它的值是 无。

这是我目前所拥有的(在这种情况下仅用于后序遍历):

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 不需要二叉 search 树，即不需要左子树中的所有节点都小于根节点和所有右子树中的节点要大于根节点，所以我也这样写:

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 只返回实际的二叉 search 树.然而，我似乎已经陷入了生成可能树的困境。

我怎样才能改进我的代码？这甚至可行吗？

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