Prolog中的二叉樹

Question

我需要編寫一個prolog程序，從鍵盤讀取這樣的正數，直到用戶寫入「stop」並生成沒有重複的二進制字典。

我嘗試：

:-dynamic tree/1. 

run:- 
    retractall(tree(_)), 
    write('Input N '), read(N), 
    insert(N,empty,T), 
    assert(tree(T)), 
    start(N),nl, 
    tree(T),write(T),!. 

start(stop):-!. 
start(N):- 
     N \= stop, 
     tree(T), 
     insert(N,T,NewTree), 
     assert(tree(NewTree)), 
     write('Input N '), read(M), 
     start(M). 

insert(NewItem,empty,tree(NewItem,empty,empty)):- !. 
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):- 
                    NewItem @< Element, 
                    !,insert(NewItem,Left,NewLeft). 

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):- 
                    insert(NewItem,Right,NewRight). 

誰能幫助我？

Answer 1

這裏有兩個錯誤。首先，第一個元素被插入兩次，因爲顯式調用要插入到運行體中，並且要啓動的調用也會調用insert。而不是這樣做，你需要從記錄空樹開始。其次，僅查詢當前正在記錄的樹是不夠的，您需要刪除樹的先前版本並記錄當前樹。

修復這兩個錯誤導致了以下解決方案：

:-dynamic tree/1. 

run:- 
    retractall(tree(_)), 
    write('Input N '), read(N), 
    assert(tree(empty)), % 1. initially the tree is empty 
    start(N),nl, 
    tree(T),write(T),!. 

start(stop):-!. 
start(N):- 
     N \= stop, 
     retract(tree(T)), % 2. changed here 
     insert(N,T,NewTree), 
     assert(tree(NewTree)), 
     write('Input N '), read(M), 
     start(M). 

insert(NewItem,empty,tree(NewItem,empty,empty)):- !. 
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):- 
     NewItem @< Element, 
     !,insert(NewItem,Left,NewLeft). 

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):- 
     insert(NewItem,Right,NewRight). 

在一個稍微不同的說明，你可能會問自己是否真的需要做到這一切的認定/收回你可以通過目前構建的樹作爲開始謂詞的論據。

消除斷言和收回給出以下版本：

run:- 
    write('Input N '), read(N), 
    start(N, empty, T),nl, 
    write(T). 

start(stop, T, T):-!. 
start(N, CurTree, FinalTree):- 
     N \= stop, 
     insert(N,CurTree,NewTree), 
     write('Input N '), read(M), 
     start(M, NewTree, FinalTree). 

insert(NewItem,empty,tree(NewItem,empty,empty)):- !. 
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):- 
     NewItem @< Element, 
     !,insert(NewItem,Left,NewLeft). 

insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):- 
     insert(NewItem,Right,NewRight). 

最後，觀察開始的第一條和用途停止與第一和第二參數在切割的限制而第三一個是免費的，使明確的檢查N \ =停止多餘。這給了我們解決方案的最終版本：

run:- 
    write('Input N '), read(N), 
    start(N, empty, T),nl, 
    write(T). 

start(stop, T, T):-!. 
start(N, CurTree, FinalTree):- 
     insert(N,CurTree,NewTree), 
     write('Input N '), read(M), 
     start(M, NewTree, FinalTree). 

insert(NewItem,empty,tree(NewItem,empty,empty)):- !. 
insert(NewItem,tree(Element,Left,Right),tree(Element,NewLeft,Right)):- 
     NewItem @< Element, 
     !,insert(NewItem,Left,NewLeft). 
insert(NewItem,tree(Element,Left,Right),tree(Element,Left,NewRight)):- 
     insert(NewItem,Right,NewRight).