PROGRAMS ON DATA STRUCTURES

1. Write a C program to implement stack using arrays.

2. Write a C program to implement queue using arrays.
3. Write a C program implement the following Stack applications
a) infix into postfix
b) Evaluation of the postfix expression
4. Write a C program to implement the following types of queues
a) Priority queue
b) Circular queue
5. Write a C program to implement the Singly Linked List
6. Write a C program to implement the doubly Linked List
7. Write a C program to implement the following search algorithms.
i) Linear search ii) Binary search iii) Fibonacci search
8. Write a C program to implement the sorting algorithms.
9. Write a C program to implement binary tree using arrays and to perform binary
traversals.
i) Inorder ii) preorder iii) post order
10. Write a C program to balance a given tree.

66
1: STACK USING ARRAYS
#include<stdio.h>
#include<conio.h>
#include<process.h>
int ch,max,item,top=-1,s[20]; void menu(void);
void push(int); int pop(void); void display(void); void main()
{
clrscr();
printf("ENTER STACK SIZE:"); scanf("%d",&max);
menu();
getch();
}
void menu()
{
printf("1.PUSH\n2.POP\n3.EXIT\n"); printf("ENTER YOUR CHOICE:");
fflush(stdin);
scanf("%d",&ch);
switch(ch)
{
case 1:printf("ENTER THE ELEMENT\n"); scanf("%d",&item);
push(item);
menu();
break;
case 2:item=pop(); menu();
break;
case 3:exit(0);
}
}
void push(int item)
{
if(top==max-1)
printf("STACK IS OVER FLOW\n"); else
{
top++;
s[top]=item;
}
display();
}
int pop()
{
if(top==-1)
{
printf("STACK IS UNDER FLOW\n"); return 0;
}
else
{
item=s[top]; top--;
}
display(); return item;
67
 }
void display()
{
int i;
printf(" top -->");
for(i=top;i>=0;i--)
printf("%d\n\t",s[i]);
}
OUTPUT:
Enter stack size: 3
1. Push
2. Pop
3. Exit
Enter your choice:1
Enter the element: 3
Top: 3
1. Push
2. Pop
3. Exit
Enter your choice:1
Enter the element: 5
Top: 5
3
1. Push
2. Pop
3. Exit
Enter your choice:1
Enter the element: 9
Top: 9 5 3
1. Push
2. Pop
3. Exit
Enter your choice: 1
Enter the element: 15
Stack is overflow
Top: 9 5 3
1. Push
2. Pop
3. Exit
Enter your choice: 3
Popped element is: 9
Top: 5 3
1. Push
2. Pop
3. Exit
Enter your choice: 2
Popped element is: 5
Top: 3
1. Push

68
 2. Pop
3. Exit
Enter your choice: 2 Stack is underflow
1. Push
2. Pop
3. Exit
Enter your choice: 3

2. QUEUE USING ARRAYS

#include<stdio.h>
#include<conio.h>
#include<stdlib.h> void insertion(void); void deletion(void); void display(void);
int q[10],n,i,f,r;
int f=0,r=0; void main()
{
int op;
clrscr();
printf("ENTER THE SIZE OF QUEUE:"); scanf("%d",&n);
while(1)
{
printf("\n1.INSERTION\n2.DELETION\n3.DISPLAY\n4.EXIT\n");
printf("ENTER YOUR OPTION:");
scanf("%d",&op);
switch(op)
{
case 1:insertion(); break;
case 2:deletion(); break;
case 3:display(); break; default:exit(0);
} } }
void insertion()
{
if(r>=n)
printf("QUEUE IS OVER FLOW"); else
{
r=r+1;
printf("\nENTER AN ELEMENT TO INSERT:"); scanf("%d",&q[r]);
if(f==0)
f=1;
} }
void deletion()
{
if(f==0)
printf("THE QUEUE IS EMPTY"); else
{
printf("THE DELETING ELEMENT IS:%5d",q[f]); f=f+1;
if(f>r)
f=0,r=0;
} }
69
 void display()
{
if(f==0)
printf("QUEUE IS EMPTY"); else
for(i=f;i<=r;i++)
printf("%5d",q[i]);
}
OUTPUT:
Enter the size of queue: 2
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your option: 1
Enter an element to insert: q [1]:34
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your option: 3 34
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your option: 4

3: STACK APPLICATIONS
a) INFIX INTO POSTFIX
b) EVALUATION OF THE POSTFIX EXPRESSION

