A node's level is the number of parent's nodes from the root to node. The root is always at level 0. The root's children are a level 1 and so on. A level's width is the number of nodes at the level. A tree's width the greatest width of all of a tree's levels' width.

Add recursive functions to the binaryTree class to compute a tree's width.

below is the given binaryTree class

//Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree

//************************************************************* // Author: D.S. Malik // // class binaryTreeType // This class specifies the basic operations to implement a // binary tree. //*************************************************************

#include

using namespace std;

//Definition of the node template struct binaryTreeNode { elemType info; binaryTreeNode *llink; binaryTreeNode *rlink; };

template class countNodes { public: countNodes() { _count = 0; } unsigned count() const { return _count; } void operator() (binaryTreeNode* p) { if(p != NULL) _count++; }

private: unsigned _count; };

//Definition of the class template class binaryTreeType { public: const binaryTreeType& operator= (const binaryTreeType&); //Overload the assignment operator. bool isEmpty() const; //Returns true if the binary tree is empty; //otherwise, returns false. void inorderTraversal() const; //Function to do an inorder traversal of the binary tree. void inorderTraversal2(countNodes& counter) const; //Function to do an inorder traversal of the binary tree. void preorderTraversal() const; //Function to do a preorder traversal of the binary tree. void postorderTraversal() const; //Function to do a postorder traversal of the binary tree.

int treeHeight() const; //Returns the height of the binary tree. int treeNodeCount() const; //Returns the number of nodes in the binary tree. int treeLeavesCount() const; //Returns the number of leaves in the binary tree. void destroyTree(); //Deallocates the memory space occupied by the binary tree. //Postcondition: root = NULL;

binaryTreeType(const binaryTreeType& otherTree); //copy constructor

binaryTreeType(); //default constructor

~binaryTreeType(); //destructor

protected: binaryTreeNode *root;

private: void copyTree(binaryTreeNode* &copiedTreeRoot, binaryTreeNode* otherTreeRoot); //Makes a copy of the binary tree to which //otherTreeRoot points. The pointer copiedTreeRoot //points to the root of the copied binary tree.

void destroy(binaryTreeNode* &p); //Function to destroy the binary tree to which p points. //Postcondition: p = NULL

void inorder(binaryTreeNode *p) const; //Function to do an inorder traversal of the binary //tree to which p points. void inorder2(binaryTreeNode *p, countNodes& counter ) const; //Function to do an inorder traversal of the binary //tree to which p points.

void preorder(binaryTreeNode *p) const; //Function to do a preorder traversal of the binary //tree to which p points. void postorder(binaryTreeNode *p) const; //Function to do a postorder traversal of the binary //tree to which p points.

int height(binaryTreeNode *p) const; //Function to return the height of the binary tree //to which p points. int max(int x, int y) const; //Returns the larger of x and y. int nodeCount(binaryTreeNode *p) const; //Function to return the number of nodes in the binary //tree to which p points int leavesCount(binaryTreeNode *p) const; //Function to return the number of leaves in the binary //tree to which p points };

//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::inorderTraversal2(countNodes& counter) const { inorder2(root, counter); } template void binaryTreeType::inorder2(binaryTreeNode *p, countNodes& counter ) const { if(p != NULL) { inorder2(p->llink, counter); counter(p); cout << p->info << ' '; inorder2(p->rlink, counter); } } 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 (binaryTreeNode* &copiedTreeRoot, binaryTreeNode* otherTreeRoot) { if (otherTreeRoot == NULL) copiedTreeRoot = NULL; else { copiedTreeRoot = new binaryTreeNode; copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->llink, otherTreeRoot->llink); copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink); } } //end copyTree

template void binaryTreeType::inorder(binaryTreeNode *p) const { if (p != NULL) { inorder(p->llink); cout << p->info << " "; inorder(p->rlink); } }

template void binaryTreeType::preorder(binaryTreeNode *p) const { if (p != NULL) { cout<info<<" "; preorder(p->llink); preorder(p->rlink); } }

template void binaryTreeType::postorder(binaryTreeNode *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(binaryTreeNode* &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); }

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

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

return 0; }

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

return 0; }

#endif