can of parent\'s nodes from the root to node. The root is always at level 0. The

ID: 3845963 • Letter: C

Question

can 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 iterative functions to the binaryTree class to compute a tree's width.

can you please provide a source.CPP

Add (iterative functions) to the binaryTree class to compute a tree's width.

below is the binaryTree class that need modification,.

//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

Explanation / Answer