CS 311 Fall 2009
Assignment 7

Assignment 7 is due at 5 p.m. Tuesday, November 24. It is worth 25 points.

Procedures

This is a group assignment. Please work in a group of 2 or 3. Each group only needs to turn in a single copy of the assignment. Under normal circumstances, each will receive the same grade on the assignment.

E-mail answers to the exercises below to ffggc@uaf.edu, using the subject “DA7”.

• Your answers should consist of one file: bstree.h, from Exercise A. This file (or an archive file containing it) should be attached to your e-mail message.
• Be sure to include the names of all group members in your e-mail.
• Suggestion: Cc the submission e-mail to all group members, so that I can reply to all indicating that it has been received.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Exercises (25 pts total)

Exercise A — Binary Search Tree Class Template

Purpose

In this exercise, you will write a simple Binary Search Tree. It will be able to retrieve and insert by key, do the three standard traversals, and copy itself.

Instructions

Implement a C++ class template that manages a Binary Search Tree holding keys without associated data. The type of key should be specified by the client code. Be sure to follow the coding standards. All standards apply.

• Call your class template “BSTree”, so that, for example, a BSTree with key type int would be declared as a BSTree<int>.
• Implement your class template in file bstree.h. Since this is a template, there should be no associated source file.
• Implementation.
  • The data must be stored in an actual Binary Tree.
  • The keys should be ordered using operator<.
  • Multiple equivalent keys are not allowed.
  You may decide other implementation issues however you want, within the constraints of the coding standards, and the rest of these requirements.
• Interface. Class BSTree must include the following public member functions, and no others:
  • Default ctor. Creates an empty BSTree.
  • Copy ctor. Copies a tree, as usual. The copy must contain completely separate data.
  • Copy assignment operator. Copies a tree, as usual. The copy must contain completely separate data.
  • Dctor. Does all necessary deallocation, destruction, and other necessary clean-up.
  • Function size. No parameters, returns std::size_t. Returns the number of keys stored in the tree.
  • Function empty. No parameters, returns bool. Returns true if the size of the tree is zero. Must be constant-time.
  • Function clear. No parameters, returns nothing. Removes all keys from the tree, resulting in an empty tree.
  • Function retrieve. Given a key, returns a bool. Returns true if a key equivalent to the given key is in the tree.
  • Function insert. Given a key, returns a bool. If a key equivalent to the given key is in the tree already, then returns true, leaving the tree unchanged. Otherwise, inserts the given key into the tree, and returns false.
  • Functions preorderTraverse, inorderTraverse, postorderTraverse. Given an output iterator, return nothing. Does “*iter++ = key;” for each key in the tree, with iter being the given iterator. The functions traverse the keys in the order given by the preorder, inorder, and postorder traversals of the tree, respectively.
• Other Requirements.
  • You may not use any C++ Standard Library classes in your implementation. (You may use simple types, like std::size_t, and functions, like std::swap.)
  • All of the functions specified above should have the highest reasonable levels of efficiency and exception safety.
  • All of the functions specified above must be exception-neutral; that is, exceptions thrown by value-type operations must propagate unchanged to the caller.
  • You may not forbid any member function of the value type from throwing, except for the destructor.

Test Program

I have written a test program: bstree_test.cpp. If you compile and run your package with this program (unmodified!), then it will test whether your code works properly.

Do not turn in bstree_test.cpp.

Notes

• You probably want to write a separate node class.
• You do not need to implement the Binary Search Tree delete operation.
• I will be discussing ideas for writing this assignment in class on Friday, November 20.
• As always, you are strongly encouraged to turn in your work on time, and late work will not be awarded full credit. However, in the interest of students enjoying their Thanksgiving vacations, Thursday 11/26 through Sunday 11/29 will not be counted toward the time allowed for late work. Thus, work turned in on Monday, November 30 will be counted as two days late, not six, and the assignment will be accepted until Thursday, December 3 (as five days late). Again, I recommend that you do not take advantage of this, but if you must ...
• Yes, I am aware that the preorder and postorder traversals do not make much sense for a Binary Search Tree. Deal with it. :-|

CS 311 Fall 2009: Assignment 7 / Updated: 23 Nov 2009 / Glenn G. Chappell / ffggc@uaf.edu