Instructions

In this homework you will write a library for binary search trees in C++. This will involve templates, iterators and const correctness. It is highly recommended that you review these topics before implementing the library.

Handout: hw7.tar.gz Update: made treeNode private in bintree.h!

• Header file for binary search tree: bintree.h
• Implementation file for binary search tree: bintree.hpp
• Simple test program for the binary search tree: test.cpp
• Makefile: Makefile

Submission

You will have to check in two files:

• bintree.h
• bintree.hpp

API Specifications

The header file will have Fill in this part sections and other instructions that you will have to fill in by yourself. From binTree we will only call functions already given in the header files - for the iterators you have to implement the required functions.

binTree Class

binTree contains the necessary attributes and methods for a binary search tree. Feel free to add in more if necessary. The methods are defined below:

• binTree<T>::binTree() : Default constructor.
• binTree<T>::binTree(const binTree<T> & obj) : Copy constructor.
• binTree<T>::~binTree() : Destructor of the tree.
• void binTree<T>::insert(const T &val) : Inserts a node with the value val into the tree. If a node with an identical value exists, simply exit.
• bool binTree<T>::exists(const T &val) const : Returns if a node with a given value exists in the tree.
• int binTree<T>::size() const : Returns the number of items in the tree.
• void binTree<T>::preorder(T *, int) const : Generate an array with items organized in preorder order.
• void binTree<T>::inorder(T *, int) const : Generate an array with items organized in inorder order.
• void binTree<T>::postorder(T *, int) const : Generate and array with items orgainzed in postorder order.
• binTree<T>::preorder_iterator binTree<T>::pre_begin() : Returns an iterator referencing the first node of a preorder traversal.
• binTree<T>::inorder_iterator binTree<T>::in_begin() : Returns an iterator referencing the first node of a inorder traversal.
• binTree<T>::postorder_iterator binTree<T>::post_begin() : Returns an iterator referencing the first node of a postorder traversal.
• binTree<T>::preorder_iterator binTree<T>::pre_end() : Returns an iterator referencing the final node of a preorder traversal.
• binTree<T>::inorder_iterator binTree<T>::in_end() : Returns an iterator referencing the final node of a inorder traversal.
• binTree<T>::postorder_iterator binTree<T>::post_end() : Returns an iterator referencing the final node of a postorder traversal.

treeNode Class

Fill in this class with attributes and methods for a node in a binary search tree.

preorder_iterator Class

Fill in this class for an iterator for preorder traversal. Refer to STL iterators for the necessary implementations.

inorder_iterator Class

Fill in this class for an iterator for inorder traversal. Refer to STL iterators for the necessary implementations.

postorder_iterator Class

Fill in this class for an iterator for postorder traversal. Refer to STL iterators for the necessary implementations.

Const Correctness

Additional Requirements

• No memory leaks are allowed. Gradebot will check for any leaks automatically but consider it as a reference only. After the deadline we will check your library by hand for any memory leaks.
• You must provide meaningful comments in English. Your comment to code ratio must be greater than 0.25 .
• You may not use an array to save the nodes or values in the iterator. The iterator must use O(1) space. We will manually review your code and nullify the scores of those who violate this requirement.
• You must define the access permissions of member functions and attributes wisely. Points will be deducted if you give a method or an attribute more permissions than required, e.g. putting something in protected or public while it can just be private.

Checkout

Checkout the homework from gradebot.

$ git clone metastasis@gradebot.org:user/{username}/3/11

Check in

To check in, make a commit and execute

$ git push origin master