Program:(a)
#include<stdio.h>
#include<conio.h>
#define MAX 50
char stack[MAX];
int top=-1
void push(char); char pop();
int priority(char); void main()
{
char a[MAX],ch; int i;
clrscr();
printf("Enter an infix expression:\t"); gets(a);
printf("\the postfix expression for the given expression is:\t"); for(i=0;a[i]!='\0';i++)
{
ch=a[i];
if((ch>='a') && (ch<='z')) printf("%c",ch);
else if(ch=='(') push(ch); else if(ch==')')
{

70
while((ch=pop())!='(')
printf("%c",ch);
}
else
{
while(priority(stack[top])>priority(ch))
printf("%c",pop());
push(ch);
}
}
while(top>-1) printf("%c",pop());
printf("\n");
getch();
}
void push(char ch)
{
if(top==MAX-1)
{
printf("STACK OVERFLOW"); return;
}
else
{
top++;
stack[top]=ch; } }
char pop()
{
int x; if(top==-1)
{
printf("STACK EMPTY");
}
else
{ x=stack[top]; top--; }
return x;
}
int priority(char ch)
{
switch(ch)
{
case '^': return 4; case '*':
case '/': return 3; case '+':
case '-': return 2; default : return 0;
} }
OUTPUT:
Enter an infix expression:
((a + b ((b ^ c – d))) * (e – (a / c)))
The postfix expression for the given expression is:
abbc^d-+eac/-*

71
Program:(b)
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<ctype.h>
void push(char);
char pop(void);
char ex[50],s[50],op1,op2; int i,top=-1;
void main()
{
clrscr();
printf("Enter the expression:"); gets(ex); for(i=0;ex[i]!='\0';i++)
{
if(isdigit(ex[i])) push(ex[i]-48); else
{
op2=pop();
op1=pop();
switch(ex[i])
{
case '+':push(op1+op2);
break;
case '-':push(op1-op2);
break;
case '*':push(op1*op2);
break;
case '/':push(op1/op2);
break;
case '%':push(op1%op2);
break;
case '^':push(pow(op1,op2));
break;
} } }
printf("result is :%d",s[top]); getch();
}
void push(char a)
{ s[++top]=a; }
char pop()
{ return(s[top--]);
}

OUTPUT:

Enter the expression: 384 * 2 / +83----

Result is: 14

72
4: TYPES OF QUEUES
a).Priority queue
b).Circular queue

Program: (a)
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
typedef struct node
{
int priority;
int info;
struct node *link;
}n;
n *getnode()
{
return ( (n *)malloc(sizeof(n)));
}
n*front=NULL,*temp=NULL,*ptr=NULL,*q=NULL;
void insertion();
void deletion();
void display();
void main()
{
int ch;
clrscr();
printf("\tMenu\n1.Insertion\n2.Deletion\n3.Display\n4.exit");
while(1)
{
printf("Enter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1:insertion();
break;
case 2:deletion();
break;
case 3:display();
break;
case 4:exit();
default : printf("\nInvalid choice ");
break;
} } }
void insertion()
{ int item,item_prty;
temp=getnode();
printf("Enter item to insert ");
scanf("%d",&item);
printf("Enter item prority ");
73
 scanf("%d",&item_prty);
temp->priority=item_prty;
temp->info=item;
if(front==NULL||item_prty>front->priority)
{
temp->link=front;
front=temp;
}
else
{
q=front;
while (q->link!=NULL &&q->link-> priority >=item_prty)
q=q->link;
temp->link=q->link;
q->link=temp;
}
}
void deletion()
{ if(front==NULL)
printf("Queue is underflow");
else
{
temp=front;
printf("Deleted item is %d\n",
temp->info);
front=front->link;
free(temp);
}
}
void display()
{
ptr=front;
if(front==NULL)
printf("Queue is underflow");
else
{
printf("Queue is :\n");
printf("priority item :\n");
while(ptr!=NULL)
{
printf("%5d %5d\n",ptr->priority,ptr->info);
ptr=ptr->link;

}
}
}

OUTPUT:

74
1 - Insert an element into queue
2 - Delete an element from queue
3 - Display queue elements
4 - Exit
Enter your choice: 1

Enter value to be inserted: 20

