0

与えられたレベル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 が 0 の場合 -> 再帰を停止します (データを「返す」、最後の引数に head を使用します)、
  • 再帰の前にレベルをデクリメントし、返されたデータをコンスします。

これは、再帰呼び出しとコンシングを備えたスケッチです。

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 に答える