//Header File Binary Search Tree #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 info rLink); } } template void binaryTreeType::preorder (nodeType *p) const { if (p != nullptr) { cout info lLink); preorder(p->rLink); } } template void binaryTreeType::postorder (nodeType *p) const { if (p != nullptr) { postorder(p->lLink); postorder(p->rLink); cout info 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 { cout int binaryTreeType::leavesCount(nodeType *p) const { cout

2. Write the definition of the function leavesCount that takes as a parameter a pointer to the root node of a binary tree and returns the number of leaves in a binary tree. Add this function to the class