# include

# include

using namespace std;

// Node Declaration

struct node

{

int info;

struct node *left;

struct node *right;

}*root;

// Class Declaration

class BST

{

public:

void find(int, node **, node **);

void insert(node*, node*);

void del(int);

void case_a(node *,node *);

void case_b(node *,node *);

void case_c(node *,node *);

void preorder(node *);

void inorder(node *);

void postorder(node *);

void display(node *, int);

BST()

{

root = NULL;

}

};

//main function

int main()

{

int choice, num;

BST bst;

node *temp;

while (1)

{

cout

cout

cout

cout

cout

cout

cout

cout

cout

cout

cout

cin>>choice;

switch(choice)

{

case 1:

temp = new node;

cout

cin>>temp->info;

bst.insert(root, temp);

case 2:

if (root == NULL)

{

cout

continue;

}

cout

cin>>num;

bst.del(num);

break;

case 3:

cout

bst.inorder(root);

cout

break;

case 4:

cout

bst.preorder(root);

cout

break;

case 5:

cout

bst.postorder(root);

cout

break;

case 6:

cout

bst.display(root,1);

cout

break;

case 7:

exit(1);

default:

cout

}

}

}

// Find Element in the Tree

void BST::find(int item, node **par, node **loc)

{

node *ptr, *ptrsave;

if (root == NULL)

{

*loc = NULL;

*par = NULL;

return;

}

if (item == root->info)

{

*loc = root;

*par = NULL;

return;

}

if (item info)

ptr = root->left;

else

ptr = root->right;

ptrsave = root;

while (ptr != NULL)

{

if (item == ptr->info)

{

*loc = ptr;

*par = ptrsave;

return;

}

ptrsave = ptr;

if (item info)

ptr = ptr->left;

else

ptr = ptr->right;

}

*loc = NULL;

*par = ptrsave;

}

//Inserting Element into the Tree

void BST::insert(node *tree, node *newnode)

{

if (root == NULL)

{

root = new node;

root->info = newnode->info;

root->left = NULL;

root->right = NULL;

cout

return;

}

if (tree->info == newnode->info)

{

cout

return;

}

if (tree->info > newnode->info)

{

if (tree->left != NULL)

{

insert(tree->left, newnode);

}

else

{

tree->left = newnode;

(tree->left)->left = NULL;

(tree->left)->right = NULL;

cout

return;

}

}

else

{

if (tree->right != NULL)

{

insert(tree->right, newnode);

}

else

{

tree->right = newnode;

(tree->right)->left = NULL;

(tree->right)->right = NULL;

cout

return;

}

}

}

//Delete Element from the tree

void BST::del(int item)

{

node *parent, *location;

if (root == NULL)

{

cout

return;

}

find(item, &parent, &location);

if (location == NULL)

{

cout

return;

}

if (location->left == NULL && location->right == NULL)

case_a(parent, location);

if (location->left != NULL && location->right == NULL)

case_b(parent, location);

if (location->left == NULL && location->right != NULL)

case_b(parent, location);

if (location->left != NULL && location->right != NULL)

case_c(parent, location);

free(location);

}

//Case a

void BST::case_a(node *par, node *loc )

{

if (par == NULL)

{

root = NULL;

}

else

{

if (loc == par->left)

par->left = NULL;

else

par->right = NULL;

}

}

// Case _b

void BST::case_b(node *par, node *loc)

{

node *child;

if (loc->left != NULL)

child = loc->left;

else

child = loc->right;

if (par == NULL)

{

root = child;

}

else

{

if (loc == par->left)

par->left = child;

else

par->right = child;

}

}

//Case_c

void BST::case_c(node *par, node *loc)

{

node *ptr, *ptrsave, *suc, *parsuc;

ptrsave = loc;

ptr = loc->right;

while (ptr->left != NULL)

{

ptrsave = ptr;

ptr = ptr->left;

}

suc = ptr;

parsuc = ptrsave;

if (suc->left == NULL && suc->right == NULL)

case_a(parsuc, suc);

else

case_b(parsuc, suc);

if (par == NULL)

{

root = suc;

}

else

{

if (loc == par->left)

par->left = suc;

else

par->right = suc;

}

suc->left = loc->left;

suc->right = loc->right;

}

// Pre Order Traversal

void BST::preorder(node *ptr)

{

if (root == NULL)

{

cout

return;

}

if (ptr != NULL)

{

coutinfo

preorder(ptr->left);

preorder(ptr->right);

}

}

// In Order Traversal

void BST::inorder(node *ptr)

{

if (root == NULL)

{

cout

return;

}

if (ptr != NULL)

{

inorder(ptr->left);

coutinfo

inorder(ptr->right);

}

}

// Postorder Traversal

void BST::postorder(node *ptr)

{

if (root == NULL)

{

cout

return;

}

if (ptr != NULL)

{

postorder(ptr->left);

postorder(ptr->right);

coutinfo

}

}

// Display Tree Structure

void BST::display(node *ptr, int level)

{

int i;

if (ptr != NULL)

{

display(ptr->right, level+1);

cout

if (ptr == root)

cout: ";

else

{

for (i = 0;i

cout

}

coutinfo;

display(ptr->left, level+1);

}

}

I need the following source code to be edited. It is all one file that compiles and runs correctly, but I need the code in separate files so it is reusable. I need main to be in its own file and I need the BinaryTree class to be converted to a template class (as in preface with template for example) in its own header file. Pase adjust arguments, variables, and class qualifiers that were used originally to conform to template specification. If it helps to know, the original program was supposed to create a class (BinaryTree) template that will creat a binary tree that can hold values of any data type. The class should provide functions to insert a node, a function to delete a node, functions to display the tree In Order, Pre order and Post order. It should also provide a member function to search the tree for a value. The class should provide a function that counts the number of nodes in the tree, a function to count the number leaf nodes in the tree, and a function that determines the height of the tree. The height of a tree is the number of levels the tree has. write a program that shows all these functions work Edit the following code to comply with the request from the first paragraph above