Description
Data Structures and Algorithm Analysis
Data Structure: Binary Search Tree
Programming Focus: C++ class development (inheritance)
For this computer assignment, implement a derived class (as a template) to represent a binary
search tree. Since a binary search tree is a binary tree, implement your binary search tree class
inheriting from the base class of the binary tree that you implemented in your previous
assignment.
The definition of the derived class of a binary search tree (as a template) is given as follows:
template
class BinarySearchTree : public BinaryTree
{
public:
void Insert(const T &x); // inserts node with value x
bool Search(const T &x) const; // searches leaf with value x
bool Remove(const T &x); // removes leaf with value x
private:
void _Insert(Node *&, const T &); // private version of insert
bool _Search(Node *, const T &) const; // private version of search
void _Remove(Node *&, const T &); // private version of remove
bool _Leaf(Node *node) const; // checks if node is leaf
};
The Insert() function inserts a node with the data value x in the tree.
For the Search() function, x is the data value of a leaf to be searched for. If the search
is successful, the Search() function returns true; otherwise, it returns false.
The Remove() function first calls the Search() function to determine the result of the
search for a leaf with the data value x, and if the search is successful, then it calls
_Remove(); the private version of the Remove() function to remove the corresponding
leaf from the tree and returns true; otherwise, it returns false.
The _Leaf() function simply checks if a node is a leaf.
The private versions of the member functions _Insert(), _Remove(), and _Search() can be
implemented as recursive functions, but these functions have an additional argument, which is
the root of the tree. The private version of the _Remove() function unlike its public version does
not return any value.
To test your derived class and its member functions, the source file of a driver program bst.cc
and its header file bst.h, are provided. This program generates a set of random integers in the
range [1, N] with N = 100 and inserts them in a vector and in a binary search tree. The
program searches for each value of the vector in the binary search tree. If the value can be
found as the data value of a leaf, then the leaf is removed from the tree. After removing all the
leaves, the size of the tree and the data values in nodes are printed in ascending order by
traversing the tree in inorder. This process continues until the tree becomes completely empty.
Put the implementation of your binary search tree class in a separate header file, that you
create and add to your repository named binarysearchtree.h. To use the class Node in your
program, include the header file node.h, by inserting the statement: #include “node.h” at
the top of your header file btree.h, and include the header file btree.h in your header file
binarysearchtree.h. Make it sure that each header file is included only once, so the contents
of each header file should be guarded as follows:
// include other header files (if any)
#ifndef BINARYSEARCHTREE_H_
#define BINARYSEARCHTREE_H_
// put statements in header file
#endif // End of BINARYSEARCHTREE_H_
The correct output of this program can be found in file bst.refout, which is in the same
directory with bst.cc.
Note: In public versions of Insert(), Remove(), and Search() functions, you’ll get a compile
error when you pass the root as an argument to these functions. To eliminate the compile
errors, you need to pass the root as this–>root.
Assignment Notes:
Include any necessary headers and add necessary global constants.
You are not allowed to use any I/O functions from the C library, such as scanf or printf.
Instead, use the I/O functions from the C++ library, such as cin or cout.
Add documentation to the appropriate source files as discussed in your class.
Prepare your Makefile (you need to construct and add Makefile) so that the TA only
needs to invoke the command make to compile your source file and produce the
executable file bst. Make sure you use exactly the same file names specified here, i.e.
bst, in your Makefile, otherwise your submission will get 0 points.
When your program is ready for grading, commit and push your local repository to remote git
classroom repository and follow the Assignment Submission Instructions.
CSCI 340
