2

我试图通过将中序列表转回 BST 来“反转”中序遍历。

BSTs 有谓词形式node(Value,Left,Right)or leaf，所以空树就是leaf，只有一个节点的树就是node(_,leaf,leaf)。

给定谓词enumerate_bst(Elems,Bst)，目标是匹配Bst中序列表的所有可能性Elems。例如（注意setof/3）：

?- setof(Bst,enumerate_bst([],Bst),Enum).
Enum = [leaf].

?- setof(Bst,enumerate_bst([1,2],Bst),Enum).
Enum = [
    node(1, leaf, node(2, leaf, leaf)),
    node(2, node(1, leaf, leaf), leaf)
].

?- setof(Bst,enumerate_bst([1,2,3],Bst),Enum).
Enum = [
    node(1, leaf, node(2, leaf, node(3, leaf, leaf))),
    node(1, leaf, node(3, node(2, leaf, leaf), leaf)),
    node(2, node(1, leaf, leaf), node(3, leaf, leaf)),
    node(3, node(1, leaf, node(2, leaf, leaf)), leaf),
    node(3, node(2, node(1, leaf, leaf), leaf), leaf)
].

我试图做的事情：

我已经有一个谓词将给定的 BST 与它的中序列表相匹配：

inorder(leaf,[]).
inorder(node(X,L,R),Elems) :-
  inorder(L,Elems_L),
  inorder(R,Elems_R),
  append(Elems_L,[X],Tmp),
  append(Tmp,Elems_R,Elems).

我试图通过放入一个列表来反向使用它，但这只返回一个结果，我不确定为什么。

我目前正在尝试做的事情

我正在尝试反向使用本机谓词append/3，但无法完全决定如何完成。

关于做到这一点的最佳方法的任何想法？谢谢！

4

2 回答 2

5

相反，您的程序不会终止。考虑：

?- inorder(Tree, []).
   Tree = leaf
;  **LOOPS**

我们希望它只显示这个唯一的解决方案然后停止。实际原因是程序的以下片段 - 。没有必要再看远了。换句话说，根本不需要了解append/3。

?- 中序（树，[]），假。

有序（叶，[]）：-假。
有序（节点（X，L，R），Elems）：-
   中序（L，Elems_L），假。
   中序（R，Elems_R），
   追加（Elems_L，[X]，Tmp），
   追加（Tmp，Elems_R，Elems）。

首先，这个片段需要终止（并且失败）。只有这样你才能考虑终止整个程序。在这个片段中，第二个参数 ( Elems) 被完全忽略了！对它感兴趣的第一个目标是最后一个目标 ( append(Tmp,Elems_R,Elems))。

一个天真的出路是重新排列目标，将两个append/3目标放在首位。这行得通（也就是说，它终止于第二个参数），但它非常不令人满意，因为该程序现在致力于将列表的元素仅分布到树中。

这是一个可以双向工作的版本，如终止条件所示：

inorder(A,B)terminates_if b(A);b(B).

它指出inorder/2如果第一个或第二个参数为接地，则终止。

inorder(Tree, Xs) :-
   phrase(inorder(Tree, Xs,[]), Xs).

inorder(leaf, Vs,Vs) -->
   [].
inorder(node(X,L,R), [_|Vs0],Vs) -->
   inorder(L, Vs0,Vs1),
   [X],
   inorder(R, Vs1,Vs).
于 2017-05-04T09:35:16.200 回答
1

前段时间我为这个任务写了一个“库”。使用它：

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

inorder(leaf,[]).
inorder(node(X,L,R),Elems) -:-
  inorder(L,Elems_L),
  inorder(R,Elems_R),
  append(Elems_L,[X],Tmp),
  append(Tmp,Elems_R,Elems).

然后

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

对代码的唯一更改（除了包含“库”）是替换:-with -:-。我选择了这个符号来暗示双向性......

于 2017-05-04T11:36:23.897 回答