Обход двоичного дерева с помощью Пролога

Question

Я пытаюсь реализовать обход по порядку, который на каждом этапе я получу текущий узел.Например:

?- getnodesinorder(tree(1,nil,nil),X).
X = 1 ;
false.

?- getnodesinorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
X = 5 ;
X = 6 ;
false. 

Я попробовал следующий код:

getnodesinorder(tree(CurrentNode,nil,nil), CurrentNode).
getnodesinorder(tree(X, Left, nil), CurrentNode) :-
    getnodesinorder(Left, _ ),
    CurrentNode is X.
getnodesinorder(tree(X, nil, Right), CurrentNode) :-
    CurrentNode is X,
    getnodesinorder(Right, _ ).
getnodesinorder(tree(X, Left, Right), CurrentNode) :-
    getnodesinorder(Left, _ ),
    CurrentNode is X,
    getnodesinorder(Right, _ ).

Так что, конечно, база (первый пример работает), но при попытке запустить второй я получаю

X=5;
false

как результат.Почему это так?

Answer 1

Ошибка возникает из-за того, что вы обрабатываете левое и правое поддеревья, но ничего не делаете со значениями в них: getnodesinorder(Left, _ ) просто выбрасывает их. Итак, ваш предикат возвращает только верхний элемент.

Вот как вы выполняете обход в порядке:

inorder(tree(_,L,_), X) :- inorder(L,X).
inorder(tree(X,_,_), X).
inorder(tree(_,_,R), X) :- inorder(R,X).

Пример запроса:

?- inorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
X = 5 ;
X = 6 ;
false.

Answer 2

[test] λ = cat test.pl 
append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

getnodesinorder(nil, []).

getnodesinorder(tree(X, Left, Right), R) :-
   getnodesinorder(Left,R1),
   getnodesinorder(Right,R2),
   append(R1,[X|R2],R).

У меня работает

?-getnodesinorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X).
X = [1,2,3,4,5,6] ? 
yes