this is C++ please lable files !! Write the definition of the function,nodecount
ID: 3866856 • 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
Below is your code: -
binaryTree.h
//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree
#include <iostream>
using namespace std;
//Definition of the Node
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() 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.
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<elemType>& otherTree);
//Copy constructor
binaryTreeType();
//Default constructor
~binaryTreeType();
//Destructor
void swapSubtreeNodes();
int treeNodeCount();
int treeLeavesCount();
protected:
nodeType<elemType> *root;
private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* 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<elemType>* &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<elemType> *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<elemType> *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<elemType> *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<elemType> *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<elemType> *p);
int leavesCount(nodeType<elemType> *p);
void swapSubtreeNodes(nodeType<elemType> *p);
};
//Definition of member functions
template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}
template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
return (root == NULL);
}
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
preorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
postorder(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
return height(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
return nodeCount(root);
}
template <class elemType>
void binaryTreeType<elemType>::swapSubtreeNodes()
{
swapSubtreeNodes(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) const
{
if (p != NULL)
{
inorder(p->lLink);
cout << p->info << " ";
inorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::preorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
cout << p->info << " ";
preorder(p->lLink);
preorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::postorder
(nodeType<elemType> *p) const
{
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);
}
//Destructor
template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
destroy(root);
}
template<class elemType>
int binaryTreeType<elemType>::height
(nodeType<elemType> *p) const
{
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) const
{
if (x >= y)
return x;
else
return y;
}
template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p)
{
if(p == NULL)
return 0;
else
return 1 + nodeCount(p->lLink) + nodeCount(p->rLink);
}
template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
{
if (p == NULL)
return 0;
if (p->lLink == NULL && p->rLink == NULL)
return 1;
else
return leavesCount(p->lLink) + leavesCount(p->rLink);
}
template<class elemType>
void binaryTreeType<elemType>::swapSubtreeNodes(nodeType<elemType>*p)
{
nodeType<elemType> *root;
nodeType<elemType> *temp;
if (p == NULL)
{
return;
}
else
{
swapSubtreeNodes (p->lLink);
swapSubtreeNodes (p->rLink);
temp = p->lLink;
p->lLink = p->rLink;
p->rLink = temp;
}
root = temp;
}
#endif
binarySearchTree.h
//Header File Binary Search Tree
#ifndef H_binarySearchTree
#define H_binarySearchTree
#include "binaryTree.h"
#include <iostream>
using namespace std;
template <class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
bool search(const elemType& searchItem) const;
//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 there is no node in the binary search
// tree that 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.
// If the binary tree is empty or deleteItem
// is not in the binary tree, an appropriate
// message is printed.
private:
void deleteFromTree(nodeType<elemType>* &p);
//Function to delete the node to which p points is
//deleted 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) const
{
nodeType<elemType> *current;
bool found = false;
if (this->root == NULL)
cout << "Cannot search an empty tree." << endl;
else
{
current = this->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>;
newNode->info = insertItem;
newNode->lLink = NULL;
newNode->rLink = NULL;
if (this->root == NULL)
this->root = newNode;
else
{
current = this->root;
while (current != NULL)
{
trailCurrent = current;
if (current->info == insertItem)
{
cout << "The item to be inserted is already ";
cout << "in the tree -- 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 (this->root == NULL)
cout << "Cannot delete from an empty tree."
<< endl;
else
{
current = this->root;
trailCurrent = this->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 item to be deleted is not in the tree."
<< endl;
else if (found)
{
if (current == this->root)
deleteFromTree(this->root);
else if (trailCurrent->info > deleteItem)
deleteFromTree(trailCurrent->lLink);
else
deleteFromTree(trailCurrent->rLink);
}
else
cout << "The item to be deleted is not in the tree."
<< endl;
}
} //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)
cout << "Error: The node to be deleted does not exist."
<< 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
#endif
treeDriver.cpp
#include "binarySearchTree.h"
#include <iostream>
using namespace std;
int main() {
int maxSize=14;
int inputArray[maxSize]={60,50,70,30,53,80,35,57,75,32,40,77,48,45};
bSearchTreeType<int> myTree;
cout<<"InorderTraversal Before Swapping: ";
for (int i=0;i<maxSize;i++)
myTree.insert(inputArray[i]);
myTree.inorderTraversal();
cout<<" InorderTraversal After Swapping: ";
myTree.swapSubtreeNodes();
myTree.inorderTraversal();
cout<<" Leaves Count: "<<myTree.treeLeavesCount();
cout<<" Nodes Count: "<<myTree.treeNodeCount()<<endl;
}
Sample Output
InorderTraversal Before Swapping: 30 32 35 40 45 48 50 53 57 60 70 75 77 80
InorderTraversal After Swapping: 80 77 75 70 60 57 53 50 48 45 40 35 32 30
Leaves Count: 4
Nodes Count: 14
--------------------------------
Process exited after 0.07266 seconds with return value 0
Press any key to continue . . .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.