#include<iostream>
using namespace std;
class bst
{
struct node
{
int info;
struct node *left,*right;
}*root;
public:
bst()
{
root=NULL;
}
void create(int ele);
void inorder(node *root);
void preorder(node *root);
void postorder(node *root);
void del(int ele);
void display();
};
void bst::create(int ele)
{
node *temp=new node;
node *p=root,*q;
temp->info=ele;
temp->left=temp->right=NULL;
if(root==NULL)
{
root=temp;
return;
}
while(p!=NULL)
{
q=p;
if(p->info==ele)
{
cout<<"\nNode already exists";
return;
}
if(p->info>ele)
p=p->left;
else
p=p->right;
}
if(q->info>ele)
q->left=temp;
else
q->right=temp;
}
void bst::inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<<root->info<<" ";
inorder(root->right);
}
}
void bst::preorder(node *root)
{
if(root!=NULL)
{
cout<<root->info<<" ";
inorder(root->left);
inorder(root->right);
}
}
void bst::postorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
inorder(root->right);
cout<<root->info<<" ";
}
}
void bst::display()
{
cout<<"\nInorder\n";
inorder(root);
cout<<"\npreorder\n";
preorder(root);
cout<<"\npostorder\n";
postorder(root);
}
void bst::del(int ele)
{
node *p=root,*q=root;
if(root==NULL)
{
cout<<"\nEmpty tree\n";
return;
}
while(p!=NULL && p->info!=ele)
{
q=p;
if(p->info<ele)
p=p->right;
else
p=p->left;
}
if(p==NULL)
{
cout<<"\nElement not found\n";
return;
}
if(p->left==NULL && p->right==NULL) //Leaf node
{
if(q->info<ele)
q->right=NULL;
else
q->left=NULL;
delete(p);
}
if(p->left==NULL)
{
}
}
main()
{
bst b1;
int i,ele;
b1.create(50);
b1.create(30);
b1.create(40);
b1.create(20);
b1.create(100);
b1.create(120);
b1.create(70);
b1.display();
for(i=0;i<7;i++)
{
cout<<"\nEnter a number to delete=";
cin>>ele;
b1.del(ele);
cout<<"\n\nAfter deleting "<<ele<<"\n";
b1.display();
}
}
using namespace std;
class bst
{
struct node
{
int info;
struct node *left,*right;
}*root;
public:
bst()
{
root=NULL;
}
void create(int ele);
void inorder(node *root);
void preorder(node *root);
void postorder(node *root);
void del(int ele);
void display();
};
void bst::create(int ele)
{
node *temp=new node;
node *p=root,*q;
temp->info=ele;
temp->left=temp->right=NULL;
if(root==NULL)
{
root=temp;
return;
}
while(p!=NULL)
{
q=p;
if(p->info==ele)
{
cout<<"\nNode already exists";
return;
}
if(p->info>ele)
p=p->left;
else
p=p->right;
}
if(q->info>ele)
q->left=temp;
else
q->right=temp;
}
void bst::inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<<root->info<<" ";
inorder(root->right);
}
}
void bst::preorder(node *root)
{
if(root!=NULL)
{
cout<<root->info<<" ";
inorder(root->left);
inorder(root->right);
}
}
void bst::postorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
inorder(root->right);
cout<<root->info<<" ";
}
}
void bst::display()
{
cout<<"\nInorder\n";
inorder(root);
cout<<"\npreorder\n";
preorder(root);
cout<<"\npostorder\n";
postorder(root);
}
void bst::del(int ele)
{
node *p=root,*q=root;
if(root==NULL)
{
cout<<"\nEmpty tree\n";
return;
}
while(p!=NULL && p->info!=ele)
{
q=p;
if(p->info<ele)
p=p->right;
else
p=p->left;
}
if(p==NULL)
{
cout<<"\nElement not found\n";
return;
}
if(p->left==NULL && p->right==NULL) //Leaf node
{
if(q->info<ele)
q->right=NULL;
else
q->left=NULL;
delete(p);
}
if(p->left==NULL)
{
}
}
main()
{
bst b1;
int i,ele;
b1.create(50);
b1.create(30);
b1.create(40);
b1.create(20);
b1.create(100);
b1.create(120);
b1.create(70);
b1.display();
for(i=0;i<7;i++)
{
cout<<"\nEnter a number to delete=";
cin>>ele;
b1.del(ele);
cout<<"\n\nAfter deleting "<<ele<<"\n";
b1.display();
}
}
No comments:
Post a Comment