Homework SourseDevelop a java BST implementation using array and genics for
Develop a java BST implementation using array and genics for the following methods isempty,size,put,get,findmax,findmin,ceil,floor,delete,deletemax,deletemin,inorder,postorder, preorder,levelorder,contains,kthsmallestelemnt,kthlargestelement,rank,isbst .
for the explanation of this methods please refer to the following url :http://algs4.cs.princeton.edu/32bst/
Please give solution as soon as possible.
Solution
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
struct treeNode
{
int data;
treeNode *left;
treeNode *right;
};
treeNode* FindMin(treeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
if(node->left) /* Go to the left sub tree to find the min element */
return FindMin(node->left);
else
return node;
}
treeNode* FindMax(treeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
if(node->right) /* Go to the left sub tree to find the min element */
return(FindMax(node->right));
else
return node;
}
treeNode *Insert(treeNode *node,int data)
{
if(node==NULL)
{
treeNode *temp;
temp=new treeNode;
//temp = (treeNode *)malloc(sizeof(treeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right,data);
}
else if(data < (node->data))
{
node->left = Insert(node->left,data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
}
treeNode * Delet(treeNode *node, int data)
{
treeNode *temp;
if(node==NULL)
{
cout<<\"Element Not Found\";
}
else if(data < node->data)
{
node->left = Delet(node->left, data);
}
else if(data > node->data)
{
node->right = Delet(node->right, data);
}
else
{
/* Now We can delete this node and replace with either minimum element
in the right sub tree or maximum element in the left subtree */
if(node->right && node->left)
{
/* Here we will replace with minimum element in the right sub tree */
temp = FindMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = Delet(node->right,temp->data);
}
else
{
/* If there is only one or zero children then we can directly
remove it from the tree and connect its parent to its child */
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp); /* temp is longer required */
}
}
return node;
}
treeNode * Find(treeNode *node, int data)
{
if(node==NULL)
{
/* Element is not found */
return NULL;
}
if(data > node->data)
{
/* Search in the right sub tree. */
return Find(node->right,data);
}
else if(data < node->data)
{
/* Search in the left sub tree. */
return Find(node->left,data);
}
else
{
/* Element Found */
return node;
}
}
void Inorder(treeNode *node)
{
if(node==NULL)
{
return;
}
Inorder(node->left);
cout<<node->data<<\" \";
Inorder(node->right);
}
void Preorder(treeNode *node)
{
if(node==NULL)
{
return;
}
cout<<node->data<<\" \";
Preorder(node->left);
Preorder(node->right);
}
void Postorder(treeNode *node)
{
if(node==NULL)
{
return;
}
Postorder(node->left);
Postorder(node->right);
cout<<node->data<<\" \";
}
int main()
{
treeNode *root = NULL,*temp;
int ch;
//clrscr();
while(1)
{
cout<<\"\ 1.Insert\ 2.Delete\ 3.Inorder\ 4.Preorder\ 5.Postorder\ 6.FindMin\ 7.FindMax\ 8.Search\ 9.Exit\ \";
cout<<\"Enter ur choice:\";
cin>>ch;
switch(ch)
{
case 1:
cout<<\"\ Enter element to be insert:\";
cin>>ch;
root = Insert(root, ch);
cout<<\"\ Elements in BST are:\";
Inorder(root);
break;
case 2:
cout<<\"\ Enter element to be deleted:\";
cin>>ch;
root = Delet(root,ch);
cout<<\"\ After deletion elements in BST are:\";
Inorder(root);
break;
case 3:
cout<<\"\ Inorder Travesals is:\";
Inorder(root);
break;
case 4:
cout<<\"\ Preorder Traversals is:\";
Preorder(root);
break;
case 5:
cout<<\"\ Postorder Traversals is:\";
Postorder(root);
break;
case 6:
temp = FindMin(root);
cout<<\"\ Minimum element is :\"<<temp->data;
break;
case 7:
temp = FindMax(root);
cout<<\"\ Maximum element is :\"<<temp->data;
break;
case 8:
cout<<\"\ Enter element to be searched:\";
cin>>ch;
temp = Find(root,ch);
if(temp==NULL)
{
cout<<\"Element is not foundn\";
}
else
{
cout<<\"Element \"<<temp->data<<\" is Found\ \";
}
break;
case 9:
exit(0);
break;
default:
cout<<\"\ Enter correct choice:\";
break;
}
}
return 0;
}
