C++ : Binary Trees
1. Write the definition of the function,nodeCount, that returns the number of nodes in thebinary tree. Add this function to the class binaryTreeType andcreate a program to test this function.
2. the definition of the function, leavesCount,that takes as a parameter a pointer to the root node of a binarytree and returns the number of leaves in a binary tree. Add thisfunction to the class binaryTreeType and create a program to testthis function.

Below are binaryTreeType and binarySearchTree classes. The test code will need to work for thebinarySearchTree class since binaryTreeType is an abstractclass.

//Header File Binary Search Tree
//binaryTree.h

#ifndef H_binaryTree
#define H_binaryTree

#include

using namespace std;

//Definition of the Node
template
struct nodeType
{
elemType info;
nodeType *lLink;
nodeType *rLink;
};

//Definition of the class
template
class binaryTreeType
{
public:
const binaryTreeType&operator=
(constbinaryTreeType&);
//Overload the assignment operator.

bool isEmpty() const;
//Function to determine whether the binary treeis empty.
//Postcondition: Returns true if the binary treeis empty;
// otherwise, returns false.

void inorderTraversal() const;
//Function to do an inorder traversal of thebinary tree.
//Postcondition: Nodes are printed in inordersequence.

void preorderTraversal() const;
//Function to do a preorder traversal of thebinary tree.
//Postcondition: Nodes are printed in preordersequence.

void postorderTraversal() const;
//Function to do a postorder traversal of thebinary tree.
//Postcondition: Nodes are printed in postordersequence.

int treeHeight() const;
//Function to determine the height of a binarytree.
//Postcondition: Returns the height of thebinary tree.

int treeNodeCount() const;
//Function to determine the number of nodes ina
//binary tree.
//Postcondition: Returns the number of nodes inthe
// binary tree.

int treeLeavesCount() const;
//Function to determine the number of leaves ina
//binary tree.
//Postcondition: Returns the number of leaves inthe
// binary tree.

void destroyTree();
//Function to destroy the binary tree.
//Postcondition: Memory space occupied by eachnode
// is deallocated.
// root = nullptr;

virtual bool search(const elemType&searchItem) const = 0;
//Function to determine if searchItem is in thebinary
//tree.
//Postcondition: Returns true if searchItem isfound in
// the binary tree; otherwise, returns
// false.

virtual void insert(const elemType&insertItem) = 0;
//Function to insert insertItem in the binarytree.
//Postcondition: If there is no node in thebinary 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 binarytree
//Postcondition: If a node with the same infoas
// 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(constbinaryTreeType& otherTree);
//Copy constructor

binaryTreeType();
//Default constructor

~binaryTreeType();
//Destructor

protected:
nodeType *root;

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

void destroy(nodeType*&p);
//Function to destroy the binary tree to which ppoints.
//Postcondition: Memory space occupied by eachnode, in
// the binary tree to which p points, is
// deallocated.
// p = nullptr;

void inorder(nodeType *p)const;
//Function to do an inorder traversal of thebinary
//tree to which p points.
//Postcondition: Nodes of the binary tree, towhich p
// points, are printed in inorder sequence.

void preorder(nodeType *p)const;
//Function to do a preorder traversal of thebinary
//tree to which p points.
//Postcondition: Nodes of the binary tree, towhich p
// points, are printed in preorder
// sequence.

void postorder(nodeType *p)const;
//Function to do a postorder traversal of thebinary
//tree to which p points.
//Postcondition: Nodes of the binary tree, towhich p
// points, are printed in postorder
// sequence.

int height(nodeType *p)const;
//Function to determine the height of the binarytree
//to which p points.
//Postcondition: Height of the binary tree towhich
// p points is returned.

int max(int x, int y) const;
//Function to determine the larger of x andy.
//Postcondition: Returns the larger of x andy.

int nodeCount(nodeType *p)const;
//Function to determine the number of nodesin
//the binary tree to which p points.
//Postcondition: The number of nodes in thebinary
// tree to which p points is returned.

int leavesCount(nodeType *p)const;
//Function to determine the number of leaves in
//the binary tree to which p points
//Postcondition: The number of leaves in thebinary
// tree to which p points is returned.
};

//Definition of member functions

template
binaryTreeType::binaryTreeType()
{
root = nullptr;
}

template
bool binaryTreeType::isEmpty() const
{
return (root == nullptr);
}

template
void binaryTreeType::inorderTraversal() const
{
inorder(root);
}

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
(nodeType* &copiedTreeRoot,
nodeType* otherTreeRoot)
{
if (otherTreeRoot == nullptr)
copiedTreeRoot =nullptr;
else
{
copiedTreeRoot = newnodeType;
copiedTreeRoot->info =otherTreeRoot->info;
copyTree(copiedTreeRoot->lLink,otherTreeRoot->lLink);
copyTree(copiedTreeRoot->rLink,otherTreeRoot->rLink);
}
} //end copyTree

