Assume the prolog predicate gt(A, B) is true when A is greater than B. Use this predicate to define the predicate addLeaf(Tree, X, NewTree) which is true if NewTree is the Tree produced by adding the item X in a leaf node. Tree and NewTree are binary search trees. The empty tree is represented by the atom nil.
๐ป Solution
week10.pl/* Description:
A binary search tree is either empty or a node with a left subtree, an item and a right subtree.
-- The empty tree is represented by the atom nil.
-- A non-empty tree is represented by the term tree(Left, Item, Right).
-- gt(A, B) is true when A is greater than B.
addLeaf(Tree, X, NewTree) is true if NewTree is the Tree produced by adding the item X in a leaf node.
If X is already in the tree, the tree is not changed.
*/
/* Production rules:
addLeaf(nil, X, tree(nil, X, nil)). X becomes a leaf of an empty tree
addLeaf(tree(L, Item, R), X, tree(NewL, Item, R)) if Item > X add X to the left subtree
addLeaf(tree(L, Item, R), X, tree(L, Item, NewR)) if X > Item add X to the right subtree
addLeaf(tree(L, X, R), X, tree(L, X, R)). X is already present
*/
% Clauses:
gt(A, B) :- A @> B.
addLeaf(nil, X, tree(nil, X, nil)) :- !.
addLeaf(tree(L, Item, R), X, tree(NewL, Item, R)) :-
gt(Item, X), !,
addLeaf(L, X, NewL).
addLeaf(tree(L, Item, R), X, tree(L, Item, NewR)) :-
gt(X, Item), !,
addLeaf(R, X, NewR).
addLeaf(tree(L, X, R), X, tree(L, X, R)).
% Extra: builds a tree from a list of items by adding them one by one
list_to_tree(List, Tree) :-
list_to_tree(List, nil, Tree).
list_to_tree([], Tree, Tree).
list_to_tree([X|Xs], Tree0, Tree) :-
addLeaf(Tree0, X, Tree1),
list_to_tree(Xs, Tree1, Tree).
๐ค Output
w10.txt% Queries:
?- addLeaf(nil, 10, T).
T = tree(nil, 10, nil).
?- addLeaf(tree(nil,10,nil), 5, T).
T = tree(tree(nil, 5, nil), 10, nil).
?- addLeaf(tree(nil,10,nil), 15, T).
T = tree(nil, 10, tree(nil, 15, nil)).
?- addLeaf(tree(tree(nil,5,nil),10,tree(nil,15,nil)), 12, T).
T = tree(tree(nil, 5, nil), 10, tree(tree(nil, 12, nil), 15, nil)).
?- addLeaf(tree(nil,10,nil), 10, T).
T = tree(nil, 10, nil).
?- addLeaf(tree(nil,m,nil), c, T).
T = tree(tree(nil, c, nil), m, nil).
?- list_to_tree([50,30,70,20,40,60,80], T).
T = tree(tree(tree(nil, 20, nil), 30, tree(nil, 40, nil)), 50, tree(tree(nil, 60, nil), 70, tree(nil, 80, nil))).
?- list_to_tree([8,3,10,1,6,14], T).
T = tree(tree(tree(nil, 1, nil), 3, tree(nil, 6, nil)), 8, tree(nil, 10, tree(nil, 14, nil))).
?- gt(7, 3).
true.
?- gt(3, 7).
false.