Lab Exercises Week 03

cp /home/cs1927/public_html/16x1/labs/lab03/files/* .

BST.c	A BST implementation that has functions called countLeaves and searchInsert and countIf that need to be completed
BST.h	A BST interface that does not need to be modified

Task 1: Binary Search Tree Functions 2 marks

Each function is worth 1 mark

You have been provided with a binary search tree implementation in BST.c.

• Inside BST.c implement the functions

  int countLeaves(treelink tree);
  

  treelink searchInsert(treelink t, TreeItem i); 
  

  The searchInsert function should search for an existing item key in the BST and if it doesn't find such an existing key, inserts the item. This is to be done in one recursive traversal of the BST. It should return the root of the tree.

• Make a file called testBST.c to test your new functions. You will lose 1 mark if you do not do a decent attempt for this.

Task 2: Binary Search Tree Functions with function pointers 1 mark

Write a function countIf

int countIf (treelink tree, int (*pred)(TreeItem));

which traverses a binary tree and counts the number of items in the tree for which the application of *pred returns a non-zero value. For example, given the tree

	  5
         / \
        2   8
       / \
      1   4  

and a function

	
int isEven (TreeItem n);

which returns 1 if n is even, 0 otherwise. Calling

noOfEvenElems = countIf (tree, isEven);

assigns the value 3 to noOfEvenElems. Write an appropriate test cases to test your function and test your implementation for at least 2 different predicates ( isNegative, isOdd ). You will lose 0.5 marks if you do not do a decent attempt at this.

Submission

When you are happy with your work, please show it to your tutor to get it marked. Before you leave your lab, remember to submit your lab via the give command

1927 classrun 16x1 give lab03 BST.c testBST.c