CSc 300 – Assignment #5 solution

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 for the submission file // I would use
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.