Recursion is an algorithmic approach which can simplify coding and solving complex problems.This programming assignment provides the use of recursion. Moreover, binary search tree and its varieties are used in quick accessing data.

Main idea:

Insert users into a binary search tree using their birth dates as comparison. You need to print the tree in several traversal methods, find the student with the highest GPA, and print the descendants of this user in the tree.

2.0 Requirements

2.1 (Class TreeType) Implement Binary Search Tree whose specification is provided in Section 8.5 and implementation is provided in Section 8.6. Create TreeType.h and TreeType.cpp files.

- (Struct TreeNode) Declare TreeNode similar to struct TreeNode in Section 8.5.

-TreeNode will have the following private members:

- User* user,

- TreeNode* left, and

- TreeNode* right

- Add the following enumerated type:

- enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

- Binary Search tree will have the following private member:

- TreeNode* root;

- Binary Search tree will have the following additional methods:

- void PutUser(User* user): This will insert user to the tree.

- User* GetHighestGPA(float& gpa);//needs to call another recursive function

- void Print(OrderType otype,std::ofstream& outfile); //needs to call another recursive function PrintTree

- void PrintTree(TreeNode* tree, std::ofstream& outfile)

- void PrintDescendants(User* user, OrderType otype, std::ofstream& outfile);//find the user in the tree and then find the descendants of the user

- Add a default constructor and destructor for the tree type.

- All users will be inserted to the binary search tree. Make similar changes as you have done in Assignment 2. Replace ItemType Item with User* user. Instead of PutItem have PutUser function. Apply similar changes for functions have ItemType, Item as part of their names and arguments.

- Tree will be built based on birthdates (i.e., search order).

2.3 (Enhance Class User by overloading operators <, > and ==)

- (Add 3 more observers) User class will have two observers per list.

- bool operator<(User* anotherUser): This will compare the birth date of the user with the birthdate of anotherUser.

- bool operator>(User* anotherUser): This will compare the birth date of the user with the birthdate of anotherUser.

- bool operator==(User* anotherUser): This will compare the birth date of the user with the birthdate of anotherUser.

2.4 (Main function) Declare treeUsers of TreeType; and treeUsers will hold users.

2.5 (Testing) Enhance TestDriver class. Create the specification file (TestDriver.h) and implementation file (TestDriver.cpp). This file should have

- int Populate(const char* input,TreeType& treeUsers) const method to read user profiles from input file input into the tree of treeUsers.

- Add one more function void Test(std::ofstream& outFile,TreeType& treeUsers) const for testing experiments. In order to test the class functions this test method should evaluate all methods in the class.

Sample Main Function:

int main()

{

TreeType treeUsers;

TestDriver tester;

User* user;

// -- Print the tree

tester.Populate("C:\\tmp\\cs221\\hw1\\hw1samplefile.txt",treeUsers);

treeUsers.Print(PREORDER,"C:\\tmp\\cs221\\hw1\\vaughnhw3samplefilePREORDER.txt");

treeUsers.Print(INORDER,"C:\\tmp\\cs221\\hw1\\vaughnhw3samplefileINORDER.txt");

treeUsers.Print(POSTORDER,"C:\\tmp\\cs221\\hw1\\vaughnhw3samplefilePOSTORDER.txt");

// -- Find the user with the highest GPA

user=treeUsers->GetHighestGPA();

user->Display();

// -- Print the descendants of the user with the highest GPA

treeUsers.PrintDescendants(user,PREORDER,"C:\\tmp\\cs221\\hw3\\vaughnhw3samplefileDescendantsPREORDER.txt");

treeUsers.PrintDescendants(user,INORDER,"C:\\tmp\\cs221\\hw3\\vaughnhw3samplefileDescendantsINORDER.txt");

treeUsers.PrintDescendants(user,POSTORDER,"C:\\tmp\\cs221\\hw3\\vaughnhw3samplefileDescendantsPOSTORDER.txt");

// -- Test Function

tester.Test("C:\\tmp\\cs221\\hw3\\vaughnhw3testing.txt",treeUsers);

return 0;

}