2

A binary tree can be defined in terms of 2 predicates:

  • emptyBT, the empty binary tree.

  • BTTree(N,T1,T2) that is true if N is the root of a binary tree with left subtree T1 and right subtree T2, where all the items in T1 are less than or equal to N and all the items in T2 are greater than N.

Write a Prolog program that implements the following predicates:

  • insert(I,T1,T2) is true if T2 is the binary tree resulting from I being inserted into binary tree T1.

  • preorder(T,L) is true if L is a list of nodes generated by a preorder traversal of the binary tree T.

  • inorder(T,L) is true if L is a list of nodes generated by a inorder traversal of the binary tree T.

  • postorder(T,L) is true if L is a list of nodes generated by a postorder traversal of the binary tree T.

  • search(T,I) is true if I is contained in the binary tree T.

  • height(T,H) is true if H is the height of the binary tree T. An empty tree has height 0 and a tree with one item has height 1.

Here's my code so far: I have no idea if its right, any help or pointers would be greatly appreciated!

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

2 回答 2

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.
于 2013-07-30T14:47:19.037 回答
0

我想提供一个与@CapelliC 相同的答案，但有一个解释，可能还有一个友好的代码。

% it is true when X is greater than Y
gt(X,Y):- X > Y.

% create a node with only X
% createnode(+Tree, +Value, -t (-Value, -LeftLeaf, -RightLeaf))
createnode(nil, X ,t(X, nil ,nil)).

% base case
% avoid the duplicate
% otherwise, create a node
createnode(t(X, Left, Right), X, t(X, Left, Right)):-!. % the "!" cut down the backtracking, it's often more efficient

% create a node to a tree with the value X
% if X is smaller, create a node, with the value X, to Left1 subtree
% which backtracks to the base case
createnode(t(Root, Left, Right), X, t(Root, Left1, Right)):-
  gt(Root, X),!,
  createnode(Left, X, Left1).

createnode(t(Root, Left, Right), X, t(Root, Left, Right1)):-
  gt(X, Root),!,
  createnode(Right, X, Right1).

% base case
% the NewTree equals the Result tree
% and the list is empty, then the backtracking stops
insertnode([],Tree,Tree).

% insert a list of tree node
insertnode([X|Xs], Tree, Result):-
  createnode(Tree, X, NewTree),
  insertnode(Xs, NewTree, Result).

查询：

?-insertnode([7,6,12],nil,Tree).
Tree = t(7, t(6, nil, nil), t(12, nil, nil)).

?- createnode(nil,7,T1),createnode(T1,12,T2),createnode(T2,6,T3)
T1 = t(7, nil, nil),
T2 = t(7, nil, t(12, nil, nil)),
T3 = t(7, t(6, nil, nil), t(12, nil, nil)).
于 2021-06-02T17:00:18.777 回答