BINARY TREE
1. Write a C program to create Binary Tree and
provide insertion and deletion operations and to traverse the tree using
In-order, Preorder and Post order using recursive method.
//PROGRAM STARTS HERE
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *r;
struct node *l;
};
typedef struct node *NODE;
NODE create(NODE root,int item)
{
NODE temp,cur,prev,new;
new=malloc(sizeof(NODE));
new->data=item;
new->r=new->l=NULL;
if(root==NULL)
{
return new;
}
prev=NULL;
cur=root;
while(cur!=NULL)
{
prev=cur;
if(item<root->data)
cur=cur->l;
else
cur=cur->r;
}
if(item<prev->data)
prev->l=new;
else
prev->r=new;
return root;
}
NODE minValue(NODE root)
{
NODE cur;
cur=root;
while(cur->l!= NULL)
{
cur=cur->l;
}
return cur;
}
NODE delete (NODE root,int item)
{
NODE temp;
if(root==NULL)
return root;
if(item< root->data)
root->l=delete(root->l,item);
else if(item>root->data)
root->r=delete(root->r,item);
else
{
if(root->l==NULL)
{
temp=root->r;
printf("deleted\n");
free(root);
return temp;
}
else if(root->r==NULL)
{
temp=root->l;
printf("deleted\n");
free(root);
return temp;
}
temp=minValue(root->r);
root->data=temp->data;
root->r=delete(root->r,temp->data);
}
return root;
}
void pre(NODE root)
{
if(root!=NULL)
{
printf("%d
\t",root->data);
pre(root->l);
pre(root->r);
}
}
void in(NODE root)
{
if(root!=NULL)
{
in(root->l);
printf("%d
\t",root->data);
in(root->r);
}
}
void post(NODE root)
{
if(root!=NULL)
{
post(root->l);
post(root->r);
printf("%d
\t",root->data);
}
}
int main()
{
int ch,item;
NODE root=NULL;
while(ch!=6)
{
printf("1.insert\t2.preorder\t3.inorder\t4.postorder\t5.delete\t6.exit\nenter
ur choice\n");
scanf("%d",&ch);
switch(ch)
{
case
1:printf("enter data\t:");
scanf("%d",&item);
root=create(root,item);
break;
case 2:
printf("\npreorder\n");
pre(root);
break;
case 3:
printf("\ninorder\n");
in(root);
break;
case 4:
printf("\npostorde\n");
post(root);
break;
case
5:printf("\nenter ele to be deleted\t");
scanf("%d",&item);
delete(root,item);
break;
default : exit(0);
}
}
}
2. Given a String representing a parentheses-free infix arithmetic
expression, implement a program to place it in a tree in the infix form. Assume
that a variable name is a single letter. Traverse the tree to produce an
equivalent postfix and prefix expression string.
//PROGRAM STARTS HERE
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
struct node{
char info;
struct node *l;
struct node *r;
};
typedef struct node *NODE;
NODE create(char sy)
{
NODE new;
new=malloc(sizeof(NODE));
new->info=sy;
new->r=NULL;
new->l=NULL;
return new;
}
int preced(char item)
{
switch(item)
{
case '-' :
case '+' : return 1;
case '/' :
case '*' : return 2;
case '^' : return 3;
}
}
NODE exptree(char infix[15])
{
int i;
int top1=-1,top2=-1;
char symbol;
NODE temp,t1,t2;
NODE treest[10],operst[10];
for(i=0;infix[i]!='\0';i++)
{
symbol=infix[i];
temp=create(symbol);
if(isalnum(symbol))
treest[++top2]=temp;
else
{
if(top1 == -1 ||
preced(operst[top1]->info) < preced(symbol))
operst[++top1]=temp;
else
{
t1=treest[top2--];
t2=treest[top2--];
temp->r=t1;
temp->l=t2;
treest[++top2]=temp;
}
}
}
while(top1 != -1)
{
t1=treest[top2--];
t2=treest[top2--];
temp=operst[top1--];
temp->r=t1;
temp->l=t2;
treest[++top2]=temp;
}
return treest[top2];
}
void inorder(NODE root)
{
if(root != NULL){
inorder(root->l);
printf("%c",root->info);
inorder(root->r);
}
}
void pre(NODE root)
{
if(root != NULL)
{
printf("%c",root->info);
pre(root->l);
pre(root->r);
}
}
void post(NODE root)
{
if(root!=NULL)
{
post(root->l);
post(root->r);
printf("%c",root->info);
}
}
int main()
{
NODE root;
root=NULL;
char infix[15];
printf("enter
exp\n");
scanf("%s",infix);
root = exptree(infix);
printf("inorder \n");
inorder(root);
printf("\nPREORDEr\n");
pre(root);
printf("\npost order\n");
post(root);
printf("\n\n\n");
}//END OF 2nd PROGRAM
3. Implement a simple Dictionary using Trees.
//PROGRAM STARTS HERE
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node{
char
word[10];
char
meaning[25];
struct
node *r;
struct
node *l;
};
typedef struct node *NODE;
NODE create(NODE root,char *word,char *meaning)
{
NODE
temp,cur,prev;
temp=(NODE)malloc(sizeof(struct
node));
strcpy(temp->word,word);
strcpy(temp->meaning,meaning);
temp->r= NULL;
temp->l= NULL;
if(root ==
NULL)
{
//root=new;
return
temp;
}
prev=NULL;
cur =
root;
while(cur
!= NULL)
{
prev
= cur;
if(strcmp(word,cur->word)
< 0)
cur=cur->l;
else
cur=cur->r;
}
if(strcmp(word,prev->word)
< 0)
prev->l=temp;
else
prev->r=temp;
return
root;
}
NODE min(NODE root)
{
NODE temp;
temp=root;
while(temp->l
!= NULL)
temp=temp->l;
return
temp;
}
NODE delete(NODE root,char *word) //sldhjgkhjhdjlkj
{
NODE temp;
if(root ==
NULL)
return
root;
if(strcmp(word,root->word)
< 0)
root->l=delete(root->l,word);
else
if(strcmp(word,root->word) > 0)
root->r=delete(root->r,word);
else
{
if(root->l
== NULL)
{
temp=root->r;
printf("word
deleted \n");
free(root);
return
temp;
}
else
if(root->r == NULL)
{
temp=root->l;
printf("word
deleted \n");
free(root);
return
temp;
}
temp=min(root->r);
strcpy(root->word,temp->word);
root->r=delete(root->r,word);
}
return
root;
}
void pre(NODE root)
{
if(root !=
NULL)
{
printf("%s->%s\n",root->word,root->meaning);
pre(root->l);
pre(root->r);
}
}
void in(NODE root)
{
if(root !=
NULL)
{
in(root->l);
printf("%s->%s\n",root->word,root->meaning);
in(root->r);
}
}
void post(NODE root)
{
if(root !=
NULL)
{
post(root->l);
post(root->r);
printf("%s->%s\n",root->word,root->meaning);
}
}
int main()
{
NODE
root=NULL;
char
word[10],meaning[25];
int ch;
while(ch!=6)
{
printf("1.insert\n2.del\n3.inorder\n4.preorder\n5.post
order \n 6.exit\nenter ur choice\n");
scanf("%d",&ch);
switch(ch)
{
case
1: printf("\nenter word\t:");
scanf("%s",word);
getchar();
printf("\nmeaning\t:");
gets(meaning);
// scanf("%s",meaning);
root
= create(root,word,meaning);
break;
case
2: printf("\nenter word to be deleted\t:");
scanf("%s",word);
root=delete(root,word);
break;
case
3: in(root);
break;
case
4:pre(root);
break;
case
5:post(root);
break;
default
: exit(0);
}
}
}//END OF 3rd PROGRAM
No comments:
Post a Comment