(C++) Below are binaryTreeType and binarySearchTree classes. class binaryTreeType has function nodeCount and leavesCount.

Create a test program (main) to test nodeCount and leavesCount functions.

The test code will need to work for the binarySearchTree class since binaryTreeType is an abstract class.

#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. int leavesCount(nodeType *p) const; //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; } template int binaryTreeType::nodeCount(nodeType *p) const { // base case if(p == NULL) return 0;

return (nodeCount(p->lLink) + 1 + nodeCount(p->rLink)); } template int binaryTreeType::leavesCount(nodeType *p) const { // base case if(p == NULL) return 0; if(p->lLink == NULL && p->rLink == NULL) return 1; return leavesCount(p->lLink) + leavesCount(p->rLink); } #endif //Header File Binary Search Tree //binarySearchTree.h #ifndef H_binarySearchTree #define H_binarySearchTree #include #include "binaryTree.h" using namespace std; template 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 bool bSearchTreeType::search(const elemType& searchItem) const { nodeType *current; bool found = false; if (root == nullptr) cout << "Cannot search an empty tree." << endl; else { current = 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 void bSearchTreeType::insert(const elemType& insertItem) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current nodeType *newNode; //pointer to create the node newNode = new nodeType; newNode->info = insertItem; newNode->lLink = nullptr; newNode->rLink = nullptr; if (root == nullptr) root = newNode; else { current = 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; delete newNode; 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 void bSearchTreeType::deleteNode(const elemType& deleteItem) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current bool found = false; if (root == nullptr) cout << "Cannot delete from an empty tree." << endl; else { current = root; trailCurrent = 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 == root) deleteFromTree(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 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