C++ program to remove duplicate elements from the binary search tree
Description:
This Program is to find the duplicate element and delete from the binary search tree.For example:
Input tree : 4,4,5,6,8,7
Output :
Element after deleting duplicate elements are : 5 6 7 8
Program :
//C++ program to remove duplicate elements from the binary search tree
using namespace std;
// tree nod
struct Node
{
int data;
int key ,count;
Node *left, *right;
};
// returns a new tree Node
Node* newNode(int data)
{
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->key = data;
temp->left = temp->right = NULL;
temp->count = 1;
return temp;
}
// A function to create binary search tree.
Node* Tree(Node* temp, int key )
{
// If the tree is empty, return a new node
if (temp == NULL)
return newNode(key);
if (key == temp->key)
{
(temp->count)++;
return temp;
}
// Otherwise, recur down the tree
if (key < temp->key)
temp->left = Tree(temp->left, key);
else
temp->right = Tree(temp->right, key);
//return the (unchanged) node pointer
return temp;
}
//function to delete the duplicate element
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);
}
return root;
}
//function to display all the element present in the binary search tree and call Delete()
void display(struct Node* root)
{
if (root != NULL)
{
display(root->left);
if(root->count>1)
{
Delete(root,root->key);
}
else
cout<<root->key<<" ";
display(root->right);
}
}
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<<"\nElement after deleting duplicate elements are : " ;
display(root);
return 0;
}
Comments