CS1D-Homework 4 Binary Tree Solved

(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.