PREORDER Tree Traversal в Прологе

Question

У меня есть этот Пролог предикат для обходе дерева:

preOrder(nil, []). 
preOrder(node(X, nil, nil), [X]). 
preOrder(node(X, L, _), [X|T]) :- preOrder(L, T). 
preOrder(node(X, _, R), [X|T]) :- preOrder(R, T). 

Проблема заключается в том, что возвращает неполный список. Например, я получаю:

?- preOrder(node(1, node(2, node(3,nil,nil), node(4,nil,nil)), node(5,nil,nil)), L). 
L = [1,2,3] 

Когда это должно быть L=[1,2,3,4,5].

Почему это прекращается?

Answer 1

Посмотрите на ответы, которые производит Prolog. Это не один:

| ?- preOrder(node(1,node(2,node(3,nil,nil),node(4,nil,nil)),node(5,nil,nil)),L). 
L = [1,2,3] ? ; 
L = [1,2,3] ? ; 
L = [1,2,3] ? ; 
L = [1,2,4] ? ; 
L = [1,2,4] ? ; 
L = [1,2,4] ? ; 
L = [1,5] ? ; 
L = [1,5] ? ; 
L = [1,5] ? ; 
no 

Каждое из ваших правил описывает какую-то часть независимо от других. Но вам нужно описать их все вместе.

Лучший способ решить это to use DCGs

Answer 2

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

Таким образом, вы должны удалить второе предложение и присоединиться к двум рекурсивным предложениям только в одном предложении, которое добавляет результаты из обеих ветвей.

Например:

preOrder(nil, []). 
preOrder(node(X, L, R), [X|T]) :- 
    preOrder(L, LT), 
    append(LT, RT, T), 
    preOrder(R, RT). 

Вы можете также использовать аккумулятор для обхода:

preOrder(Tree, List):- 
    preOrder(Tree, [], RList), 
    reverse(RList, List). 

preOrder(nil, List, List). 
preOrder(node(X, L, R), List, NList) :- 
    preOrder(L, [X|List], MList), 
    preOrder(R, MList, NList). 

Обратите внимание, что, как сказал один из комментаторов, эти определения для предзаказа нет не работает право генерировать деревья дали ВТП.

Вы можете использовать DCGs определить процедуру, которая будет обратимым, внутренне используя открытые списки:

preOrder(nil)-->[]. 
preOrder(node(X, L, R))-->[X], preOrder(L), preOrder(R). 

И вы бы назвали его помощью phrase/2:

?- phrase(preOrder(node(1, node(2, node(3,nil,nil), node(4,nil,nil)), node(5,nil,nil))), L). 
L = [1, 2, 3, 4, 5].