Enter your choice: 1
Enter value to be inserted: 45
Enter your choice: 1
Enter value to be inserted: 89
Enter your choice: 3
89 45 20
Enter your choice: 1
Enter value to be inserted: 56
Enter your choice: 3
89 56 45 20
Enter your choice: 2
Enter value to delete: 45
Enter your choice: 3
89 56 20
Enter your choice: 4

Program: (b)
#include<stdio.h>
#include<conio.h>
#define max 3
int q[max],rear=-1,front=-1;
void main()
{ int ch;
clrscr();
do
{ printf("\nqueue implementation\n");
printf("1.insert 2.delete 3.display 4.exit\n");
printf("enter your choice\n");
scanf("%d",&ch);
switch(ch)
{ case 1:insert(); break;
case 2:delete(); break;
case 3:display(); break;
case 4:exit(1);
default:printf("wrong choice\n"); break;
}
}while(ch<=4);
getch();
}
insert()
{ int item;

75
 if(rear==max-1)
{ printf("queue overflow\n"); }
else
{ if(front==-1)
front=0;
printf("insert the element in queue:");
scanf("%d",&item);
rear++;
q[rear]=item;
}
}
delete()
{ if(front==-1)
{ printf("queue underflow\n");
}
else
{ printf("element deleted from queue is:%d\n",q[front]);
front++;
if(front==max)
front=rear=-1;
}
}
display()
{ int i;
if(front==-1)
printf("queue is empty\n");
else
{ printf("queue is :\n");
for(i=front;;i++)
{ printf("%2d",q[i]);
if(i==rear)
return;
} } }

OUTPUT:
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:1
Enter element to cqueue: 10
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice: 1
Enter element to circular queue: 20
1. Insert
2. Delete

76
3. Display
4. Exit
Enter your choice: 2
Deleted element from circular queue is: 10
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice: 3
Elements from circular queue is: 20
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice: 4

5: SINGLY LINKED LIST

Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h> struct node
{
int data;
struct node* link; };
typedef struct node* pnode; pnode head=NULL;
void menu(void); void insbeg(int); void delbeg(void); void insend(int); void delend(void);
void insafter(int,int); void delmid(int); void display(void); void main()
{
int ch,x,pos; clrscr(); while(1)
{
menu();
printf("enter ur choice\n"); scanf("%d",&ch);
switch(ch)
{
case 1: printf("enter element to insert\n");
scanf("%d",&x);
insbeg(x);
break;
case 2:delbeg();
break;

case 3: printf("enter element to insert\n");

scanf("%d",&x);
insend(x);
break;
case 4:delend();
break;
case 5: printf("enter element,pos to insert\n");
77
scanf("%d%d",&x,&pos);
insafter(x,pos);
break;
case 6:printf("enter position of element to delete\n"); scanf("%d",&pos);
delmid(pos);
break;
case 7:display();
break;
case 8:exit(0);
} } }
void menu()
{
printf("1.insbeg\n2.delbeg\n3.insend\n4.delend\n");
printf("5.insafter\n6.delmid\n7.display\n8.exit\n");
}
void insbeg(int x)
{
pnode ptr;
ptr=(pnode)malloc(sizeof(struct node));
ptr->data=x;
ptr->link=head; head=ptr;
}
void delbeg()
{
pnode tmp; int x;
if(head==NULL)
{
printf("list is empty\n"); return;
}
tmp=head;
head=tmp->link;
printf("deleted element is %d\n",tmp->data);
free(tmp);
}
void insend(int x)
{
pnode tmp,ptr;
ptr=(pnode)malloc(sizeof(struct node));
ptr->data=x;
ptr->link=NULL; if(head==NULL)
{
head=ptr;
}
else
{
tmp=head;
while(tmp->link!=NULL)
tmp=tmp->link;
tmp->link=ptr;

78
 } }
