2

二分木は、次の 2 つの述語で定義できます。

  • emptyBT、空の二分木。

  • BTTree(N,T1,T2)が左サブツリーと右サブツリーNを持つバイナリ ツリーのルートであり、 のすべての項目が より小さいか等しく、 のすべての項目が より大きい場合、これは真です。T1T2T1NT2N

次の述語を実装する Prolog プログラムを作成します。

  • insert(I,T1,T2)T2が二分木に挿入された結果の二分木である場合は真ですT1。

  • preorder(T,L)Lがバイナリ ツリーの事前順トラバーサルによって生成されたノードのリストである場合は true ですT。

  • inorder(T,L)Lがバイナリ ツリーの順序どおりのトラバーサルによって生成されたノードのリストである場合は true ですT。

  • postorder(T,L)Lがバイナリ ツリーのポストオーダー トラバーサルによって生成されたノードのリストである場合は true ですT。

  • search(T,I)Iがバイナリ ツリーに含まれている場合は true ですT。

  • height(T,H)Hがバイナリ ツリーの高さである場合は true ですT。空のツリーには height が0あり、アイテムが 1つあるツリーには height があり1ます。

これまでの私のコードは次のとおりです。その権利が正しいかどうかはわかりません。ヘルプやポインターをいただければ幸いです。

isempty(nil) :- !.
isempty(tree(nil,nil,nil)).

bTTree(tree(_,nil,nil)).
bTTree(tree(N,Left,nil)) :- Left@=<N.
bTTree(tree(N,nil,Right)) :- N@<Right.
bTTree(tree(_,Left,Right)) :- bTTree(Left), bTTree(Right).
bTTree(tree(N,Left,Right)) :- Left@=<N, N@<Right.

%traversals.
%preorder -- N,Left,Right

preorder(t,L) :- bTTree(t),
bTTree(t(N,Left,Right)),
append(N,[Left|Right],L).
preorder(t,L) :- bTTree(t(_,Left,_),
preorder(Left,L).
preorder(t,L) :- bTTree(t(_,_,Right),
preorder(Right,L).


%inorder -- Left,N,Right.

inorder(t,L) :- bTTree(t),
bTTree(t(N,Left,Right)),
append(Left,[N|Right],L).
inorder(t,L) :- bTTree(t(N,_,_)), inorder(N,L).
inorder(t,L) :- bTTree(t(_,_,Right)), inorder(Right,L).


%postorder -- Left,Right,N

postorder(t,L) :- bTTree(t),
bTTree(t(N,Left,Right)),
append(Left,[Right|N],L).
postorder(t,L) :- bTTree(t(_,_,Right)),
inorder(Right,L).
postorder(t,L) :- bTTree(t(N,_,_)),
append(_,[_|N],L).

search(t,I) :- bTTree(t(I,_,_)). %searches each node for I
search(t,I) :- bTTree(t(_,I,_)).
search(t,I) :- bTTree(t(_,_,I)).
search(t,I) :- bTTree(t(_,N,_)), search(N,I).%recursive method to search left branch for I
search(t,I) :- bTTree(t(_,_,N)), search(N,I).%recursive  " " " right branch for I

height(t,H) :- bTTree(t(nil,nil,nil)), H is 0.   %height of empty tree is 0
height(t,H) :- bTTree(t(_,nil,nil)), H is 1.     %height of single node Btree is 1
height(t,H) :-
   bTTree(t(_,Left,Right)),  %otherwise height of bTree is the max
   height(Left, H1),     %height of left or right branch plus 1
   height(Right, H2),
   H is max(H1,H2) + 1.

insert(I,t1,t2) :-
   bTTree(t1(X,L,_)),
   bTTree(t2(X,L,I)).
insert(I,t1,t2) :-
   bTTree(t1(nil,nil,nil)),
   bTTree(t2(I,nil,nil)).
insert(I,t1,t2) :-
   bTTree(t1(X,L,_)),
   bTTree(t2(X,L,I)).
4

2 に答える 2

1

明確にするために、あなたのコードは機能せず、有用なコーディング方法を示していないと思います。-次に、空のツリーであるコンパクトな表記法を使用して実装し、ツリーはt(LeftSubtree, Int, RightSubtree)です。必要に応じて、LeftSubtree のすべての int は Int より小さいなど...

ins(I, -, t(-, I, -)).
ins(I, t(L, X, R), t(P, Y, Q)) :-
    (   I < X
    ->  ins(I, L, U),
        (P, Y, Q) = (U, X, R)
    ;   I > X
    ->  ins(I, R, U),
        (P, Y, Q) = (L, X, U)
    ;   (P, Y, Q) = (L, X, R)  % already in, nothing to do
    ).

inl([N|Ns], T0, T) :-
    ins(N, T0, T1),
    inl(Ns, T1, T).
inl([], T, T).

inl/3 ツリーにすべての int を挿入し、結果を「返す」ユーティリティです。いくつかのテスト:

inl([3,6,1],-,X).
X = t(t(-, 1, -), 3, t(-, 6, -)) ;
false.

?- inl([3,6,1,1],-,X).
X = t(t(-, 1, -), 3, t(-, 6, -)) .

?- inl([3,6,1,1,4],-,X).
X = t(t(-, 1, -), 3, t(t(-, 4, -), 6, -)) ;
false.
于 2013-07-30T14:47:19.037 に答える