C++ program to delete an element into binary search tree
Description:
Program :
This Program is to find the number entered by the user and search it in the binary search tree, if the element is present it will send it's position and delete the element from that position, and if the element is not found it will display element not fond message and will print the list of elements as it is.
For Example:
Input for tree is: 4,5,7,8,9
The entered element to delete from binary search tree is : 5
Output will be :
5 found at position 2
Element deleted
After deleting array is : 4,7,8,9
//C++ program to delete an element into binary search tree
using namespace std;
// tree node
struct Node
{
int data;
Node *left, *right;
};
// returns a new tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A function to create binary search tree.
Node* Tree(Node* root, int data)
{
// Create node using data entered by user.
Node *temp = newNode(data);
Node *temp1 = new Node;
temp1 = root;
// If root is null then the node created.
if(root == NULL)
root = temp;
else
{
// Search the position for the new node to be inserted.
while(temp1 != NULL)
{
if(temp1->data < data )
{
if(temp1->right == NULL)
{
// If current node is NULL then the value will be inserted here and break.
temp1->right = temp;
break;
}
// Shift pointer to the left.
temp1 = temp1->right;
}
else if(temp1->data > data)
{
if(temp1->left == NULL)
{
temp1->left = temp;
break;
}
// Shift pointer to the left.
temp1 = temp1->left;
}
}
}
return root;
}
//function to display all the element present in the binary search tree
void display(struct Node* root)
{
if (root != NULL)
{
display(root->left);
cout<<root->data<<" ";
display(root->right);
}
}
// A function to search item in a binary search tree.
void Search(Node *root, int data)
{
int pos = 0;
Node *temp = new Node;
temp = root;
// Run the loop until temp points to a NULL pointer.
while(temp != NULL)
{
pos++;
if(temp->data == data)
{
cout<<"\nData found at position: "<<pos;
return;
}
// Shift pointer to left child.
else if(temp->data > data)
temp = temp->left;
// Shift pointer to right child.
else
temp = temp->right;
}
cout<<"\n Data not found";
return;
}
//function to find the minimum
Node* Min(Node*root)
{
while(root->left!=NULL)
{
root=root->left;
}
return root;
}
//function to delete the element entered by the user
Node* Delete( Node* root,int value)
{
if(root==NULL)
return root;
else if(value< root->data)
{
root->left= Delete(root->left,value);
}
else if(value> root->data)
{
root->right= Delete(root->right,value);
}
// Node deletion
else
{
// Leaf Node
if(root->left==NULL&&root->right==NULL)
{
delete root;
root=NULL;
return root;
}
//one child
else if(root->left==NULL)
{
struct Node* temp=root;
root=root->right;
delete temp;
return root;
}
else if(root->right==NULL)
{
struct Node* temp=root;
root=root->left;
delete temp;
return root;
}
//child
else
{
struct Node*temp=Min(root->right);
root->data=temp->data;
root->right=Delete(root->right,temp->data);
}
}
return root;
}
int main()
{
char ch;
int n, arr[20],size;
Node *root = new Node;
root = NULL;
cout<<"Enter the size of array : ";
cin>>size;
cout<<"Enter the elements in array : ";
for(int i=0;i<size;i++)
{
cin>>arr[i];
}
// Construct the binary search tree.
for(int i = 0; i < size; i++)
root = Tree(root, arr[i]);
cout<<"\nEnter the Element to be deleted: ";
cin>>n;
Search(root, n);
Delete(root,n);
cout<<"\nElement Deleted"<<endl;
cout<<"\nAfter Deletion: "<<endl;
cout<<"Elements are: ";
display(root);
cout<<endl;
return 0;
}
Comments