void delend()
{
pnodeprev=NULL,ptr=head;
int x; if(head==NULL)
{
printf("listis empty\n"); return;
}
while(ptr->link!=NULL)
{
prev=ptr; ptr=ptr->link;
}
if(prev==NULL)
head=NULL;
else
prev->link=NULL;
printf("deleted node:%d\n",ptr->data);
free(ptr);
}
void insafter(intx,intpos)
{
pnodetmp=head,ptr;
int i;
for(i=1;i<pos;i++)
{
tmp=tmp->link;
if(tmp==NULL)
{
printf("position out of range\n"); return;
} }
ptr=(pnode)malloc(sizeof(struct node));
ptr->data=x;
ptr->link=tmp- >link;
tmp->link=ptr;
}
void delmid(intpos)
{
pnodeprev=NULL,tmp=head;
int i;

if(head==NULL)
{
printf("list is empty\n"); return;
}
for(i=0;i<pos;i++)
{
prev=tmp; tmp=tmp->link;
if(tmp==NULL)
{ printf("position out of range\n"); return;

79
 } }

if(prev!=NULL)
prev->link=tmp->link;
else
head=tmp->link;
printf("deleted element: %d\n",tmp->data);
free(tmp);
}
void display()
{
pnodeptr=head;
while(ptr!=NULL)
{
printf("%d-->",ptr->data);
ptr=ptr->link;
}
printf("\n");
getch();
}
OUTPUT:
1. Ins beg
2. el beg
3. Ins end
4. Del end
5. Ins after
6. Del mid
7. Display
8. Exit
Enter your choice: 1
Enter element to insert: 94
1. Ins beg
2. Del beg
3. Ins end
4. Del end
5. Ins after
6. Del mid
7. Display
8. Exit
Enter your choice: 1
Enter element to insert: 90
1. Ins beg
2. Del beg
3. Ins end
4. Del ed
5. Ins after
6. Del mid
7. Display
8. Exit

80
 Enter your choice 5
Enter element, Pos to insert
55 2

1. Ins beg
2. Del beg
3. Ins end
4. Del end
5. Ins after
6. Del mid
7. Display
8. Exit
Enter your choice 7 90->94->55->
1. Ins beg
2. Del beg
3. Ins end
4. Del end
5. Ins after
6. Del mid
7. Display
8. Exit
Enter your choice 8

6: DOUBLY LINKED LIST

Program:
#include<stdio.h>
#include<conio.h> struct node
{
struct node *prev; int data;
struct node *nxt;
}
*head=NULL,*curr=NULL,*curr1=NULL,*p;

void insert(int pos)

{
int count=1,i; p=head;
while(p->nxt!=NULL)
{
count++; p=p->nxt;
}
p=head;
if(pos<=count+1)
{
curr=(struct node*)malloc(sizeof(struct node));
printf("Enter the node:");
scanf("%d",&curr->data);
curr->nxt=NULL;
curr->prev=NULL;
if(head==NULL)

81
{
head=curr; }
else if(pos==1)
{
head->prev=curr;
curr->nxt=head;
head=curr; }
else
{ for(i=1;i<(pos-1);i++) p=p->nxt;
curr->prev=p; curr->nxt=p->nxt;
p->nxt->prev=curr;
p->nxt=curr;
}
printf("\n%d inserted at pos:%d!\n",curr->data,pos);
}
else
printf("\nEnter a valid position!");

}
void deletenode(int data)
{
int found=0; curr=head; if(head->data == data)
{
(head->nxt)->prev=NULL; head=head->nxt;
printf("\n%d deleted!\n",curr->data);
free(curr);
}
else
{
curr=curr->nxt;
while(curr->nxt!=NULL)
{
if(curr->data==data)
{
found=1;
break;
}
else
curr=curr->nxt;
}
if(found==1 || curr->data==data)
{
curr1=curr->prev; curr1->nxt=curr->nxt; (curr->nxt)->prev=curr1; printf("\n%d
deleted!\n",curr->data); free(curr);
}
else
printf("\n%d is not present in the list!\n",data);
} }
void display()

82
 {
curr=head;
if(head==NULL)
printf("\nList is empty!\n"); else {
printf("\nList:\n"); while(curr->nxt!=NULL) {
printf("%d\t",curr->data); curr=curr->nxt;
}
printf("%d\n",curr->data);
}
}
void main()
{
intop,data;
clrscr();
printf("Creation of Doubly Linked List\n");
curr=(struct node*)malloc(sizeof(struct node));
curr->nxt=NULL;
curr->prev=NULL; printf("Enter the first node:"); scanf("%d",&curr->data); head=curr;
head->nxt=NULL; head->prev=NULL; do
{ printf("\nDOUBLY LINKED LIST OPERATIONS:\n1.Insert a node ");
printf("\n2.Delete a node\n3.Display\n4.Exit\n");
printf("\nSelect an operation:"); scanf("%d",&op);
switch(op)
{
case 1:
{ printf("Enter the position where you want to insert the node:"); scanf("%d",&data);
insert(data); break;
}
case 2:{
printf("Enter the node to be deleted:"); scanf("%d",&data);
deletenode(data); break; }

case 3: {
display();
break; }
case 4:
break;
default:
printf("\nEnter a valid option!");
}
}while(op!=4);
getch();
}
OUTPUT:
Doubly linked list operations
1. Insert node
2. Delete node
3. Display

83
4. Exit
Select an operation: 1
Enter the position to insert node: 1 Enter the node: 59
59 inserted at pos: 1
1. Insert node
2. Delete node
3. Display
4. Exit
Select an operation: 4

7: SEARCHING ALGORITHMS

i) Linear search ii) Binary search

