1

プロローグ述語を作成する必要があるため、from_list/2呼び出すfrom_list([], T)と、リスト(int)内のアイテムを含むツリーが返されます。これまでのところ:

from_list([], empty).
from_list([X], T) :-
    insert(X, empty, T).
from_list([X|Y], T) :-
    from_list(Y, NT),
    insert(X, NT, T).

編集：それを理解しましたが、リストの逆順でツリーに追加しています。何か助けはありますか？

これが私の挿入述語です。これはうまく機能しているようです。

insert( X, empty, bt(X, empty, empty) ). 
insert( X, bt(X2, L, R), bt(X2, NL, R) ) :-
    X < X2,
    !,
    insert(X, L, NL). 
insert( X, bt(X2, L, R), bt(X2, L, NR) ):-
    insert(X, R, NR).

そして、答えを必要としない2番目のはるかに小さな質問でもありません

プロローグが適切に使用されると非常にエレガントなスタイルになることは知っています...そしてこのコードは...それほどエレガントではありません...

is_search(empty).
is_search( bt(_, empty, empty) ).
is_search( bt( X, empty, bt(Y,LEFT,RIGHT) ) ) :-
    X < Y,
    is_search(LEFT),
    is_search(RIGHT).
is_search( bt(X, bt(Y,LEFT,RIGHT), empty) ) :-
    X > Y,
    is_search(LEFT),
    is_search(RIGHT).
is_search( bt( X, bt(Y,L1,R1), bt(Z, L2, R2) ) ) :-
    X > Y,
    X < Z,
    is_search( bt(Y, L1, R1) ),
    is_search( bt(Z, L2, R2) ).

それを少しきれいにする方法についてのヒントはありますか？

4

2 に答える 2

1

私の側からのヒント：

from_list([], empty).
from_list([X], T):- insert(X, empty, T).
from_list([X|Y], T):- from_list(Y, NT), insert(X, NT, T).

行 2 の空を見ている場合は不明であるため、これは機能しません。

リストを逆順で使用するには

reverse(X,R).

PS: 私が見る限り、私たちは SWI-Prolog について話していますよね?

于 2012-04-27T12:03:36.950 に答える
1

2 番目の質問については、バイナリ ツリーの 2 つのケース (5 つではありません!) を説明する必要があると思います。空であるか、左右のすべての要素がそれぞれ小さいか大きい内部ノードです。 、および二分木そのものです。

bt(empty).
bt(bt(Val, Left, Right)) :-
    all_smaller_than(Left, Val),
    all_larger_than(Right, Val),
    bt(Left),
    bt(Right).

all_smaller_than/2 と all_larger_than/2 は演習として残しておきます。ヒント: ここでも、それぞれに対して 2 つの句で十分です。あなたもそれをより速くする方法を見つけるかもしれません...

于 2012-05-04T12:15:26.270 に答える