19.1)Add these three functions to the class binaryTreeType (provided).

Write the definition of the function, nodeCount, that returns the number of nodes in the binary tree.

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.

Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Print the original tree and the resulting tree using a pre-order traversal.

Write a program to test your new functions. Use the data provided to build your binary search tree (-999 is the sentinel):

Data: 65 55 22 44 61 19 90 10 78 52 -999

below is the source code:

//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 = NULL;

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 = NULL;

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 = NULL; }

template bool binaryTreeType::isEmpty() const { return (root == NULL); }

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 == NULL) copiedTreeRoot = NULL; 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 != NULL) { inorder(p->lLink); cout << p->info << " "; inorder(p->rLink); } }

template void binaryTreeType::preorder (nodeType *p) const { if (p != NULL) { cout << p->info << " "; preorder(p->lLink); preorder(p->rLink); } }

template void binaryTreeType::postorder (nodeType *p) const { if (p != NULL) { 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 != NULL) //if the binary tree is not empty, //destroy the binary tree destroy(root);

if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); }//end else

return *this; }

template void binaryTreeType::destroy(nodeType* &p) { if (p != NULL) { destroy(p->lLink); destroy(p->rLink); delete p; p = NULL; } }

template void binaryTreeType::destroyTree() { destroy(root); }

//copy constructor template binaryTreeType::binaryTreeType (const binaryTreeType& otherTree) { if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); }

//Destructor template binaryTreeType::~binaryTreeType() { destroy(root); }

template int binaryTreeType::height (nodeType *p) const { if (p == NULL) 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 << "Write the definition of the function nodeCount." << endl;

return 0; }

template int binaryTreeType::leavesCount(nodeType *p) const { cout << "Write the definition of the function leavesCount." << endl;

return 0; }

#endif