Assignment 4: Binary Search Tree (100 pts)
Due Wednesday, March 2 at midnight on Catalyst

Part 1: Building Your BST
  • Using the header file provided in class, create a templated BST data structure.
  • Your BST class must contain the following public constructors and destructors:
    • Default constructor
    • Copy constructor
    • Destructor
  • Your BST class must also contain the following access functions:
    • bstdata minimum(); //finds the minimum value in the BST and returns it
    • bstdata maximum(); //finds the maximum value in the BST and returns it
    • bool isEmpty(); //returns whether the tree is empty
    • int getSize(); //returns the size of the tree
    • Note: You for this function, you must remove any updates to the size variable in add() and remove() and instead, write a recursive version of this function that simply counts the number of elements in the tree and returns this number as the size.
    • bstdata getRoot(); //returns the value stored at the root of the tree
    • int getHeight(); //recursively finds the height of the tree and returns it
    • bool search(bstdata value); //returns whether the value is in the tree
  • Your BST class must contain the following manipulation procedures:
    • void insert(bstdata value); //adds the specified value to the tree
    • void remove(bstdata value); //removes the specified value from the tree
  • Your BST class must contain the following additional functions:
    • void inOrderPrint(); // recursively prints the values contained in the BST according to an in order traversal
    • void preOrderPrint(); //recursively prints the values contained in the BST according to a pre order traversal
    • void postOrderPrint();//recursively prints the values contained in the BST according to a post order traversal
  • In addition, your BST must contain a number of private helper functions wherever necessary for the recursive implementation of the above public functions.
  • All of these functions and their definitions must be located inside of a file named BST.h
  • Finally, you must have a file named BSTTest.cpp in which you thoroughly test each of these functions, including their edge cases.
Part 2: Files and Your BST
  • Create a file named BST.cpp in which you have a main function which opens a file, reads the contents of the file into a BST and then performs operations on the tree, the result of which you then write to an output file.
  • The name of the input file MUST BE input.txt and it will be structured as follows:
    • The first line of the file will contain the integer values to insert into your BST.
    • The second line of the file will contain a value to search for in the BST.
    • If this value exists in the tree, you must remove it.
    • The third line of the file will contain an integer value to add to the tree.
    • The fourth line will contain the values to insert into a BST
    • The above will repeat for the next BSTs
  • In other words, the file will be structured in groups of three:
    • line one: data to fill a BST
    • line two: one value to search for and remove
    • line three: one additional value to add
  • The file will be of indeterminate length
  • For example, 3 lines of the file might look like the following:
599 7 91 8888 26 10 4 100 45 769 22
4
67
  • Your job is to fill the BST with the given data on the first line of the group of three
  • You must then write the contents of this BST to a file TWICE, once by calling preOrderPrint and once by calling inOrderPrint.
  • Then, you should move to the next line of the file and print a message about whether the value to search for was contained in the file. Your message should be either:
    • <value> was found in the BST
    • <value> was not found in the BST
  • You should then remove the value from the BST if it exists.
  • Next, you should add the new value to the BST.
  • Next, you should print the updated tree to the file by calling postOrderPrint.
  • Finally, you should print out the size and height of the tree.
  • You should repeat this process in a loop for each group of three in the file.
  • The name of your output file MUST BE output.txt


Example File

  • Here is a short file to get you started.
  • Note that you will want to add onto this file to ensure your BST.cpp is working properly

Example input.txt file:

12 6 9 45 3 7 10 2 4 13
4
9
55 18 3 6 78 9
13
66
808 707 909 1001 505 1200 499 644 1190 1592
707
78

Matching output.txt file


12 6 3 2 4 9 7 10 45 13
2 3 4 6 7 9 10 12 13 45
4 was found in the BST
2 3 7 10 9 6 13 45 12
The size of the BST is 9
The height of the BST is 3

55 18 3 6 9 78
3 6 9 18 55 78
13 was not found in the BST
9 6 3 18 66 78 55
The size of the BST is 7
The height of the BST is 4

808 707 505 499 644 909 1001 1200 1190 1592
499 505 644 707 808 909 1001 1190 1200 1592
707 was found in the BST
78 499 644 505 1190 1592 1200 1001 909 808
The size of the BST is 10
The height of the BST is 4

A Word About Printing

  • Note that you will need to alter the signatures of preOrderPrint, inOrderPrint and postOrderPrint to take in information about a file.
  • You must print the information about each tree to the output.txt file in groups, separated by a blank line, identical to the sample output file shown above.

What To Submit

  • Upload BST.h, BSTTest.cpp (test file to ensure binary search tree working properly), BST.cpp (file with I/O logic) to Catalyst.


Grading

  • I will be testing your BST class functions with my own tests.
  • You will receive 100 points if all tests pass, 75 points if 3/4 of the tests pass, etc.
  • The tests are considered to pass if your output.txt contains the same contents as my output.txt after I run my input file with your code.
  • One test is one BST, which prints a correct inOrder, preOrder and postOrder print, correctly alerts me that the searched for value is or is not located in the BST, and prints the required information about the size and height of the tree.
  • -15 points for not naming your input and output files input.txt and output.txt, respectively!