prolog

Question

我正在练习dcg技术，但是我有一个问题。我将实现将 BST 树转换为列表（每个可能）和相反的一面 - 列表 ot bst（每个可能）。（这里的列表是指真实设置）。
然而，
这个语法应该没问题，但它会产生很多重复项。我知道原因 (nil)，但我无法处理它。

 bstToList(nil) --> [].
    bstToList(t(Root, L, R)) --> [Root], bstToList(L), bstToList(R).
    bstToList(t(Root, L, R)) --> [Root], bstToList(R), bstToList(L).
    bstToList(t(Root, L, R)) -->  bstToList(R), [Root], bstToList(L).
    bstToList(t(Root, L, R)) -->  bstToList(L), [Root], bstToList(R).
    bstToList(t(Root, L, R)) --> bstToList(L), bstToList(R), [Root].
    bstToList(t(Root, L, R)) --> bstToList(R), bstToList(L), [Root].

你能帮帮我吗？

Answer 1

你如何实现它的问题在于你在每个遍历步骤中混合了每个遍历方法。换句话说，在每个遍历步骤中，您的谓词将探索每个遍历方法。

你需要在更高层次上分解它们：

bst_to_list(BST, Ls) -->
    bst_to_list_pre_LR(BST, Ls, _) |
    bst_to_list_pre_RL(BST, Ls, _) |
    bst_to_list_in_LR(BST, Ls, _) |
    bst_to_list_in_RL(BST, Ls, _) |
    bst_to_list_post_LR(BST, Ls, _) |
    bst_to_list_post_RL(BST, Ls, _).

然后分别实现每个类型：

% Pre-order, left-to-right
bst_to_list_pre_LR(nil, Es, Es) --> [].
bst_to_list_pre_LR(t(Root, L, R), [_|Es0], Es) -->
    [Root],
    bst_to_list_pre_LR(L, Es0, Es1),
    bst_to_list_pre_LR(R, Es1, Es).

% Pre-order right-to-left
bst_to_list_pre_RL(nil, Es, Es) --> [].
bst_to_list_pre_RL(t(Root, L, R), [_|Es0], Es) -->
    [Root],
    bst_to_list_pre_RL(R, Es0, Es1),
    bst_to_list_pre_RL(L, Es1, Es).

... % Etc...

此外，请再次仔细阅读@mat 对您先前问题的回答，，因为其中提供了有用的技术，可以为每种情况提供更强大的解决方案。我在上面的代码中采用了该技术。

请注意，您仍然可能会得到重复项，因为某些树在以不同方式遍历时会产生相同的结果。

根据评论，似乎寻求一种解决方案来定义 BST 和节点列表之间的关系，以便 BST 中的顺序可以是任意的。因为顺序可以是任何东西，所以它不适合 DCG。这是一个可能的非 DCG 解决方案：

bst_list_all(BST, L) :-
    tree_list_bound(BST, L, _),
    bst_list_all_(BST, L).

bst_list_all_(nil, []).
bst_list_all_(t(Root, L, R), Es) :-
    select(Root, Es, Es1),
    append(Ls, Rs, Es1),
    bst_list_all_(L, Ls),
    bst_list_all_(R, Rs).

tree_list_bound(nil, [], []).
tree_list_bound(t(_, L, R), [_|Es0], Es2) :-
    tree_list_bound(L, Es0, Es1),
    tree_list_bound(R, Es1, Es2).
tree_list_bound(t(_, L, R), [_|Es0], Es2) :-
    Es0 = [_|_],
    tree_list_bound(R, Es0, Es1),
    tree_list_bound(L, Es1, Es2).

谓词tree_list_bound为解决方案建立了一个有界框架以避免终止问题。它 "feels" 就像这个解决方案可以被压缩，但我还没有找到一种方法来做到这一点。但是，它似乎确实为所揭示的问题提供了解决方案，而不会产生重复的解决方案。

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

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

?-

prolog - 要列出的 bst 树

prolog - bst tree to list

dcg