1

バランスの取れたツリーである場合に真になるisBalanced/1ような述語を実装する必要があります。isBalanced(T)T

この場合、二分木は、構造 node(left,right) によって定義されます。ここで、左と右は、別のノードまたは任意の Prolog データ項目のいずれかです。

私がこれまでに持っているもの:

height(node(L,R), Size) :-
    height(L, Left_Size),
    height(R, Right_Size),
    Size is Left_Size + Right_Size + 1 .
height(l(_),1).

isBalanced(l(_)).
isBalanced(node(B1,B2)):-
    height(B1,H1),
    height(B2,H2),
    abs(H1-H2) =< 1,
    isBalanced(B1),
    isBalanced(B2).

期待される出力:

?- isBalanced(1).
true.
?- isBalanced(node(1,2)).
true.
?- isBalanced(node(1,node(1,node(1,2)))).
false.

うまくいきません。アドバイスをいただければ幸いです。

4

1 に答える 1