iii) Fibonacci search

Program: (i)and (ii)

#include <stdio.h>
#include <conio.h>
# include <stdlib.h>
void main()
{
Int a[10],n,flag=0,i,lb,ub,key,mid,ch;
clrscr();
printf("enter the size of the elements\n");
scanf("%d",&n);
printf("enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter any key element to search\n");
scanf("%d",&key);
printf("menu\n");
printf("\n1.linear search\n2.binary search \n");
printf("enter your choice:\n"); scanf("%d",&ch);
switch(ch)
{ case 1:for(i=0;i<n;i++) if(a[i]==key)
{
flag=1;
break;}
case 2:for(lb=0,ub=n-1;lb<=ub;)
{
mid=(lb+ub)/2;
if(key==a[mid])
{
flag=1;
break;
}
else if(key<a[mid]) ub=mid-1;
else lb=mid+1;
}

84
 break;
default:exit(0);
}
if(flag==1)
printf("seach is successful");
else
printf("search is not successful \n");
getch();

}
OUTPUT:
Enter the size of the elements 5
Enter the elements 32 6 3 9 5
Enter any element to search 3
Menu
1. Linear search
2. Binary search Enter your choice: 2
Search is successful

Program:(iii)
#include<stdio.h>
void main()
{
int n,a[50],i,key,loc,p,q,r,m,fk;
clrscr();
printf("\nenter number elements to be entered");
scanf("%d",&n);
printf("enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("enter the key element");
scanf("%d",&key);
fk=fib(n+1);
p=fib(fk);
q=fib(p);
r=fib(q) ;
m=(n+1)-(p+q);
if(key>a[p])
p=p+m;
loc=rfibsearch(a,n,p,q,r,key);
if(loc==0)
printf("key is not found");
else
printf("%d is found at location %d",key,loc);
getch();
}
int fib(int m)
{
int a,b,c;

85
 a=0;
b=1;
c=a+b;
while(c<m)
{
a=b;
b=c;
c=a+b;
}
return b;
}
int rfibsearch(int a[],int n,int p,int q,int r,int key)
{
int t;
if(p<1||p>n)
return 0;
else if(key==a[p])
return p;
else if(key<a[p])
{
if(r==0)
return 0;
else
{
p=p-r;
t=q;
q=r;
r=t-r;
return rfibsearch(a,n,p,q,r,key);
} }
else
{
if(q==1)
return 0;
else
{
p=p+r;
q=q-r;
r=r-q;
return rfibsearch(a,n,p,q,r,key);
} } }

OUTPUT:
Enter the number elements to be entered 8
Enter the elements 1 3 2 5 4 6 7 9
Enter the key element 9
8 is found at location 8

86
8: SORTING ALGORITHMS
Program: Bubble Sort
#include<stdio.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
void bubblesort(int x[],int n); void main()
{
intnum[10],i,n;
clrscr();
printf("Enter the no of elements\n"); scanf("%d",&n);
printf("Enter the elements\n"); for(i=0;i<n;i++) scanf("%d",&num[i]); bubblesort(num,n);
printf("sorted elements are\n"); for(i=0;i<n;i++) printf("%d\t",num[i]);
getch();}
void bubblesort(int x[],int n)
{
inthold,j,pass,K=TRUE;
for(pass=0;pass<n-1&&K==TRUE;pass++)
{
K=FALSE;
for(j=0;j<n-pass-1;j++) if(x[j]>x[j+1])
{
K=TRUE;
hold=x[j];
x[j]=x[j+1];
x[j+1]=hold;}}}
OUTPUT:
Enter the no of elements 5
Enter the elements 36 23 59 68 2
Sorted elements are 2 23 36 59 68

Program: selection sort

#include<stdio.h>
#include<conio.h> void main()
{
intn,i,j,a[10],min,t;
clrscr();
printf("enter how many elements\n"); scanf("%d",&n);
printf("enter the elements\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[min]>a[j])
min=j;
}
t=a[i];
a[i]=a[min];
a[min]=t;
87
}
printf("the sorted elements are \n"); for(i=0;i<n;i++)
printf("%5d",a[i]);
getch();
}
OUTPUT:
Enter how many elements 5
Enter the elements 56 48 46 23 35
The sorted elements are 23 35 46 56 98

