๐Ÿค–
B.TECH II YEAR โ€ข II SEMESTER โ€ข R22

Skill Development Course - Lab Manual

PROLOG / LISP / PySWIP โ€ข Program 9 Solution

๐Ÿ“˜ R22 Regulation ๐ŸŽ“ II Year ๐Ÿ“š II Semester ๐Ÿค– Skill Development Course ๐Ÿงช Lab Program 9
Aim

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.

โ† All Programs

๐Ÿ’ป 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.
โ† Program 8 Program 10 โ†’
โ† Back to Skill Development Course Lab Programs ๐Ÿ“š All Lab Manuals