Binary Search Trees
(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).
- Implement BinarySearchTree
- You may write some functions recursively.
- You do not have to show O(N) derivations if your functions are recursive.
- Write the following functions with the O(N) in the comments (unless recursive)
- BinarySearchTree::insert(string s,int count) BinarySearchTree::find(string s)
CS1D Spring 2019 TTH 5PM HW05: 100pts Due: Thu 03/14/2019 7:20PM
- BinarySearchTree::remove(string s)
- TreeNode::insert()
- int & BinarySearchTree::operator[] (string s)
(b)Convert TreeNode and BinarySearchTree into a template
- Convert TreeNode and BinarySearchTree into a template so that KeyType and ElementType may be specified with different types.
- Create a tar file which includes hw04.cpp, hw04f.cpp, hw04.h, and hw04.scr
- Submit hw04.tar to canvas by the due date on top of this page. 4. Be sure to include valgrind results in your script file
Reviews
There are no reviews yet.