пролог - bst дерево в список

Question

Я использую технику dcg, но у меня есть проблема. Я собираюсь внедрить преобразование дерева BST в список (каждый из возможных) и в обратном боковом списке ot bst (каждый из возможных). (Список означает, что здесь установлено значение real).
Однако,
эта грамматика должна быть в порядке, но она генерирует очень много дубликатов. Я знаю причину (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... 

Кроме того, прочитайте еще раз внимательно @ ответ мата для вашего предварительного вопроса, Prolog, reconstruct BST trees from inorder list, так как есть полезные методы, представленные там для более надежного решения для каждого из этих случаев. Я включил эту технику в приведенный выше код.

Обратите внимание, что вы все равно можете получать дубликаты, поскольку некоторые деревья могут давать одинаковые результаты при пересечении по-разному.

---

В свете комментариев выясняется, что решение определяется для определения связи между 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 устанавливает ограниченную основу для решения, чтобы избежать проблем терминации. Он «чувствует», как это решение может быть сжато, но я еще не нашел способ сделать это. Тем не менее, похоже, он обеспечивает решение выявленного вопроса, не давая дублирующих решений.

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

?-