CS 302 Assignment 5: Implementing a Binary Search Tree

Due date: Tuesday, April 2, 2013, midnight.

All programming assignments must be submitted electronically. Submit them to the graduate assistant by email on or before the due date at
androvas"at"unlv"dot"nevada"dot"edu
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. 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 the method "inorder" must write the data in the binary search tree to an output stream. 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. 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.