Write a program that uses the binary tree definition in Figure 6.8 on page 220-222 1. Add a function to the class to count the number of nodes in a binary tree 2. Add a function to the class to count the number of leaves in a binary tree YOU MUST USE THE BINARY TREE DEFINITION AS LISTED IN THE BOOK. Any other tree definition will not be accepted. Create a program that uses this class as follows (The tree is used store strings names)

1. The program should present the user with a menu as follows:

1. Add a new name 2. Delete a name 3. List the contents in ascending order 4. Display the number of nodes in the tree 5. Display the number of leafs 6. Exit the system Please enter your choice 2. Create a function for each option on the menu to handle the request. 3. For choice # 1 (Add a new value), the function should prompt the user to enter a value (a string). If the value is already stored in the tree, you should display a message that indicates that. 4. For choice # 2 (Delete a value), the function should prompt the user to enter a value (a string). Display a message to indicate if the value is found and deleted or if it is not found. 5. Main() should call a function called menu() to display the menu and return users input. Main() should not handle any input or output other than reading and validating users input.

220 Chapter 6 Binary Trees FIGURE 6.8 mplementation of a generic binary search tree. //***genBST.h ** generic binary search tree #include #include queue> using namespace std; #ifndef BINARY SEARCH TREE #de fine BINARYSEARCH TREE - templatecclass T> class Stack public stackeT> >//as in Figure 4.21 templatecclass T> class Queue public queue public: T dequeue) T tmp front O queue: :popO return tmp; void enqueue (const T&el) push (el) templatecclass T> class BSTNode public: BSTNode () left- right 0 T el; BSTNode class BST public: BSTO root-0 -BST () clear ) void clear) clear (root) root 0 bool isEmpty) const return root 0; void preorder) preorder (root) // Figure 6.11 void inorder) inorder (root) // Figure 6.11 void postorder) postorder (root) // Figure 6.11 T* search (const T& el) const return search (root,el); // Figure 6.9 void breadthFirst) void iterativePreorder void iterativeInorder void iterativePostorder) void MorrisInorder O void insert (const T&) void deleteByMerging (BSTNodeT>*&) ; // Figure 6.10 // Figure 6.15 // Figure 6.17 // Figure 6.16 // Figure 6.20 // Figure 6.23 // Figure 6.29 void findAndDeleteByMerging (const T&) i // Figure 6.29 void void deleteByCopying (BSTNodeT>*&) ; balance (T*, int,int); // Figure 6.32 // Section 6.7 protected BSTNodeeT>* root; Continues 222 Chapter 6 Binary Trees FIGURE 6.8 (continued) void clear (BSTNode*) void inorder (BSTNode*) virtual void visit (BSTNode* p) // Figure 6.11 // Figure 6.11 // Figure 6.11 cout