Program: insertion sort

#include<stdio.h>
#include<conio.h> void main()
{
intn,i,a[10],t,j;
clrscr();
printf("enter how many elements\n");
scanf("%d",&n);
printf("enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
for(j=i;j>0;j--)
{
if(a[j]<a[j-1])
{
t=a[j]; a[j]=a[j-1]; a[j-1]=t;
} } }
printf("the sorted elements are\n"); for(i=0;i<n;i++)
printf("%5d",a[i]);
getch();
}
OUTPUT:
Enter how many elements 5
Enter the elements 26 36 98 12 5
The sorted elements are 5 12 26 36 98

Program:Quick sort
#include<stdio.h>
#include<conio.h>
void quick(int a[10],intlb,int n);
void main()
{
intn,i,a[10];
clrscr();
printf("enter how many elements \n"); scanf("%d",&n);
printf("enter the elements \n"); for(i=0;i<n;i++) scanf("%d",&a[i]); quick(a,0,n-1);
printf("the sorted elements are \n"); for(i=0;i<n;i++)

88
printf("%d \n",a[i]); getch();
}
void quick(int a[],intlb,intub)
{
inti,j,t,key;
if(lb>ub) return; i=lb;
j=ub;
key=lb;
while(i<j)
{
while(a[key]>a[i])
i++;
while(a[key]<a[j]) j--;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
t=a[j];
a[j]=a[key];
a[key]=t;
quick(a,0,j-1);
quick(a,j+1,ub);
}
OUTPUT:
Enter how many elements 5
Enter the elements 65 23 89 68 71
The sorted elements are 23 65 68 71 89

program:heap sort
#include<conio.h>
void maxheap(int [],int,int);
void buildmaxheap(int a[],int n)
{
int i; for(i=n/2;i>=1;i--)
{
maxheap(a,i,n);
}
}
void maxheap(int a[],inti,int n)
{
intR,L,largest,t;
L=2*i;
R=2*i+1;
if((L<=n) && (a[L]>a[i])) largest=L;
else largest=i;
if((R<=n) && (a[i]>a[largest])) largest=R;

89
if(largest!=i)
{
t=a[i];
a[i]=a[largest];
a[largest]=t;
maxheap(a,largest,n);
}
}
void heapsort(int a[],int n)
{
inti,temp;
buildmaxheap(a,n);
for(i=n;i>=2;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp; maxheap(a,1,i-1);
}
}
vod main()
{
int a[50],i,n; clrscr();
printf("Enter the size of array : "); scanf("%d",&n);
printf("Enter the elements of array \n"); for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
heapsort(a,n);
printf("sorted array is \n"); for(i=1;i<=n;i++)
{
printf("%d\t",a[i]);
}
getch();
}
OUTPUT:
Enter the size of array: 4
Enter the elements of array: 35 21 95 17
Sorted array is: 17 21 35 95
Program: merge sort
#include<stdio.h>
#include<conio.h>
void merge(int [],int ,int ,int );
void part(int [],int ,int );
int main()
{
intarr[30];
inti,size;
printf("\n\t------- Merge sorting method -------\n\n");
printf("Enter total no. of elements : "); scanf("%d",&size);

90
for(i=0; i<size; i++)
{printf("Enter %d element : ",i+1);
scanf("%d",&arr[i]);
}
part(arr,0,size-1);
printf("\n\t------- Merge sorted elements -------\n\n"); for(i=0; i<size; i++)

printf("%d ",arr[i]); getch();

return 0;
}
void part(intarr[],intmin,int max)
{
int mid; if(min<max)
{
mid=(min+max)/2;
part(arr,min,mid);

part(arr,mid+1,max);
merge(arr,min,mid,max);
}
}
void merge(intarr[],intmin,intmid,int max)
{
inttmp[30];
inti,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)
{
if(arr[j]<=arr[m])
{
tmp[i]=arr[j];
j++;
}
else
{
tmp[i]=arr[m];
m++;
}
}
if(j>mid)
{
for(k=m; k<=max; k++)
{
tmp[i]=arr[k];
i++;
}
}
else

91
{
for(k=j; k<=mid; k++)
{
tmp[i]=arr[k];
i++;
}
}
for(k=min; k<=max; k++) arr[k]=tmp[k];
}
OUTPUT:
Merge sorting method
Enter total no of elements: 4
Enter 4 elements:
35
95
17
21
Merge sorted elements: 17 21 35 95

