二叉樹在Prolog

Question

二進制樹可以在2個謂詞來定義：

• emptyBT，空二叉樹。

• BTTree(N,T1,T2)這是真的，如果N是左子樹T1和右子樹T2，其中T1所有項目都小於或等於N二進制樹的根，並在T2所有的項目都超過N更大。

編寫實現以下謂詞一個Prolog程序：

• insert(I,T1,T2)爲真，如果T2是我插入二叉樹T1產生的二叉樹。

• preorder(T,L)如果L是通過對二叉樹T進行預先遍歷而生成的節點列表，則爲true。

• inorder(T,L)如果L是二叉樹T的次序遍歷生成的節點列表，則爲true。

• postorder(T,L)爲真，如果L是二叉樹T的後序遍歷生成的節點的列表。如果包含在二叉樹T中，則爲真。如果H是二叉樹的高度T，則爲真。一棵空樹的高度爲0，而一棵樹的高度爲1。

---

這裏是我到目前爲止的代碼：我不知道，如果它的權利，任何幫助或指針將 不勝感激！

isempty(nil) :- !. 
isempty(tree(nil,nil,nil)). 

bTTree(tree(_,nil,nil)). 
bTTree(tree(N,Left,nil)) :- Left@=<N. 
bTTree(tree(N,nil,Right)) :- N@<Right. 
bTTree(tree(_,Left,Right)) :- bTTree(Left), bTTree(Right). 
bTTree(tree(N,Left,Right)) :- Left@=<N, N@<Right. 

%traversals. 
%preorder -- N,Left,Right 

preorder(t,L) :- bTTree(t), 
bTTree(t(N,Left,Right)), 
append(N,[Left|Right],L). 
preorder(t,L) :- bTTree(t(_,Left,_), 
preorder(Left,L). 
preorder(t,L) :- bTTree(t(_,_,Right), 
preorder(Right,L). 


%inorder -- Left,N,Right. 

inorder(t,L) :- bTTree(t), 
bTTree(t(N,Left,Right)), 
append(Left,[N|Right],L). 
inorder(t,L) :- bTTree(t(N,_,_)), inorder(N,L). 
inorder(t,L) :- bTTree(t(_,_,Right)), inorder(Right,L). 


%postorder -- Left,Right,N 

postorder(t,L) :- bTTree(t), 
bTTree(t(N,Left,Right)), 
append(Left,[Right|N],L). 
postorder(t,L) :- bTTree(t(_,_,Right)), 
inorder(Right,L). 
postorder(t,L) :- bTTree(t(N,_,_)), 
append(_,[_|N],L). 

search(t,I) :- bTTree(t(I,_,_)). %searches each node for I 
search(t,I) :- bTTree(t(_,I,_)). 
search(t,I) :- bTTree(t(_,_,I)). 
search(t,I) :- bTTree(t(_,N,_)), search(N,I).%recursive method to search left branch for I 
search(t,I) :- bTTree(t(_,_,N)), search(N,I).%recursive " " " right branch for I 

height(t,H) :- bTTree(t(nil,nil,nil)), H is 0. %height of empty tree is 0 
height(t,H) :- bTTree(t(_,nil,nil)), H is 1.  %height of single node Btree is 1 
height(t,H) :- 
    bTTree(t(_,Left,Right)), %otherwise height of bTree is the max 
    height(Left, H1),  %height of left or right branch plus 1 
    height(Right, H2), 
    H is max(H1,H2) + 1. 

insert(I,t1,t2) :- 
    bTTree(t1(X,L,_)), 
    bTTree(t2(X,L,I)). 
insert(I,t1,t2) :- 
    bTTree(t1(nil,nil,nil)), 
    bTTree(t2(I,nil,nil)). 
insert(I,t1,t2) :- 
    bTTree(t1(X,L,_)), 
    bTTree(t2(X,L,I)). 

Answer 1

爲了清楚起見，我認爲你的代碼不能工作，並且不顯示任何有用的編碼習慣。然後我使用一種簡潔的符號來實現，其中-是空樹，樹是t(LeftSubtree, Int, RightSubtree)。根據需要，在LeftSubtree所有整數小於詮釋，等等

ins(I, -, t(-, I, -)). 
ins(I, t(L, X, R), t(P, Y, Q)) :- 
    ( I < X 
    -> ins(I, L, U), 
     (P, Y, Q) = (U, X, R) 
    ; I > X 
    -> ins(I, R, U), 
     (P, Y, Q) = (L, X, U) 
    ; (P, Y, Q) = (L, X, R) % already in, nothing to do 
    ). 

inl([N|Ns], T0, T) :- 
    ins(N, T0, T1), 
    inl(Ns, T1, T). 
inl([], T, T). 

INL/3它是插入一個樹中的所有整數和「返回」結果的工具。 一些測試：

inl([3,6,1],-,X). 
X = t(t(-, 1, -), 3, t(-, 6, -)) ; 
false. 

?- inl([3,6,1,1],-,X). 
X = t(t(-, 1, -), 3, t(-, 6, -)) . 

?- inl([3,6,1,1,4],-,X). 
X = t(t(-, 1, -), 3, t(t(-, 4, -), 6, -)) ; 
false.