C++ : Binary Trees 1. Write the definition of the function, nodeCount , that returns the number
Question:
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
nodeType
};
//Definition of the class
template
class binaryTreeType
{
public:
const binaryTreeType
(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
//Copy constructor
binaryTreeType();
//Default constructor
~binaryTreeType();
//Destructor
protected:
nodeType
private:
void copyTree(nodeType
nodeType
//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
//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
//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
//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
//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
//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
//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
//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
{
root = nullptr;
}
template
bool binaryTreeType
{
return (root == nullptr);
}
template
void binaryTreeType
{
inorder(root);
}
template
void binaryTreeType
{
preorder(root);
}
template
void binaryTreeType
{
postorder(root);
}
template
int binaryTreeType
{
return height(root);
}
template
int binaryTreeType
{
return nodeCount(root);
}
template
int binaryTreeType
{
return leavesCount(root);
}
template
void binaryTreeType
(nodeType
nodeType
{
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
(nodeType
{
if (p != nullptr)
{
inorder(p->lLink);
cout << p->info<< " ";
inorder(p->rLink);
}
}
template
void binaryTreeType
(nodeType
{
if (p != nullptr)
{
cout << p->info<< " ";
preorder(p->lLink);
preorder(p->rLink);
}
}
template
void binaryTreeType
(nodeType
{
if (p != nullptr)
{
postorder(p->lLink);
postorder(p->rLink);
cout << p->info<< " ";
}
}
//Overload the assignment operator
template
const binaryTreeType
operator=(const binaryTreeType
{
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
{
if (p != nullptr)
{
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = nullptr;
}
}
template
void binaryTreeType
{
destroy(root);
}
//copy constructor
template
binaryTreeType
(const binaryTreeType
{
if (otherTree.root == nullptr) //otherTree isempty
root = nullptr;
else
copyTree(root,otherTree.root);
}
//Destructor
template
binaryTreeType
{
destroy(root);
}
template
int binaryTreeType
(nodeType
{
if (p == nullptr)
return 0;
else
return 1 +max(height(p->lLink), height(p->rLink));
}
template
int binaryTreeType
{
if (x >= y)
return x;
else
return y;
}
template
intbinaryTreeType
{
//implement
}
template
intbinaryTreeType
{
//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
//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
{
nodeType
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
{
nodeType
nodeType
nodeType
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
{
nodeType
nodeType
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."
<
{
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
{
nodeType
nodeType
nodeType
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