0

我编写了一个将元素插入树中的函数，然后返回新树。它采用以下形式：

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

并且，理论上，应该返回：

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

简单来说，就是把这两个加到左子树上，再加上 nil 使其成为二叉树。然而，在我的实现中，这两个被添加到左右子树中。条件句总是被违反；如果 2 是 6，它仍然被添加到两个子树中，而不仅仅是右边。

我已经浏览了这个代码一个小时，但找不到错误。一双新鲜的眼睛能从这里掠过吗？

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 回答