this is C++ please lable files !! Write the definition of the function,nodecount
ID: 3867082 • Letter: T
Question
this is C++
please lable files !!
Write the definition of the function,nodecount,that returns the number of nodes in the binary tree.add this function to the class birnaryTreeType and create a program to test this function
Write the definition of the function,leavescount ,that takes as a parameter a pointer to the root of a binary tree and returns the number of leaves in a binary tree. Add this function to the class binaryTree Type and create a program to test this function
Write a function, swapSubtrees,that swaps all of the left and right subtrees of a binary tree add this function ti the class binarytreeType and create a program to test this function
Explanation / Answer
the Code is given below:
#ifndef H_binaryTree
#define H_binaryTree
#include <iostream>
#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
using namespace std;
template<class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *llink;
nodeType<elemType> *rlink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty();
//Function to determine if the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
// otherwise, returns false.
void inorderTraversal();
//Function to do an inorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the inorder sequence.
void preorderTraversal();
//Function to do a preorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the preorder sequence.
void postorderTraversal();
//Function to do a postorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the postorder sequence.
int treeHeight();
//Function to deteremine the height of the binary tree.
//Postcondition: The height of the binary tree is returned.
int treeNodeCount();
//Function to determine the number of nodes in the
//binary tree.
//Postcondition: The number of nodes in the binary tree
// is returned.
int treeLeavesCount();
//Function to determine the number of leaves in the
//binary tree.
//Postcondition: The number of leaves in the binary tree
// is returned.
void destroyTree();
//Deallocates the memory space occupied by the binary tree.
//Postcondition: root = NULL;
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//copy constructor
binaryTreeType();
//default constructor
~binaryTreeType();
//destructor
protected:
nodeType<elemType> *root;
int leafCnt;
private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot);
//Function to make 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<elemType>* &p);
//Function to destroy the binary tree to which p points.
//Postcondition: The nodes of the binary tree to which
// p points are deallocated.
// p = NULL.
void inorder(nodeType<elemType> *p);
//Function to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the inorder sequence.
void preorder(nodeType<elemType> *p);
//Function to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the preorder sequence.
void postorder(nodeType<elemType> *p);
//Function to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the postorder sequence.
int height(nodeType<elemType> *p);
//Function to determine the height of the binary tree
//to which p points.
//Postcondition: The height of the binary tree to which p
// points is returned.
int max(int x, int y);
//Function to determine the larger of x and y.
//Postcondition: The larger of x and y is returned.
int nodeCount(nodeType<elemType> *p);
//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<elemType> *p);
//Function to determine the number of leaves in the binary
//tree to which p points.
//Postcondition: The number of nodes in the binary tree
// to which p points is returned.
int childCount(nodeType<elemType> *p);
};
//Definition of member functions
template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
nodecnt=0;
leafCnt=0;
}
template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
{
return (root == NULL);
}
template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
{
inorder(root);
}
template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
{
preorder(root);
}
template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
{
postorder(root);
}
template<class elemType>
int binaryTreeType<elemType>::treeHeight()
{
return height(root);
}
template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
return nodeCount(root);
}
template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
{
return leavesCount(root);
}
template <class elemType>
void binaryTreeType<elemType>::copyTree
(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot)
{
if(otherTreeRoot == NULL)
copiedTreeRoot = NULL;
else
{
copiedTreeRoot = new nodeType<elemType>;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
}
} //end copyTree
template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
if(p != NULL)
{
inorder(p->llink);
cout<<p->info<<" ";
inorder(p->rlink);
}
}
template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
{
if(p != NULL)
{
cout<<p->info<<" ";
preorder(p->llink);
preorder(p->rlink);
}
}
template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
{
if(p != NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout<<p->info<<" ";
}
}
//Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& 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 <class elemType>
void binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
if(p != NULL)
{
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;
}
}
template <class elemType>
void binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}
//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
(const binaryTreeType<elemType>& otherTree)
{
if(otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}
template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
destroy(root);
}
template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p)
{
if(p == NULL)
return 0;
else
return 1 + max(height(p->llink), height(p->rlink));
}
template<class elemType>
int binaryTreeType<elemType>::max(int x, int y)
{
if(x >= y)
return x;
else
return y;
}
template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p){
// Count the nodes in the binary tree to which
// root points, and return the answer.
if ( p == NULL )
return 0; // The tree is empty. It contains no nodes.
else {
int count = 1; // Start by counting the root.
count += nodeCount(root->left); // Add the number of nodes
// in the left subtree.
count += nodeCount(root->right); // Add the number of nodes
// in the right subtree.
return count; // Return the total.
}
}
template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p){
cout<<"The top element is:"<<p->info<<endl;
if(p->llink!=NULL)
leafCnt+=leavesCount(p->llink);
if(p->rlink!=NULL)
leafCnt+=leavesCount(p->rlink);
return leafCnt;
}
template<class elemType>
int binaryTreeType<elemType>::childCount(nodeType<elemType> *p){
if (p == NULL)
return 0;
}
//bbbbbbbbsearchtreee
template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
bool search(const elemType& searchItem);
//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 no node in the binary search tree 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.
private:
void deleteFromTree(nodeType<elemType>* &p);
//Function to delete the node, to which p points, from the
//binary search tree.
//Postcondition: The node to which p points is deleted
// from the binary search tree.
};
template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
nodeType<elemType> *current;
bool found = false;
if(root == NULL)
cerr<<"Cannot search the empty tree."<<endl;
else
{
current = root;
while(current != NULL && !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<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
nodeType<elemType> *current; //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
nodeType<elemType> *newNode; //pointer to create the node
newNode = new nodeType<elemType>;
assert(newNode != NULL);
newNode->info = insertItem;
newNode->llink = NULL;
newNode->rlink = NULL;
if(root == NULL)
root = newNode;
else
{
current = root;
while(current != NULL)
{
trailCurrent = current;
if(current->info == insertItem)
{
cerr<<"The insert item is already in the list -- ";
cerr<<"duplicates are not allowed."<<endl;
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<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
nodeType<elemType> *current; //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
bool found = false;
if(root == NULL)
cerr<<"Cannot delete from the empty tree."<<endl;
else
{
current = root;
trailCurrent = root;
while(current != NULL && !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 == NULL)
cout<<"The delete item 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);
}//end if
}
}//end deleteNode
template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
(nodeType<elemType>* &p)
{
nodeType<elemType> *current; //pointer to traverse
//the tree
nodeType<elemType> *trailCurrent; //pointer behind current
nodeType<elemType> *temp; //pointer to delete the node
if(p == NULL)
cerr<<"Error: The node to be deleted is NULL."
<<endl;
else if(p->llink == NULL && p->rlink == NULL)
{
temp = p;
p = NULL;
delete temp;
}
else if(p->llink == NULL)
{
temp = p;
p = temp->rlink;
delete temp;
}
else if(p->rlink == NULL)
{
temp = p;
p = temp->llink;
delete temp;
}
else
{
current = p->llink;
trailCurrent = NULL;
while(current->rlink != NULL)
{
trailCurrent = current;
current = current->rlink;
}//end while
p->info = current->info;
if(trailCurrent == NULL) //current did not move;
//current == p->llink; adjust p
p->llink = current->llink;
else
trailCurrent->rlink = current->llink;
delete current;
}//end else
}//end deleteFromTree
int main(){
int maxSize=14;
int inputArray[maxSize]=(60,50,70,30,53,80,35,57,75,32,40,77,48,45);
char inChoice;
bSearchTreeType<int> myTree;
for (int i=0;i<maxSize;i++)
myTree.insert(inputArray[i]);
cout<<"Display output using: a)inorder traversal b)preorder traversal";
cout<<" c)postorder traversal Enter choice:";
cin>>inChoice;
cout<<" ";
switch(inChoice)
{
case'a':case'A':
myTree.inorderTraversal();
break;
case'b':case'B':
myTree.preorderTraversal();
break;
case'c':case'C':
myTree.postorderTraversal();
break;
}
cout<<endl;
cout<<" The number of nodes in the tree is-are:"<<myTree.treeNodeCount()<<endl;
cout<<" The number of leaves in the tree is-are:"<<myTree.treeLeavesCount()<<endl;
cout<<endl;
return 0;
}
Hope This Helps
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.