#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left,* right;
};
// Basic Functions...
struct node* insert(struct node* troot,int x);
struct node* deletenode(struct node* troot,int x);
struct node* findmin(struct node* troot);
int search(struct node* troot,int x);
// Basic display..
void predisplay(struct node* troot);
void indisplay(struct node* troot);
void postdisplay(struct node* troot);
void main()
{
struct node* root=NULL;
int n,a,i,val;
int breakcondition=0;
printf("\nChoice: \n1) Insert a node.. \n2) Delete a node.. \n3) Search for a node.. \n4) Display as Per Pre-order traversal.. \n5) Display as Per In-order traversal.. \n6) Display as Per Post-order traversal.. \n7)Stop ");
int ch;
while(1){
printf("\nEnter your choice..");
scanf("%d",&ch);
switch(ch){
case 1:{
printf("\nEnter any element to be inserted..");
scanf("%d",&val);
root=insert(root,val);
break;
}
case 2:{
printf("\nEnter the element to be deleted..");
scanf("%d",&val);
root=deletenode(root,val);
break;
}
case 3:{
printf("\nEnter the element to be searched..");
scanf("%d",&val);
if(search(root,val)){
printf("\nThe element is found..");
}
else{
printf("\nThe element is not found..");
}
break;
}
case 4:{
if(root==NULL){
printf("\nThe list is empty..");
break;
}
printf("\nThe tree displayed as per pre order traversal is..");
predisplay(root);
break;
}
case 5:{
if(root==NULL){
printf("\nThe list is empty..");
break;
}
printf("\nThe tree displayed as per in order traversal is..");
indisplay(root);
break;
}
case 6:{
if(root==NULL){
printf("\nThe list is empty..");
break;
}
printf("\nThe tree displayed as per post order traversal is..");
postdisplay(root);
break;
}
case 7:{
breakcondition=1;
break;
}
}
if(breakcondition==1){
break;
}
}
}
struct node* insert(struct node* troot,int x)
{
if(troot==NULL){
struct node* temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->left=temp->right=NULL;
troot=temp;
}
else if(x<troot->data){
troot->left=insert(troot->left,x);
}
else if(x>troot->data){
troot->right=insert(troot->right,x);
}
else{
printf("\nThe element is already present..");
}
return troot;
}
struct node* deletenode(struct node* troot,int x)
{
if(troot==NULL){
return troot;
}
else if(x<troot->data){
troot->left=deletenode(troot->left,x);
}
else if(x>troot->data){
troot->right=deletenode(troot->right,x);
}
else{
if(troot->right==NULL && troot->left==NULL){
free(troot);
troot=NULL;
}
else if(troot->left==NULL){
struct node* temp=troot;
troot=troot->right;
free(temp);
}
else if(troot->right==NULL){
struct node* temp=troot;
troot=troot->left;
free(temp);
return troot;
}
else{
struct node* temp=findmin(troot->right);
troot->data=temp->data;
troot->right=deletenode(troot->right,temp->data);
}
return troot;
}
}
struct node* findmin(struct node* troot)
{
if(troot->left==NULL)
return troot;
else
return findmin(troot->left);
}
int search(struct node* troot,int x)
{
if(troot==NULL)return 0;
else if (troot->data==x)return 1;
else if(x<=troot->data)return search(troot->left,x);
else return search(troot->right,x);
}
void predisplay(struct node* troot)
{
if(troot==NULL)
return;
printf("%d ",troot->data);
predisplay(troot->left);
predisplay(troot->right);
}
void indisplay(struct node* troot)
{
if(troot==NULL)
return;
indisplay(troot->left);
printf("%d ",troot->data);
indisplay(troot->right);
}
void postdisplay(struct node* troot)
{
if(troot==NULL)
return;
postdisplay(troot->left);
postdisplay(troot->right);
printf("%d ",troot->data);
}
#include<stdlib.h>
struct node
{
int data;
struct node* left,* right;
};
// Basic Functions...
struct node* insert(struct node* troot,int x);
struct node* deletenode(struct node* troot,int x);
struct node* findmin(struct node* troot);
int search(struct node* troot,int x);
// Basic display..
void predisplay(struct node* troot);
void indisplay(struct node* troot);
void postdisplay(struct node* troot);
void main()
{
struct node* root=NULL;
int n,a,i,val;
int breakcondition=0;
printf("\nChoice: \n1) Insert a node.. \n2) Delete a node.. \n3) Search for a node.. \n4) Display as Per Pre-order traversal.. \n5) Display as Per In-order traversal.. \n6) Display as Per Post-order traversal.. \n7)Stop ");
int ch;
while(1){
printf("\nEnter your choice..");
scanf("%d",&ch);
switch(ch){
case 1:{
printf("\nEnter any element to be inserted..");
scanf("%d",&val);
root=insert(root,val);
break;
}
case 2:{
printf("\nEnter the element to be deleted..");
scanf("%d",&val);
root=deletenode(root,val);
break;
}
case 3:{
printf("\nEnter the element to be searched..");
scanf("%d",&val);
if(search(root,val)){
printf("\nThe element is found..");
}
else{
printf("\nThe element is not found..");
}
break;
}
case 4:{
if(root==NULL){
printf("\nThe list is empty..");
break;
}
printf("\nThe tree displayed as per pre order traversal is..");
predisplay(root);
break;
}
case 5:{
if(root==NULL){
printf("\nThe list is empty..");
break;
}
printf("\nThe tree displayed as per in order traversal is..");
indisplay(root);
break;
}
case 6:{
if(root==NULL){
printf("\nThe list is empty..");
break;
}
printf("\nThe tree displayed as per post order traversal is..");
postdisplay(root);
break;
}
case 7:{
breakcondition=1;
break;
}
}
if(breakcondition==1){
break;
}
}
}
struct node* insert(struct node* troot,int x)
{
if(troot==NULL){
struct node* temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->left=temp->right=NULL;
troot=temp;
}
else if(x<troot->data){
troot->left=insert(troot->left,x);
}
else if(x>troot->data){
troot->right=insert(troot->right,x);
}
else{
printf("\nThe element is already present..");
}
return troot;
}
struct node* deletenode(struct node* troot,int x)
{
if(troot==NULL){
return troot;
}
else if(x<troot->data){
troot->left=deletenode(troot->left,x);
}
else if(x>troot->data){
troot->right=deletenode(troot->right,x);
}
else{
if(troot->right==NULL && troot->left==NULL){
free(troot);
troot=NULL;
}
else if(troot->left==NULL){
struct node* temp=troot;
troot=troot->right;
free(temp);
}
else if(troot->right==NULL){
struct node* temp=troot;
troot=troot->left;
free(temp);
return troot;
}
else{
struct node* temp=findmin(troot->right);
troot->data=temp->data;
troot->right=deletenode(troot->right,temp->data);
}
return troot;
}
}
struct node* findmin(struct node* troot)
{
if(troot->left==NULL)
return troot;
else
return findmin(troot->left);
}
int search(struct node* troot,int x)
{
if(troot==NULL)return 0;
else if (troot->data==x)return 1;
else if(x<=troot->data)return search(troot->left,x);
else return search(troot->right,x);
}
void predisplay(struct node* troot)
{
if(troot==NULL)
return;
printf("%d ",troot->data);
predisplay(troot->left);
predisplay(troot->right);
}
void indisplay(struct node* troot)
{
if(troot==NULL)
return;
indisplay(troot->left);
printf("%d ",troot->data);
indisplay(troot->right);
}
void postdisplay(struct node* troot)
{
if(troot==NULL)
return;
postdisplay(troot->left);
postdisplay(troot->right);
printf("%d ",troot->data);
}
No comments:
Post a Comment