項目被插入兩次（進入兩個子樹）。原因未知

Question

我寫了一個函數，它將一個元素插入樹中，然後返回新的樹。它的格式爲：

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

，理論上，應該返回：

T = tree(tree(nil, 2, nil) 5, 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). 

Answer 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 
    ).