template
void binaryTreeType::inorder
(nodeType *p) const
{
if (p != nullptr)
{
inorder(p->lLink);
cout << p->info<< " ";
inorder(p->rLink);
}
}

template
void binaryTreeType::preorder
(nodeType *p) const
{
if (p != nullptr)
{
cout << p->info<< " ";
preorder(p->lLink);
preorder(p->rLink);
}
}

template
void binaryTreeType::postorder
(nodeType *p) const
{
if (p != nullptr)
{
postorder(p->lLink);
postorder(p->rLink);
cout << p->info<< " ";
}
}

//Overload the assignment operator
template
const binaryTreeType&binaryTreeType::
operator=(const binaryTreeType&otherTree)
{
if (this != &otherTree) //avoidself-copy
{
if (root != nullptr) //if the binary tree is not empty,
//destroy the binary tree
destroy(root);

if (otherTree.root ==nullptr) //otherTree is empty
root =nullptr;
else
copyTree(root, otherTree.root);
}//end else

return *this;
}

template
void binaryTreeType::destroy(nodeType*&p)
{
if (p != nullptr)
{
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = nullptr;
}
}

template
void binaryTreeType::destroyTree()
{
destroy(root);
}

//copy constructor
template
binaryTreeType::binaryTreeType
(const binaryTreeType& otherTree)
{
if (otherTree.root == nullptr) //otherTree isempty
root = nullptr;
else
copyTree(root,otherTree.root);
}

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

template
int binaryTreeType::height
(nodeType *p) const
{
if (p == nullptr)
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
intbinaryTreeType::nodeCount(nodeType*p) const
{
//implement
}

template
intbinaryTreeType::leavesCount(nodeType*p) const
{
//implement
}

#endif

//Header File Binary Search Tree
//binarySearchTree.h

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include
#include "binaryTree.h"

using namespace std;

template
class bSearchTreeType : public binaryTreeType
{
public:
bool search(const elemType& searchItem)const;
//Function to determine if searchItem is in thebinary
//search tree.
//Postcondition: Returns true if searchItem isfound in
// the binary search tree; otherwise,
// returns false.

void insert(const elemType&insertItem);
//Function to insert insertItem in the binarysearch tree.
//Postcondition: If there is no node in thebinary 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 binarysearch tree
//Postcondition: If a node with the same info asdeleteItem
// 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*&p);
//Function to delete the node to which p pointsis
//deleted from the binary search tree.
//Postcondition: The node to which p points isdeleted
// from the binary search tree.
};

template
bool bSearchTreeType::search(const elemType&searchItem) const
{
nodeType *current;
bool found = false;

if (root == nullptr)
cout << "Cannot searchan empty tree." << endl;
else
{
current = root;

while (current != nullptr&& !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
void bSearchTreeType::insert(const elemType&insertItem)
{
nodeType *current; //pointer totraverse the tree
nodeType *trailCurrent;//pointer behind current
nodeType *newNode; //pointer to create the node

newNode = new nodeType;
newNode->info = insertItem;
newNode->lLink = nullptr;
newNode->rLink = nullptr;

if (root == nullptr)
root = newNode;
else
{
current = root;

while (current !=nullptr)
{
trailCurrent = current;

if(current->info == insertItem)
{
cout << "The item to be inserted isalready ";
cout << "in the tree -- duplicatesare not "
<< "allowed."<< endl;

delete newNode;

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
void bSearchTreeType::deleteNode(constelemType& deleteItem)
{
nodeType *current; //pointer totraverse the tree
nodeType *trailCurrent;//pointer behind current
bool found = false;

if (root == nullptr)
cout << "Cannot deletefrom an empty tree." << endl;
else
{
current = root;
trailCurrent = root;

while (current != nullptr&& !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 ==nullptr)
cout<< "The item to be deleted is not in the tree."
< else if (found)
{
if(current == root)
deleteFromTree(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."
< }
} //end deleteNode

template
voidbSearchTreeType::deleteFromTree(nodeType*&p)
{
nodeType *current; //pointer totraverse the tree
nodeType *trailCurrent; //pointer behind current
nodeType *temp; //pointer to delete the node

if (p == nullptr)
cout << "Error: Thenode to be deleted does not exist."
<< endl;
else if (p->lLink == nullptr &&p->rLink == nullptr)
{
temp = p;
p = nullptr;
delete temp;
}
else if (p->lLink == nullptr)
{
temp = p;
p = temp->rLink;
delete temp;
}
else if (p->rLink == nullptr)
{
temp = p;
p = temp->lLink;
delete temp;
}
else
{
current = p->lLink;
trailCurrent = nullptr;

while (current->rLink!= nullptr)
{
trailCurrent = current;
current =current->rLink;
}//end while

p->info =current->info;

if (trailCurrent ==nullptr) //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