Предварительный обход дерева в Прологе

Посмотрите на ответы, которые дает Пролог. Это не один:

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

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

Лучший способ решить эту проблему — использовать DCG.

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

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

E.g.:

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

Обратите внимание, что, как сказал один комментатор, эти определения для preOrder не работают правильно для создания деревьев с учетом обхода.

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

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