序言中序遍历

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中需要一个事实！

因此，考虑所有这些措施可以写，采用DCG中：

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

您在递归案例中使用小写xinOrder;这应该是一个变量。但这可能不是唯一的问题。