This Program is to find the number entered by the user in the binary tree, if the element is present then delete the element from that position, and if the element is not found it will display 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 tree is : 5
Output will be :
Element deleted
After deleting array is : 4,7,8,9
Program :
//C++ program to delete an element into binary tree
#include<bits/stdc++.h>usingnamespacestd;
// tree nodestructNode
{int data;
structNode *left, *right;
};
// returns a new tree Nodestruct Node* newNode(int data){
structNode* temp = newNode();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
};
//function to display all the element present in the binary treevoiddisplay(struct Node* root){
if (root != NULL)
{
display(root->left);
cout<<root->data<<" ";
display(root->right);
}
}
voiddeletnode(struct Node *root,struct Node *node){
queue<struct Node*> q;
q.push(root);
// Do level order traversal until last nodestructNode* temp;while(!q.empty())
{
temp = q.front();
q.pop();
if (temp->right)
{
if (temp->right == node)
{
temp->right = NULL;
delete(node);
return;
}
else
q.push(temp->right);
}
if (temp->left)
{
if (temp->left == node)
{
temp->left=NULL;
delete(node);
return;
}
else
q.push(temp->left);
}
}
}
// function to delete element in binary treevoiddeletion(struct Node* root, int data){
queue<struct Node*> q;
q.push(root);
structNode *temp;structNode *data_node = NULL;// Do level order traversal to find deepestwhile (!q.empty())
{
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
int x = temp->data;
deletnode(root, temp);
data_node->data = x;
}
intmain(){
int n;
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(5);
root->right->right = newNode(6);
root->left->left = newNode(4);
root->left->left->left = newNode(7);
root->left->left->right = newNode(8);
root->right->left->left = newNode(9);
root->right->right->left = newNode(10);
root->left->left->left->left = newNode(11);
root->left->left->right->left = newNode(12);
root->left->left->right->right = newNode(13);
cout<<"\nEnter the Element to be deleted: ";
cin>>n;
deletion(root,n);
cout<<"\nElement Deleted"<<endl;
cout<<"\nAfter Deletion: "<<endl;
cout<<"Elements are: ";
display(root);
cout<<endl;
return0;
}
Comments