0

我需要在 prolog 中执行一个程序，该程序打印出给定 N 级树的所有节点的列表（它必须是一个列表）。我只是无法将节点放入列表中。有人告诉我使用 findall 功能，但它仍然不起作用。我不想更改谓词 levelNodes 但没有 findall 的解决方案会很好。

domains
element=integer
treetype=tree(element,treetype,treetype);nil
list=element*
predicates
create_tree(element,treetype)
insert_left(treetype,treetype,treetype)
insert_right(treetype,treetype,treetype)
levelNode(treetype,element)
levelNodes(element,treetype,element)
goal
create_tree(10,Ten),
create_tree(11,Eleven),
create_tree(3,Three),
create_tree(5,Five),
create_tree(8,Eight),
create_tree(4,Four),
create_tree(1,One),

insert_left(Ten,Eleven,Eleven1),
insert_right(Three,Eleven1,Eleven2),
insert_left(Five,Eight,Eight1),
insert_right(Four,Eight1,Eight2),
insert_left(Eleven2,One,One1),
insert_right(Eight2,One1,FinalTree),
levelNode(FinalTree,1),
nl.
clauses
levelNode(tree(I,L,R),N):-
    findall(X,levelNodes(X,tree(I,L,R),N),O),
    write(O).
levelNodes(X,tree(I,_,_),0):-
    X=I,
    !.
levelNodes(X,tree(I,L,R),N):-
    N>0,
    N2=N-1,
    levelNodes(X,L,N2),
    levelNodes(X,R,N2). 
create_tree(A,tree(A,nil,nil)).

insert_left(X,tree(A,_,B),tree(A,X,B)).

insert_right(X,tree(A,B,_),tree(A,B,X)).
4

1 回答 1

0

如果我改写作业，我会得到：

  • 开始递归访问，向下传递正确初始化的Level，
  • 如果 Level 为 0 -> 停止递归（'返回'数据，我使用 head' 最后一个参数），
  • 递归前递减Level，并cons返回的数据。

这是一个草图，包含递归调用和 consing。

levelNode(tree(N,_,_), 0, [N]).
levelNode(tree(_,L,R), Level, Ns) :-
    Level > 0,
    Sub is Level - 1, % maybe you'll need Sub=Level-1
    % recurse left, ...

OT请注意，Prolog 中的递归数据结构非常容易描述，并且是问题建模中的重要组成部分。考虑而不是

create_tree(10,Ten),
create_tree(11,Eleven),
create_tree(3,Three),
create_tree(5,Five),
create_tree(8,Eight),
create_tree(4,Four),
create_tree(1,One),

insert_left(Ten,Eleven,Eleven1),
insert_right(Three,Eleven1,Eleven2),
insert_left(Five,Eight,Eight1),
insert_right(Four,Eight1,Eight2),
insert_left(Eleven2,One,One1),
insert_right(Eight2,One1,FinalTree),
levelNode(FinalTree, 1, Nodes),
...

在这样相当难以阅读的代码之后，我们有了FinalTree = tree(1, tree(11, tree(10, nil, nil), tree(3, nil, nil)), tree(8, tree(5, nil, nil), tree(4, nil, nil))).

切换到其他（等效）表示形式使其更具可读性，您不觉得吗？

...
Tree = t(1, t(11, t(10, t, t), t(3, t, t)), t(8, t(5, t, t), t(4, t, t))),
levelNode(Tree, 1, Nodes),
...

编辑代码是

levelNode(t(N,_,_), 0, [N]).
levelNode(t(_,L,R), Level, Ns) :-
    Level > 0,
    Sub is Level - 1, % maybe you'll need Sub=Level-1
    levelNode(L, Sub, A),
    levelNode(R, Sub, B),
    append(A, B, Ns).

测试：

?- T=t(1,t(2,t,t),t(3,t,t)),levelNode(T,1,L).
T = t(1, t(2, t, t), t(3, t, t)),
L = [2, 3] ;
false.
于 2012-11-07T21:20:35.130 回答