Homework SourseC Binary Tree Write your own version of a class template tha
C++
Binary Tree
Write your own version of a class template that will create a binary tree that can hold values of any data type. Demonstrate the class with a driver program.
Your program should include:
Node Counter: Write a member function that counts and returns the number of nodes in the tree.
Leaf Counter Write a member function that counts and returns the number of leaf nodes in the tree.
Tree Height Write a member function that returns the height of the tree. The height of the tree is the number of levels it contains. For example, the tree shown in Figure 20-10 has three levels.
Tree Width: Write a member function that returns the width of the tree. The width of the tree is the largest number of nodes in the same level.
Solution
#include <iostream>
#include \"BinarySearchTree.h\"
using namespace std;
// Default constructor
BinarySearchTree::BinarySearchTree()
{
root = NULL;
return;
}
bool BinarySearchTree::IsEmpty()
{
return(root ==NULL);
}
void BinarySearchTree::Insert(TreeNode* &node, int item)
{
if (node == NULL)
{
node = new TreeNode;
node -> right = NULL;
node -> left = NULL;
node -> info = item;
}
else if (item < (node -> info))
Insert(node -> left, item);
else
Insert(node -> right, item);
}
TreeNode *BinarySearchTree::SearchTree(int info)
{
int valueInTree = false;
TreeNode *temp;
temp = root;
while((temp != NULL) && (temp ->info != info))
{
//Search is before
if(info < temp->info)
temp = temp -> left;
//Search is after
else
temp = temp-> right;
}
//Search Not found
if(temp ==NULL)
return temp;
}
void BinarySearchTree::treeDelete(int info)
{
TreeNode *back;
TreeNode *temp;
TreeNode *deleteParent;
TreeNode *deleteNode;
temp = root;
back = NULL;
//Locates the Node to be deleted
while((temp != NULL) && (info != temp->info))
{
back = temp;
if(info < temp->info)
temp = temp->left;
else
temp = temp->right;
}
// Deleting the root
if(temp == root)
{
deleteNode = root;
deleteParent = NULL;
}
else
{
deleteNode = temp;
deleteParent = back;
}
Deleting node with no children or one child
if(deleteNode->right == NULL)
{
if(deleteParent == NULL) // If deleting the root
{
root = deleteNode->left;
delete deleteNode;
}
else
{
if(deleteParent->left == deleteNode)
deleteParent->left = deleteNode->left;
else
deleteParent->right = deleteNode->left;
delete deleteNode;
}
}
// There is at least one child
else
{
if(deleteNode->left == NULL) // Only 1 child and it is on the right
{
if(deleteParent == NULL) // If deleting the root
{
root = deleteNode->right;
delete deleteNode;
}
else
{
if(deleteParent->left == deleteNode)
deleteParent->left = deleteNode->right;
else
deleteParent->right = deleteNode->right;
delete deleteNode;
}
}
//Deleting node with two children
else
{
// Find the replacement value. Locate the node
// containing the largest value smaller than the
// key of the node being deleted.
temp = deleteNode->left;
back = deleteNode;
while(temp->right != NULL)
{
back = temp;
temp = temp->right;
}
// Copy the replacement values into the node to be deleted
deleteNode->info = temp->info;
// Remove the replacement node from the tree
if(back == deleteNode)
back->left = temp->left;
else
back->right = temp->left;
delete temp;
}
}
}
void BinarySearchTree::treeInOrder(TreeNode *root)
{
if(!root == NULL)
{
treeInOrder(root -> left);
cout << root -> info << \" \";
treeInOrder(root -> right);
}
}
void BinarySearchTree::treePostOrder(TreeNode *root)
{
if(!root == NULL)
{
treePostOrder(root -> left);
treePostOrder(root -> right);
cout << root -> info << \" \" ;
}
}
void BinarySearchTree::treePreOrder(TreeNode *root)
{
if(!root == NULL)
{
cout << root -> info << \" \";
treePreOrder(root -> left);
treePreOrder(root -> right);
}
}
