Пролог в заказе обход

Question

пример узла выглядит следующим образом:

node(3, nil, 14). 
node(14, nil, 15). 
node(15, nil, 92). 

Я видел подобные вопросы, заданные здесь, однако, у меня это разные, как мои узлы имеют три, а не два значение параметра

пример того, как он должен работать:

?- inOrder(3, X). 
X = [3, 14, 15, 35, 65, 89, 92] . 

мой текущий код:

% the in-order traversal of a leaf is the leaf 
inOrder(X, [X]) :- 
    node(X, nil, nil). 

% if the node only has a left child, we traverse that 
inOrder(x, [X|T]) :- 
    node(X, L, [X|T]), 
    inOrder(L, T). 
% if the node only has a right child we traverse that 
inOrder(x, [X|T]) :- 
    node(X, nil, R), 
    inOrder(R, T). 
% if the node has both, we traverse them both. 
inOrder(x, [X|T]) :- 
    node(L, X, R), 
    L \= nil, R \= nil, 
    inOrder(L, T1), 
    inOrder(R, T2), 
    append(T1, T, T2). 

Он возвращает false вместо фактического значения, спасибо в продвинутом для любой помощи!

Answer 1

В вашем представлении есть несколько поворотов. В общем, древовидные структуры не сглажены в базе данных, здесь с node/3, но сохраняются в течение одного периода.

Кроме того, представляется хорошей идеей настаивать на том, что каждый узел имеет свой собственный факт. В вашем примере 92 нужен факт!

Поэтому, учитывая все эти меры предосторожности, можно написать, используя DCGs:

node(3, nil, 14). 
node(14, nil, 15). 
node(15, nil, 92). 
node(92, nil, nil). % added! 

inorder(I, Xs) :- 
    phrase(inorder(I), Xs). 

inorder(nil) --> 
    []. 
inorder(I) --> 
    {dif(I, nil)}, 
    {node(I, L, R)}, 
    inorder(L), 
    [I], 
    inorder(R). 

| ?- inorder(3,L). 
L = [3,14,15,92] ? ; 
no 

проверочной базы данных для осиротевших узлов:

orphan(Nr) :- 
    node(_, L, R), 
    (Nr = L ; Nr = R), 
    dif(Nr, nil), 
    \+ node(Nr, _, _). 

Так orphan(N) должен провалиться по вашей базе данных.

Answer 2

Вы используете нижний регистр x в своих рекурсивных случаях для inOrder; это должна быть переменная. Но это, вероятно, не единственная проблема.