(a) Implement classes TreeNode and BinarySearchTree. Use the following function prototypes as a starting point.
template <typename KeyType, typename ElementType class TreeNode{
KeyType key;
ElementType info;
TreeNode * left, * right; public:
TreeNode(KeyType newKey, ElementType newInfo, TreeNode *l, TreeNode *r); static TreeNode * newNode(KeyType k, ElementType e, TreeNode * l, TreeNode * r); static TreeNode * insert(KeyType key, ElementType info, TreeNode * t); static TreeNode * find(KeyType key , TreeNode * t); static TreeNode * remove(KeyType key , TreeNode * t); static void print(ostream & out , TreeNode * t); static void deleteNode(TreeNode * t); static void deleteTree(TreeNode * t);
};
template <typename KeyType, typename ElementType class BinarySearchTree{ TreeNode * root; public:
void insert(KeyType key, ElementType info); ElementType find(KeyType key); void remove(KeyType key);
void print(ostream & out); };
1. Implement TreeNode
• It will have two data members - a KeyType which will be of type string, and an ElementType which will be of type int.
• ElementType (which will be the count (the frequency of occurrence) of each word in a given file).
2. Implement BinarySearchTree
• You may write some functions recursively.
• You do not have to show O(N) derivations if your functions are recursive.
3. Write the following functions with the O(N) in the comments (unless recursive)
• BinarySearchTree::insert(string s,int count) • BinarySearchTree::find(string s)
1
• BinarySearchTree::remove(string s)
• TreeNode::insert()
• int & BinarySearchTree::operator[] (string s)
(b)Convert TreeNode and BinarySearchTree into a template
1. Convert TreeNode and BinarySearchTree into a template so that KeyType and ElementType may be specified with different types.
