Homework SourseC Add these three functions to the class binaryTreeType prov
(C++) Add these three functions to the class binaryTreeType (provided below).
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): Example Data: 65 55 22 44 61 19 90 10 78 52 -999
Already completed code is below:
//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
//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
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.
};
//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() const
{
return nodeCount(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
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;
}
#endif
Solution
CODE:
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.
SOLN:------>
template<class elemType>
int binaryTreeType<elemType>::LeavesCount()
{ return leavesCount(root); }
template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
{
cout<<\"\ \\tDebug: The top element is: \" << p->info << endl;
if (p->llink != NULL)
{
cout << \"Old leafCnt = \" << leafCnt << endl;
leafCnt += leavesCount(p->llink);
cout << \"New leafCnt = \" << leafCnt << endl;
}
else
{
cout << \"p->llink == NULL\" << endl;
}
if (p->rlink != NULL)
{
cout << \"Old leafCnt = \" << leafCnt << endl;
leafCnt += leavesCount(p->rlink);
cout << \"New leafCnt = \" << leafCnt << endl;
}
else {
cout << \"p->rlink == NULL\" << endl;
}
return leafCnt;
}
Write the definition of the function, nodeCount, that returns the number of nodes in the binary tree.
SOLN:------>
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.
preorder(p);
treemirror(p);
preorder(p);
}
if (p==NULL)
return;
else
{
nodeType<elemType> *temp;
mirror(p->lLink);
mirror(p->rLink);
temp = p->lLink;
p->lLink =p->rLink;
p->rLink= temp;
}
}
Write a program to test your new functions. Use the data provided to build your binary search tree (-999 is the sentinel): Example Data: 65 55 22 44 61 19 90 10 78 52 -999
int main()
int totalLeafNodes=leavescount(root);