9.BINARY TREE TRAVERSALS

i) Preorder ii) Inorder iii) Postorder
Program:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h> struct node
{
int data;
struct node *left; struct node *right; };
typedefstruct node *pnode; pnode root=NULL;
void insert(intval)
{
pnodep,q,t; t=(pnode)malloc(sizeof(struct node)); t->left=t->right=NULL;
t->data=val; if(root==NULL)
{
root=t;
return;
}
p=root;q=NULL;
while(p)
{
if(p->data==val)
{
return;
}
q=p;
if(val<p->data) p=p->left;
else if(val>p->data)
p=p->right;
92
}
if(val<q->data) q->left=t; if(val>q->data) q->right=t;
}
int search(int key)
{
pnode p=root;
while(p)
{
if(p->data==key) return 1;
else if(key<p->data) p=p->left;
else if(key>p->data) p=p->right;
}
return 0;
}
void inorder(pnode p)
{
if(p==NULL)
return; inorder(p->left); printf("%3d",p->data); inorder(p->right);
}
void preorder(pnode p)
{
if(p==NULL)
return;
printf("%3d",p->data);
preorder(p->left);
preorder(p->right);
}
void postorder(pnode p)
{
if(p==NULL)
return;
postorder(p->left);
postorder(p->right);
printf("%3d",p->data);
}
int main()
{
intch,x;
clrscr();
while(1)
{
printf("\n1.insertion");
printf("\n2.inorder");
printf("\n3.preorder");
printf("\n4.postorder");
printf("\n5.search");
printf("\n6.exit");
printf("\nenterur choice\n");
scanf("%d",&ch);

93
switch(ch)
{
case 1:printf("enter an elements\n"); scanf("%d",&x);
insert(x);
break;
case 2:inorder(root); break;
case 3:preorder(root); break;
case 4:postorder(root); break;
case 5:printf("enter key elements\n");
scanf("%d",&x);
if(search(x))
printf("found"); else
printf("not found"); break;
case 6:exit(0);
} } }
OUTPUT:

Tree traversal
Enter the number of terms to add 7 Enter the item 15
Enter the item 7 Enter the item 9 Enter the item 18 Enter the item 6 Enter the item 21 Enter
the item 2
In order traversal 2 6 7 9 15 18 21
Pre order traversal 15 7 6 2 9 18 21
Post order traversal 2 6 9 7 21 18 15

10.BALANCE A TREE

Program:
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
};

typedef struct btnode N;

N* bst(int arr[], int first, int last);
N* new(int val);
void display(N *temp);
int main()
{
int arr[] = {10, 20, 30, 40, 60, 80, 90};
N *root = (N*)malloc(sizeof(N));
int n = sizeof(arr) / sizeof(arr[0]), i;

printf("Given sorted array is\n");

for (i = 0;i < n;i++)
94
 printf("%d\t", arr[i]);
root = bst(arr, 0, n - 1);
printf("\n The preorder traversal of binary search tree is as follows\n");
display(root);
printf("\n");
return 0;
}
N* new(int val)
{
N* node = (N*)malloc(sizeof(N));

node->value = val;
node->l = NULL;
node->r = NULL;
return node;
}

N* bst(int arr[], int first, int last)

{
int mid;
N* temp = (N*)malloc(sizeof(N));
if (first > last)
return NULL;
mid = (first + last) / 2;
temp = new(arr[mid]);
temp->l = bst(arr, first, mid - 1);
temp->r = bst(arr, mid + 1, last);
return temp;
}
void display(N *temp)
{
printf("%d->", temp->value);
if (temp->l != NULL)
display(temp->l);
if (temp->r != NULL)
display(temp->r);
}
OUTPUT:

Given sorted array is

10 20 30 40 60 80 90
The preorder traversal of binary search tree is as follows
40->20->10->30->80->60->90

95