Description
Create a user-defined Abstract Data Type (ADT) that implements a Binary Search Tree using a C++ class
named BSTreeType and an appropriate set of C++ header/implementation files as discussed in class.
• The BSTreeType ADT must be implemented using a dynamic linked structure.
• Each element stored in the BSTreeType ADT is of type ElementType.
The BSTreeType ADT must define and implement the following data types and operations.
• Do not add to or modify the public interface (exportable components – public components).
• Do not add to or modify any attributes or data types (storage components).
Exportable Operations: (declared .h file and defined .cpp file)
BSTreeType default constructor – creates an initialized empty BST
BSTreeType copy constructor – uses copy to create a duplicate copy of an existing BST
~BSTreeType destructor – uses destroy to remove all elements from an existing BST
BST instance state before going out of scope – initialized empty BST
insert inserts a new element node to the BST – ignore duplicates (*)
do not add duplicate nodes – do not count duplicate insert attempts
remove locates an existing element node to be removed from the BST (*)
uses removeNode to handle the actual node removal process
search returns a pointer to an existing element node in the BST, otherwise NULL (*)
not used as part of the remove element node process (returns an external pointer)
preOrderView displays the elements in the BST from top to bottom (left to right) (*)
inOrderView displays the elements in the BST in ascending order (*)
postOrderView displays the elements in the BST from bottom to top (left to right) (*)
Non-Exportable Operations: (declared .h file and defined .cpp file)
copy recursively copies an existing BST (form of pre-order traversal)
destroy recursively removes all element nodes from the BST (form of post-order traversal)
removeNode removes an existing element node from the BST
findMinNode finds the minimum element node in the right subtree of the BST
(*) recursive version of each of the 6 exportable functions (function overloading required)
Exportable User-Defined Data Types: (Usage not restricted to the BSTreeType class alone)
ElementType, NodeType, PointerType
ElementType is a primitive int data type
NodeType consists of three fields: element, left, right
PointerType is a pointer to a NodeType
BSTreeType Required Output Format: (inOrderView example)
// Empty Tree // Populated Tree
The Start -> The End The Start -> -10 -> 0 -> 10 -> The End
Make sure that you completely document the header/implementation files.
• The header (.h) file tells the user exactly how to use your ADT
o General descriptions only – do not include implementation details
• The implementation file (.cpp) tells the implementer/programmer exactly how the ADT works
o Detailed descriptions – include implementation details
Zip together and e-mail your header/implementation files using the following naming convention.
• Do not e-mail your main/driver program
o I will create my own main/driver program to test your ADT
username5.h for the header file // I would use gamradtk5.h
username5.cpp for the implementation file // I would use gamradtk5.cpp
username5.zip for the submission file // I would use gamradtk5.zip
List the class number, your username, and assignment number as the e-mail message
SUBJECT: csc300 – gamradtk – a5 // This is what I would use
Required header file (.h). (only partially specified)
// General description of the ADT and supported operations – exportable operations only
// Do not include any implementation details
// ElementType, NodeType, PointerType – declarations/definitions here
class BSTreeType {
public: // exportable
BSTreeType();
BSTreeType( const BSTreeType & );
~BSTreeType();
void insert( const ElementType );
void remove( const ElementType );
PointerType search( const ElementType ) const;
void preOrderView() const;
void inOrderView() const;
void postOrderView() const;
private: // non-exportable
PointerType theTree;
void copy( const PointerType );
void destroy( PointerType & );
void removeNode( PointerType & );
void findMinNode( PointerType &, PointerType & );
void insert( PointerType &, const ElementType );
void remove( PointerType &, const ElementType );
PointerType search( const PointerType, const ElementType ) const;
void preOrderView( const PointerType ) const;
void inOrderView( const PointerType ) const;
void postOrderView( const PointerType ) const;
};
Define a macro to prevent multiple inclusion of the header file.
• I would use _GAMRADTK5_H for a header file with the filename gamradtk5.h.
I will write a test program that will include your ADT so all header/implementation files tested must use
common names. So you MUST use:
• the EXACT same names for each data type and function in the header/implementation files.
• the EXACT same function argument sequence in the header/implementation files.
Throughout the textbook examples are shown using Templates.
• Do not use Templates unless you are explicitly told to do so.
