CSI 2165, Winter 2006

Assignment 4

Due Mon, April 3, 11am

Submission instructions: The submission is done electronically through Virtual Campus.

Please submit a file called a4.pl with comments inside. The first comment should include your name and student number. The file should contain the Prolog code for the required predicates, and comments explaining what they do and how they do it. Add in comments example queries that you ran for testing each predicate and what the Prolog output was (thorough testing is important). Make sure your program can be loaded (consulted) in Prolog without giving errors. Make sure the name of the file and the names of the predicates are the required ones.

Note: No late assignments are allowed.

This assignment explores data structures, in particular binary trees and binary search trees.

Binary trees can be represented as structures with three arguments, lets say:

bt(Key, LeftSubTree, RightSubTree).

The leaves of the trees can be denoted by:

bt(key, nil, nil)

where nil is just a constant to represent an empty tree.

A binary search tree is a binary tree such that the value of the key in a node is larger than the keys in the left subtree and smaller than the keys in the right subtree. For example the following binary search tree:

4

/ \

2 5

/ \

1 3

is represented as:

bt(4, bt(2, bt(1, nil, nil), bt(3, nil, nil)), bt(5, nil, nil))

a. Implement a predicate that builds a binary search tree from a list of numbers. The first element in the list is the root of the tree, and all the elements of the list are inserted in the binary search tree in the right positions, according to their values. The first element of the list is inserted in an empty tree, the second element is inserted in the previous tree, than the third element, etc. (Hint: you can use the btInsert predicate from the lecture notes.)

?- list2tree([7, 5, 1, 3, 6, 9] , T).

T = bt(7, bt(5, bt(1, nil, bt(3, nil, nil)), bt(6, nil, nil)), bt(9, nil, nil));

No

The above binary tree looks like this:

7

/ \

5 9

/ \

1 6

\

3

b. Implement a predicate that counts the number of leaves in a tree (a leave is a node with no subtrees: the left and the right subtrees are both nil). For the previous tree the leaves are 3, 6, and 9. Example:

?- count_leaves(bt(7, bt(5, bt(1, nil, bt(3, nil, nil)), bt(6, nil, nil)), bt(9, nil, nil)), N).

N = 3;

No

c. Implement a predicate that counts the number of internal nodes of a tree. An internal node has one or two subtrees that are not empty (not nil). For the previous tree the leaves are 7, 5, and 1. Example:

?- count(bt(7, bt(5, bt(1, nil, bt(3, nil, nil)), bt(6, nil, nil)), bt(9, nil, nil)), N).

N = 3;

No

d. Implement a predicate that traverses a binary tree in prefix order (visits the node first, then the left subtree, then the right subtree). The result is the second argument, a list. Example:

?- tree2list_pre(bt(7, bt(5, bt(1, nil, bt(3, nil, nil)), bt(6, nil, nil)), bt(9, nil, nil)),L).

L = [7, 5, 1, 3, 6, 9];

No

e. Implement a predicate that traverses a binary tree in infix order (visits the left subtree, then the node, then the right subtree). The result is the second argument, a list. Example:

?- tree2list_in(bt(7, bt(5, bt(1, nil, bt(3, nil, nil)), bt(6, nil, nil)), bt(9, nil, nil)),L).

L = [1, 3, 5, 6, 7, 9];

No

f. Implement a predicate that traverses a binary tree in postfix order (visits the left subtree, then the right subtree, and the node at the end). The result is the second argument, a list. Example:

?- tree2list_post(bt(7, bt(5, bt(1, nil, bt(3, nil, nil)), bt(6, nil, nil)), bt(9, nil, nil)),L).

L = [3, 1, 6, 5, 9, 7];

No

Hint: for part a, you can use the following predicate that takes a new key (a number in our case) and a binary search tree, and produces a new binary search tree with the new key inserted in the right position.

btInsert(E, nil, bt(E, nil, nil)).

btInsert(E, bt(E, L, R), bt(E, L, R)).

btInsert(E, bt(E1, L, R), bt(E1, L1, R)) :-

btInsert(E, L, L1), E < E1.

btInsert(E, bt(E1, L, R), bt(E1, L, R1)) :-

btInsert(E, R, R1), E > E1.

Examples of use:

?- btInsert(4,nil,T).

T = bt(4, nil, nil)

?- btInsert(2, bt(4, nil, nil), T).

T = bt(4, bt(2, nil, nil), nil)

?- btInsert(5, bt(4, bt(2, nil, nil), nil), T).

T = bt(4, bt(2, nil, nil), bt(5, nil, nil))

Have fun!!!