Binary Tree В Прологе

Question

Бинарное дерево может быть определено в терминах 2 предикатами:

• emptyBT, пустое бинарное дерево.

• BTTree(N,T1,T2), что является истинным, если N является корнем бинарного дерева с левого поддерева T1 и правого поддерева T2, где все элементы T1 меньше или равна N и все элементы T2 больше, чем N ,

Напишите программу на Прологе, которая реализует следующие предикаты:

• insert(I,T1,T2) верно, если T2 является бинарное дерево, в результате я вставляется в бинарное дерево T1.

• preorder(T,L) верно, если L список узлов, порожденных обходе двоичного дерева T.

• inorder(T,L) имеет значение true, если L - это список узлов, сгенерированных обходным путем по двоичному дереву T.

• postorder(T,L) имеет значение true, если L - это список узлов, сгенерированных последующим обходом двоичного дерева T.

• search(T,I) имеет значение true, если I содержится в двоичном дереве T.

• height(T,H) имеет значение true, если 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 меньше, чем Int, и т.д ...

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.