CptS 122 –
Data Structures
Lab 13: Developing a BST Class in C++
Assigned: Week of
Due: At the end of the
lab session
I. Learner
Objectives:
At the conclusion
of this programming assignment, participants should be able to:
II.
Prerequisites:
Before starting
this programming assignment, participants should be able to:
This lab, along with your TA, will help you navigate through designing,
implementing, and testing a BST class in C++. It will also help you with understanding
how to apply a BST object to an application.
Labs are held in a “closed” environment such that you may ask your TA
questions. Please use your TAs knowledge to your advantage. You are required to
move at the pace set forth by your TA. Please help other students in need when
you are finished with a task. You may work in pairs if you wish. However, I
encourage you to compose your own solution to each problem. Have a great time!
Labs are a vital part to your education in CptS 122 so work diligently.
Tasks:
For this lab you
will develop a BST class and use it to solve a sorting problem. You will create
the BSTNode and BST declarations in a single .h file, called BST.h, and define
all of the functionality in BST.cpp.
Task 1. Defining
a class, BSTNode
Start this task by
designing the BSTNode class for the BST. For the initial development you should
just build the node to hold a string as its data. The BSTNode class will
consist of a string and left and right pointers. It will be able to make a new
node using it’s constructor. You will also overload the stream insertion
operator << to output a node.
Finally, you will
need to make the class BST a friend of the BSTNode class so that the class BST
will be able to access the member data of the BSTNode, but still keep it
private from every one else. Do this by including the statement:
friend class BST;
Ok, now that
you have this, create the forward declaration for the class BST
class BST; // this is a forward declaration.
Task 2. Now
create the BST class
Implement a BST
class. You are now ready to define the BST class. You should create an
attribute member for a pointer that will be the root of the BST. The pointers
should be of type BSTNodePtr. You will also implement the constructor, the copy
constructor, the assignment operator, and the destructor.
Additionally, you
need:
insertNode ( ) - that adds an item to the BST.
inOrderTraversal ( ) - that prints the
contents of the BST inorder.
preOrderTraversal ( ) - that prints the contents of the BST preorder.
postOrderTraversal
( ) - that prints the contents of the BST postorder.
isEmpty ( ) - that is a Boolean function that indicates
that the BST is empty or not.
You will overload the stream insertion operator << to output a BST in a elegant way. Here is an example of both non-templated and templated BST class. Please see the differences and follow either one of these for this lab assignment.
// Non-templated BST Class
class BST
{
private:
struct Node
{
char* Data;
Node* Left;
Node* Right;
Node(char* dataStringToCopy)
{
Data = new char[strlen(dataStringToCopy) + 1];
strcpy(Data, dataStringToCopy);
Left = Right = NULL;
}
~Node()
{
delete []
Data;
}
};
// Pointer to the root node
Node*
m_root;
public:
BST();
~BST();
// Adds an item to the BST
void insertNode(char* stringItem);
// Prints the contents of the BST inorder
void inOrderTraversal();
// Prints the contents of the BST preorder
void
preOrderTraversal();
// Prints the contents of the BST postorder
void
postOrderTraversal();
// Boolean function that indicates that the BST is
empty or not
bool isEmpty();
// You may add more helper functions if needed
};
// Templated BST Class
template< class NODETYPE > class BST; // forward declaration
template<class NODETYPE>
class BSTNode
{
friend class BST< NODETYPE >;
// make BST a friend
public:
BSTNode( const NODETYPE & d
): leftPtr(0), data(d), rightPtr(0) { }; // copy constructor
NODETYPE getData() const { // return data in the node
return data;
}
private:
NODETYPE data; // data
BSTNode< NODETYPE > *leftPtr; // pointer to left subtree
BSTNode< NODETYPE >
*rightPtr; // pointer to right subtree
};
template< class NODETYPE >
class BST
{
public:
BST(); // constructor
~BST(); // destructor
void insertNode( const NODETYPE & );
void preOrderTraversal( ) const;
void inOrderTraversal( ) const;
void postOrderTraversal( ) const;
bool isEmpty()
const;
private:
BSTNode< NODETYPE >
*rootPtr; // pointer to root node
// Utility function
void insertNodeHelper (BSTNode< NODETYPE > **, const NODETYPE & );
void preOrderHelper (BSTNode< NODETYPE > * ) const;
void inOrderHelper (BSTNode< NODETYPE > * ) const;
void postOrderHelper (BSTNode< NODETYPE >
* ) const;
Task 3. Create a
an application to sort strings
Create an application
that populates an array with names of your favorite people. Take the array and
place all names in the array into a BST object. Traverse the BST inorder (you
will need to modify inorder) and place the inorder strings back into the
original array. The array of people's names is now sorted. QUESTION: When would
it be a good idea to use a BST for sorting items? Do you know of other
algorithms and data structures that are more efficient for a sorting task?
IV. Submitting Labs:
V. Grading Guidelines: