CS 302 Assignment 3: Implementing a Binary Search Tree

Due date: Friday, February 16, 2018, midnight.

All programming assignments must be submitted electronically. Submit them to the graduate assistant by email on or before the due date

Your email must come from your engineering college (or computer science or computer engineering) account.
Your program must compile on the College of Engineering machines.
  1. Implement a binary seach tree data type.
    1. Write C++ code for a class whose objects are binary search trees where the data items have type integer. The class must contain a methods "insert," "find" (which returns a Boolean), "delete," as well as method "inorder" and "preorder" which must write the data in the binary search tree to an output stream in inorder or preorder, as the case may be. You also need the method "initialize" which initializes a binary search tree to be empty.
      The names of these methods do not have to be "insert," "inorder," etc.; you can use any appropriate names.
    2. Write the C++ code for the methods mentioned above. Use lazy deletion.
    3. Your program should read the data from a file.
    4. Some sample files.
    5. When the command is either inorder or preorder list, and the tree is empty, your output must state that the tree is empty.
      Warning: if the tree still has nodes but they are all marked deleted, then the tree is empty.
    6. If the command is to delete an item which is not in the tree, nothing happens, and there is no required output.
    7. If the command is to insert an item which is already in the tree, nothing happens, and there is no required output.
    8. You must not take the implementation of the ADT binary search tree from the standard template library, or any similar library. The reason for this rule is that you need experience designing your own data structure, and you don't get that by simply grabbing one from the library.
      Perhaps you think that you don't need that experience, since the standard template library is available. But, you're wrong. Libraries only contain things which are commonly used. They do not contain the more complex data structures you will need to design for specific applications in the future.
  2. Write code for binary tree sort, sorting a list of real numbers.
    Binary tree sort can work badly, taking up to quadratic time.
    Count the number of comparisons, to see how close you get to the Ω(n log n) lower bound (or the O(n2) upper bound) for each example.
    Use the following five files to test your program.
    1. a small file.
    2. a large file.
    3. a file that is "almost" sorted.
    4. another file that is almost sorted.
    5. A bad example? You tell me.
  3. Here is an updated version of my code which contains some additional diagnostics.