Homework 4

Due Date: Midnight, Tuesday, November 21
(NOTE: NO LATE HOMEWORKS WILL BE ACCEPTED.)

Assignment:

1. Write a template class definition for a binary tree class called BinTree. The class defintion must contain the following operations:
   • BinTree: default constructor (i.e., no arguments)
   • a copy constructor
   • ~BinTree: destructor
   • overloaded = operator
   • insert: insert a data item into the tree
     • Input: root node pointer
     • Input: data item (not the node) to be inserted
     • Output: none
   • delete: delete a node containing a given data item from the tree
     • Input: root node pointer
     • Input: data item of the node to be deleted
     • Output: true = data item is in tree, false = data item not in tree
   • preorderPrint: perform a preorder traversal to print the tree contents
     • Input: root node pointer
     • Output: none
   • inorderPrint: perform an inorder traversal to print the tree contents
     • Input: root node pointer
     • Output: none
   • postorderPrint: perform a postorder traversal to print the tree contents
     • Input: root node pointer
     • Output: none
   • getRootPtr: return the pointer to the root node
     • Input: none
     • Output: pointer to the root node
   • find: find the location of the node containing a given data item
     • Input: root node pointer
     • Input: data item being searched for
     • Output: pointer to the node located
     • Output: pointer to the parent of the node located
     • Output: true = node found, false = node not found

     Note: Don't get confused by the multiple outputs from the find method. Remember that outputs can be returned via the method's parameter list as well as its return statement.

2. Embed the BinTree class definition in a complete C++ header file called BinTree.H.

3. Write stub (dummy) methods for each of the operations listed above. For example, for a method called anyMethod that has no parameters and returns an integer, the stub would look like: template <class T> int BinTree<T>::anyMethod() { return(1); }

   Place these methods in a file called BinTree.C.

4. Write a template class definition for a binary tree node class called BTNode. The class defintion must contain the following operations:
   • BTNode: default constructor
     • Input: data item to put into the node
     • Output: none
   • a copy constructor
   • ~BTNode: destructor
   • overloaded = operator
   • getData: returns the node's data item
     • Input: none
     • Output: the node's data item

   Make the BinTree class a friend of the BTNode class.

5. Embed the BTNode class definition in a complete C++ header file called BTNode.H.

6. Write stub (dummy) methods for each of the operations listed above. Place these methods in a file called BTNode.C.

7. Write a main function that simply instantiates an object of type BinTree. Place the main function in a file called main.C.

8. Create a makefile to compile and link your code into an executable called hw4.

Homework Submission

Submit your makefile and all five source code files using the usual submit process.

Last Modified: