CSC 240 PA5 Working with Binary Trees Write the definitions of the member functions nodeCount() and leavesCount() that return the number of nodes and leaves, respectively, in the binary tree of type binaryTreeType . See the ToDo sections in binaryTree.h . This is the only file you should modify and submit. You should compile the main.cpp provided, in the presence of the binarySearchTree.h that is provided, as well as your modified binaryTree.h . Each of these two (template) functions should take as a parameter a pointer to a node of a binary tree, and return an integer. One of them still needs to be added to the class. Do not alter the functions treeNodeCount() or treeLeavesCount()--they are wrappers that merely call your functions. While your functions can theoretically perform the counts on a subtree, the wrapper calls yours passing the root node pointer, ensuring that the full tree will be counted. Chapter 19 discusses binary trees at length. Sample Run: Enter integers ending with -999 65 55 22 44 61 19 40 10 18 52 -999 Tree nodes in inorder: 10 18 19 22 40 44 52 55 61 65 Tree nodes in preorder: 65 55 22 19 10 18 44 40 52 61 Tree nodes in postorder: 18 10 19 40 52 44 22 61 55 65 Tree Height: 6 Number of Nodes: 10 Number of Leaves: 4 (after Malik, C++ Programming: Program Design Including Data Structures, 7E)

----------------------------------------------binaryTree.h(Edit this one)----------------------------------------------------

//Header File Binary Search Tree // See the 'ToDo's below // Your name // and date #ifndef H_binaryTree #define H_binaryTree #include  using namespace std; //Definition of the Node template  struct nodeType { elemType info; nodeType *lLink; nodeType *rLink; }; //Definition of the class template  class binaryTreeType { public: const binaryTreeType& operator= (const binaryTreeType&); //Overload the assignment operator. bool isEmpty() const; //Function to determine whether the binary tree is empty. //Postcondition: Returns true if the binary tree is empty; // otherwise, returns false. void inorderTraversal() const; //Function to do an inorder traversal of the binary tree. //Postcondition: Nodes are printed in inorder sequence. void preorderTraversal() const; //Function to do a preorder traversal of the binary tree. //Postcondition: Nodes are printed in preorder sequence. void postorderTraversal() const; //Function to do a postorder traversal of the binary tree. //Postcondition: Nodes are printed in postorder sequence. int treeHeight() const; //Function to determine the height of a binary tree. //Postcondition: Returns the height of the binary tree. int treeNodeCount() const; //Function to determine the number of nodes in a //binary tree. //Postcondition: Returns the number of nodes in the // binary tree. int treeLeavesCount() const; //Function to determine the number of leaves in a //binary tree. //Postcondition: Returns the number of leaves in the // binary tree. void destroyTree(); //Function to destroy the binary tree. //Postcondition: Memory space occupied by each node // is deallocated. // root = nullptr; virtual bool search(const elemType& searchItem) const = 0; //Function to determine if searchItem is in the binary //tree. //Postcondition: Returns true if searchItem is found in // the binary tree; otherwise, returns // false. virtual void insert(const elemType& insertItem) = 0; //Function to insert insertItem in the binary tree. //Postcondition: If there is no node in the binary tree // that has the same info as insertItem, a // node with the info insertItem is created // and inserted in the binary search tree. virtual void deleteNode(const elemType& deleteItem) = 0; //Function to delete deleteItem from the binary tree //Postcondition: If a node with the same info as // deleteItem is found, it is deleted from // the binary tree. // If the binary tree is empty or // deleteItem is not in the binary tree, // an appropriate message is printed. binaryTreeType(const binaryTreeType& otherTree); //Copy constructor binaryTreeType(); //Default constructor ~binaryTreeType(); //Destructor protected: nodeType *root; private: void copyTree(nodeType* &copiedTreeRoot, nodeType* otherTreeRoot); //Makes a copy of the binary tree to which //otherTreeRoot points. //Postcondition: The pointer copiedTreeRoot points to // the root of the copied binary tree. void destroy(nodeType* &p); //Function to destroy the binary tree to which p points. //Postcondition: Memory space occupied by each node, in // the binary tree to which p points, is // deallocated. // p = nullptr; void inorder(nodeType *p) const; //Function to do an inorder traversal of the binary //tree to which p points. //Postcondition: Nodes of the binary tree, to which p // points, are printed in inorder sequence. void preorder(nodeType *p) const; //Function to do a preorder traversal of the binary //tree to which p points. //Postcondition: Nodes of the binary tree, to which p // points, are printed in preorder // sequence. void postorder(nodeType *p) const; //Function to do a postorder traversal of the binary //tree to which p points. //Postcondition: Nodes of the binary tree, to which p // points, are printed in postorder // sequence. int height(nodeType *p) const; //Function to determine the height of the binary tree //to which p points. //Postcondition: Height of the binary tree to which // p points is returned. int max(int x, int y) const; //Function to determine the larger of x and y. //Postcondition: Returns the larger of x and y. int nodeCount(nodeType *p) const; //Function to determine the number of nodes in //the binary tree to which p points. //Postcondition: The number of nodes in the binary // tree to which p points is returned. // ToDo : declare leavesCount() here:  //Function to determine the number of leaves in //the binary tree to which p points //Postcondition: The number of leaves in the binary // tree to which p points is returned. }; //Definition of member functions template  binaryTreeType::binaryTreeType() { root = nullptr; } template  bool binaryTreeType::isEmpty() const { return (root == nullptr); } template  void binaryTreeType::inorderTraversal() const { inorder(root); } template  void binaryTreeType::preorderTraversal() const { preorder(root); } template  void binaryTreeType::postorderTraversal() const { postorder(root); } template  int binaryTreeType::treeHeight() const { return height(root); } template  int binaryTreeType::treeNodeCount() const { return nodeCount(root); } template  int binaryTreeType::treeLeavesCount() const { return leavesCount(root); } template  void binaryTreeType::copyTree (nodeType* &copiedTreeRoot, nodeType* otherTreeRoot) { if (otherTreeRoot == nullptr) copiedTreeRoot = nullptr; else { copiedTreeRoot = new nodeType; copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink); copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink); } } //end copyTree template  void binaryTreeType::inorder (nodeType *p) const { if (p != nullptr) { inorder(p->lLink); cout << p->info << " "; inorder(p->rLink); } } template  void binaryTreeType::preorder (nodeType *p) const { if (p != nullptr) { cout << p->info << " "; preorder(p->lLink); preorder(p->rLink); } } template  void binaryTreeType::postorder (nodeType *p) const { if (p != nullptr) { postorder(p->lLink); postorder(p->rLink); cout << p->info << " "; } } //Overload the assignment operator template  const binaryTreeType& binaryTreeType:: operator=(const binaryTreeType& otherTree) { if (this != &otherTree) //avoid self-copy { if (root != nullptr) //if the binary tree is not empty, //destroy the binary tree destroy(root); if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); }//end else return *this; } template  void binaryTreeType::destroy(nodeType* &p) { if (p != nullptr) { destroy(p->lLink); destroy(p->rLink); delete p; p = nullptr; } } template  void binaryTreeType::destroyTree() { destroy(root); } //copy constructor template  binaryTreeType::binaryTreeType (const binaryTreeType& otherTree) { if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); } //Destructor template  binaryTreeType::~binaryTreeType() { destroy(root); } template int binaryTreeType::height (nodeType *p) const { if (p == nullptr) return 0; else return 1 + max(height(p->lLink), height(p->rLink)); } template  int binaryTreeType::max(int x, int y) const { if (x >= y) return x; else return y; } // ToDo : implement the member template function // nodeCount() here. Name the template class parameter // 'elemType' . Have nodeCount() take one parameter, a // nodeType pointer, and return an int. // The logic will be recursive, containing two calls to // itself. // ToDo : implement the member template function // leavesCount() here. Name the template class parameter // 'elemType' . Have leavesCount() take a nodeType pointer // and return an int. The logic will be recursive, containing // two calls to itself. #endif 

-------------------------------------------------binarySearchTree.h------------------------------------------------------

//Header File Binary Search Tree // Students do not modify // wrb 2018 #ifndef H_binarySearchTree #define H_binarySearchTree #include  #include "binaryTree.h" using namespace std; template <class elemType> class bSearchTreeType: public binaryTreeType { public: bool search(const elemType& searchItem) const; //Function to determine if searchItem is in the binary //search tree. //Postcondition: Returns true if searchItem is found in // the binary search tree; otherwise, // returns false. void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If there is no node in the binary search // tree that has the same info as // insertItem, a node with the info // insertItem is created and inserted in the // binary search tree. void deleteNode(const elemType& deleteItem); //Function to delete deleteItem from the binary search tree //Postcondition: If a node with the same info as deleteItem // is found, it is deleted from the binary // search tree. // If the binary tree is empty or deleteItem // is not in the binary tree, an appropriate // message is printed. private: void deleteFromTree(nodeType* &p); //Function to delete the node to which p points is //deleted from the binary search tree. //Postcondition: The node to which p points is deleted // from the binary search tree. }; template <class elemType> bool bSearchTreeType::search (const elemType& searchItem) const { nodeType *current; bool found = false; if (this->root == nullptr) cout << "Cannot search an empty tree." << endl; else  { current = this->root; while (current != nullptr && !found) { if (current->info == searchItem) found = true; else if (current->info > searchItem) current = current->lLink; else  current = current->rLink; }//end while }//end else return found; }//end search template <class elemType> void bSearchTreeType::insert (const elemType& insertItem) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent = nullptr; //pointer //behind current nodeType *newNode; //pointer to create the node newNode = new nodeType; newNode->info = insertItem; newNode->lLink = nullptr; newNode->rLink = nullptr; if (this->root == nullptr) this->root = newNode; else  { current = this->root; while (current != nullptr) { trailCurrent = current; if (current->info == insertItem) { cout << "The item to be inserted is already "; cout << "in the tree -- duplicates are not " << "allowed." << endl; return; } else if (current->info > insertItem) current = current->lLink; else  current = current->rLink; }//end while if (trailCurrent->info > insertItem) trailCurrent->lLink = newNode; else  trailCurrent->rLink = newNode; } }//end insert template <class elemType> void bSearchTreeType::deleteNode (const elemType& deleteItem) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current bool found = false; if (this->root == nullptr) cout << "Cannot delete from an empty tree." << endl; else  { current = this->root; trailCurrent = this->root; while (current != nullptr && !found) { if (current->info == deleteItem) found = true; else  { trailCurrent = current; if (current->info > deleteItem) current = current->lLink; else  current = current->rLink; } }//end while if (current == nullptr) cout << "The item to be deleted is not in the tree." << endl; else if (found) { if (current == this->root) deleteFromTree(this->root); else if (trailCurrent->info > deleteItem) deleteFromTree(trailCurrent->lLink); else  deleteFromTree(trailCurrent->rLink); } else  cout << "The item to be deleted is not in the tree." << endl; } } //end deleteNode template <class elemType> void bSearchTreeType::deleteFromTree (nodeType* &p) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current nodeType *temp; //pointer to delete the node if (p == nullptr) cout << "Error: The node to be deleted does not exist." << endl; else if (p->lLink == nullptr && p->rLink == nullptr) { temp = p; p = nullptr; delete temp; } else if (p->lLink == nullptr) { temp = p; p = temp->rLink; delete temp; } else if (p->rLink == nullptr) { temp = p; p = temp->lLink; delete temp; } else  { current = p->lLink; trailCurrent = nullptr; while (current->rLink != nullptr) { trailCurrent = current; current = current->rLink; }//end while p->info = current->info; if (trailCurrent == nullptr) //current did not move; //current == p->lLink; adjust p p->lLink = current->lLink; else  trailCurrent->rLink = current->lLink; delete current; }//end else } //end deleteFromTree #endif 

----------------------------------------------------main.cpp--------------------------------------------

//Data: 65 55 22 44 61 19 40 10 18 52 -999 // Driver file main.cpp // Students do not modify // wrb 2018 #include  #include "binarySearchTree.h" using namespace std; int main() { bSearchTreeType<int> treeRoot; int num; cout << "Enter integers ending with -999" << endl; cin>>num; while (num != -999) { treeRoot.insert(num); cin >> num; } cout << endl << "Tree nodes in inorder: "; treeRoot.inorderTraversal(); cout << endl << "Tree nodes in preorder: "; treeRoot.preorderTraversal(); cout << endl << "Tree nodes in postorder: "; treeRoot.postorderTraversal(); cout << endl; cout << "Tree Height: " << treeRoot.treeHeight() << endl; cout << "Number of Nodes: " << treeRoot.treeNodeCount() << endl; cout << "Number of Leaves: " << treeRoot.treeLeavesCount() << endl; cout << endl; return 0; }