Programming Assignment 8

A) A sequential search member function of SortedType (a sorted list covered in Chapters 4 and 5) has the following prototype:

void SortedType::Search(int value, bool & found);

The first parameter is the value to be searched for, and the second parameter is true if the value is found and false otherwise.

a) Write the function definition as a recursive search assuming a linked list representation. This should follow the format of the reverse list function that we wrote in class. The public member function is not recursive, but an auxilary function is recursive. This allows the first call to the recursive function to have access to the pointer to the beginnning of the list.

b) Declare a list and enqueue 10 items. Test the function by searching a linked list for three items that are on the lists (the first item, last item and one of the middle items.) Test the function for searching for three items that are not on the list (smaller than the first, larger than the last, and between the first and last).

B) Add a Boolean member function IsBST to the class TreeType that determines whether a binary tree is a binary search tree.

a) Write the function prototype.

b) Write the recursive implementation of this function.

c) Test the function.