0

要素をツリーに挿入し、新しいツリーを返す関数を作成しました。次の形式を取ります。

% insert(Element, OldTree, NewTree)
?-insert(2, tree(nil, 5, nil), T).

そして、理論的には、次を返す必要があります。

T = tree(tree(nil, 2, nil) 5, nil)

簡単に言えば、左側のサブツリーに 2 つが追加され、バイナリにするために nil が追加されます。ただし、私の実装では、2つは左と右の両方のサブツリーに追加されます。条件には常に違反があります。2 が 6 だった場合でも、右側だけでなく両方のサブツリーに追加されます。

このコードを 1 時間調べましたが、バグが見つかりません。新鮮な目がこれをすくい取ることができますか?

tree(Left, Root, Right).

insert(Item, Oldtree, Newtree).

%tree is empty
insert(Element, Empty, tree(Empty, Element, Empty)):-!.

%tree isn't empty. if NewItem is less than Root, we put it on the left subtree
insert(NewItem, tree(LeftSubtree, Root, RightSubtree), tree(NewLeftSubtree, Root, RightSubtree)):-
        NewItem < Root,
    !,
        insert(NewItem, LeftSubtree, NewLeftSubtree).

%else
insert(NewItem, tree(LeftSubtree, Root, RightSubtree), tree(LeftSubtree, Root, NewRightSubtree)):-
    NewItem > Root,
    !,
        insert(NewItem, RightSubtree, NewRightSubtree).
4

1 に答える 1

1

まず、これをしないでください：

tree(Left, Root, Right).

これはtree、(かなり役に立たない) 述語として定義されます。Prolog でデータ型を宣言する必要はありません。

次、

insert(Item, Oldtree, Newtree).

insert/3常に成功する述語として定義します。この句は必要ありません。

insert(Element, Empty, tree(Empty, Element, Empty)):-!.

あなたが思っていることをしません。Emptyは変数なので、何にでもマッチします。

最後に、すべての複雑なカット ロジックの代わりに、if-then-else を使用します。

insert(X, tree(L0,Y,R0), tree(L,Y,R)) :-
    (X < Y ->
        % insert into left subtree
    ; X > Y ->
        % insert into right subtree
    ;
        % equals case
    ).
于 2012-03-27T10:58:02.490 に答える