1.Binary search
#include<stdio.h>
#include<conio.h>
void sortarray(int a[])
{
int i,j,temp;
for(i=0;i<8;i++)
{
for(j=i+1;j<8;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf(“\n\nThe Sorted Array:\n\n”);
for(i=0;i<8;i++)
printf(“%3d”,a[i]);
}
int binarySearch(int arr[],int key)
{
int beg=0,end=8,mid,result=-1;
// mid=(beg+end)/2;
while(beg<=end)
{
mid=(beg+end)/2;
if(arr[mid]==key)
{
result=mid;
end=mid-1;
}
else if(key<arr[mid])
end=mid-1;
else
beg=mid+1;
}
return result;
}
void main(){
int arr[]={4,7,3,2,1,7,9,0};
int i,key=7,loc;
clrscr();
printf(“\nBinary Search\n”);
printf(“\nArray values are: \n”);
for(i=0;i<8;i++)
printf(“%3d”,arr[i]);
printf(“\n\nThe Search element is %d”,
key);
printf(“\n\nSorting the array elements
“);
sortarray(arr);
printf(“\n\nPerforming Binary Search to
find the element: %d”,key);
loc=binarySearch(arr,key);
printf(“\n\nThe element’s first occurence
is at the position %d”,loc+1);
getch();
}
2.Quicksort
#include <stdio.h>
#include <conio.h>
int partition(int a[10], int low, int high) {
int pivot, j, temp, i;
pivot = low;
i = low;
j = high; while (i < j) {
while (i < high && a[i] <= a[pivot])
i++;
while (a[j] > a[pivot])
j–;
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[pivot];
a[pivot] = a[j];
a[j] = temp;
return j;
}
void quicksort(int a[10], int low, int high) {
int j;
if (low < high) {
j = partition(a, low, high);
quicksort(a, low, j – 1);
quicksort(a, j + 1, high);
}
}
void main() {
int i, n, a[10];
clrscr();
printf(“Enter the array size:\n”);
scanf(“%d”, &n);
printf(“Enter the array elements:\n”);
for (i = 0; i < n; i++) {
scanf(“%d”, &a[i]);
}
quicksort(a, 0, n – 1);
printf(“Sorted Array is\n”);
for (i = 0; i < n; i++)
printf(“%d “, a[i]);
getch();
}
3.Mergesort
#include <conio.h>
#include <stdio.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m – l + 1;
int n2 = r – m;
int L[10], R[10];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergesort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r – l) / 2;
mergesort(arr, l, m);
mergesort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int n, i; int arr[50];
// clrscr();
printf(“Enter the array size: “);
scanf(“%d”, &n);
printf(“Enter array elements:\n”);
for (i = 0; i < n; i++)
scanf(“%d”, &arr[i]);
mergesort(arr, 0, n – 1);
printf(“Sorted array is: “);
for (i = n – 1; i >= 0; i–)
{
printf(“%d “, arr[i]);
}
printf(“\n”);
// getch();
return 0;
}
4./* Write a program to insert the elements 61,16,8,27 into
single linked list & delete 8, 61, 27 from list. Display the list after
each insertion & deletion*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int INFO;
struct node *LINK;
};
typedef struct node NODE;
NODE *start= NULL;
void create()
{
char ch;
int i=0;
NODE *currptr, *NEWNODE;
currptr= (NODE *) malloc (sizeof(NODE));
start= currptr;
while(1)
{
printf(“enter the node %d”, i+1);
scanf(“%d”, &currptr ->INFO);
printf(” do you want to add one more item(Y/N)”);
ch= getche();
if(toupper(ch) ==’Y’)
{ NEWNODE=(NODE *) malloc (sizeof(NODE));
currptr -> LINK= NEWNODE;
currptr= NEWNODE;
}
else
{ currptr -> LINK=
NULL;
break; }
i++;
} }
void display()
{
NODE *currptr= start;
if( start== NULL)
printf(” linked list is empty\n”);
else
{ while( currptr != NULL)
{ printf(“%d”, currptr -> INFO);
printf(” -> “);
currptr= currptr -> LINK;
} printf(” NULL”);
} }
void insert_beg(int item)
{
NODE * NEWNODE;
NEWNODE= (NODE *) malloc (sizeof(NODE));
NEWNODE -> INFO = item;
NEWNODE -> LINK= start;
start= NEWNODE;
}
void insert_end(int item)
{
NODE *currptr, *NEWNODE;
if(start == NULL)
{
NEWNODE= (NODE *) malloc (sizeof(NODE));
NEWNODE -> INFO= item;
NEWNODE -> LINK= NULL;
start = NEWNODE;
} else
{ currptr= start;
while(currptr -> LINK!= NULL)
{ currptr= currptr -> LINK;
}
NEWNODE= (NODE *) malloc (sizeof(NODE));
NEWNODE -> INFO= item;
NEWNODE -> LINK= NEWNODE;
NEWNODE -> LINK= NULL;
} }
void insert_pos(int
item, int pos)
{
int i;
NODE *currptr= start, *NEWNODE;
if(pos==-1)
insert_beg(item);
else
{ for(i=0;i< pos-2;i++)
{ currptr= currptr -> LINK;
}
NEWNODE= (NODE *) malloc (sizeof(NODE));
NEWNODE -> INFO= item;
NEWNODE -> LINK= currptr -> LINK;
currptr-> LINK= NEWNODE;
} }
void delete_beg()
{
NODE *currptr;
if(start == NULL)
{ printf(” linked list is empty\n”);
return ;
}
else
{ currptr= start;
start= start -> LINK;
free(currptr);
} }
void delete_end()
{
NODE *currptr, *prevptr;
if(start== NULL)
printf(” linked list is empty\n”);
else if(start -> LINK== NULL)
{ start= NULL;
//return 0;
}
else
{ currptr= start;
prevptr= NULL;
while(currptr -> LINK!= NULL)
{ prevptr= currptr;
currptr= currptr -> LINK;
}
prevptr -> LINK= NULL;
} }
void delete_pos(int pos)
{
int i;
NODE *currptr, *prevptr;
if(pos==1)
delete_beg();
else {
currptr= start;
prevptr= NULL;
for(i=1;i<pos;i++)
{ prevptr= currptr;
currptr= currptr -> LINK;
}
prevptr ->LINK= currptr -> LINK;
} }
void delete_item(int item)
{
NODE *currptr= start, *prevptr= NULL;
if(start== NULL){
printf(” linked list is empty\n”);
//return 0;
}
else if(start -> INFO== item)
{ start= start -> LINK;
free(currptr);
//return 0;
}
else
{ while(currptr!=NULL && currptr ->INFO!=item)
{ prevptr= currptr;
currptr= currptr -> LINK;
}
if(currptr== NULL)
printf(“\n item is not found in LL”);
else
prevptr ->LINK= currptr->LINK;
} }
int length()
{
int len=0;
NODE *currptr;
if( start== NULL)
{ printf(” linked list is empty\n”);
return(len); }
currptr = start;
while(currptr!= NULL)
{ len++;
currptr= currptr -> LINK;
} return(len);
}
void main()
{
int ch, item, pos;
clrscr();
while(1)
{
printf(“\n 1.create a linked list”);
printf(“\n 2.display”);
printf(“\n 3.insert first node”);
printf(“\n 4.insert at the end”);
printf(“\n 5.insert at given position”);
printf(“\n 6.delete first node”);
printf(“\n 7.delete last node”);
printf(“\n 8.delete at given position”);
printf(“\n 9.delete a node when item is given”);
printf(“\n 10.exit”);
printf(“enter your choice\n”);
scanf(“%d”, &ch);
switch(ch)
{
case 1:start= NULL;
create();
break;
case 2:display();
break;
case 3:printf(“\nenter item to insert at beginning
\n”);
scanf(“%d”, &item);
printf(“\n LL before insertion is:”);
display();
insert_beg(item);
printf(“\n LL after insertion is:”);
display();
break;
case 4:printf(“\nenter item to insert at end”);
scanf(“%d”, &item);
printf(“\n LL before insertion is:”);
display();
insert_end(item);
printf(“\n LL after insertion is:”);
display();
break;
case 5:printf(“\nenter item to insert at given
position”);
scanf(“%d”, &item);
printf(“enter a valid pos”);
scanf(“%d”, &pos);
if((pos==0) || (pos>length()+1))
{ printf(“\n
invalid position”);
break;}
else
{ printf(“\n LL before insertion is:”);
display();
insert_beg(item);
printf(“\n LL after insertion is:”);
display();
break;}
case 6: printf(” \n linked list before deletion”);
display();
delete_beg();
printf(” \n linked list after deletion”);
display();
break;
case 7:printf(” \n linked list before deletion”);
display();
delete_end();
printf(” \n linked list after deletion”);
display();
break;
case 8: printf(“enter a valid position to
delete\n”);
if((pos==0) || (pos>length()))
{ printf(”
invalid position\n”);
break; }
else
{ printf(” \n linked list before deletion”);
display();
delete_pos(pos);
printf(” \n linked list after deletion”);
display();
break;
}
case 9: printf(” \n linked list before deletion”);
display();
printf(” enter an item to be deleted \n”);
scanf(“%d”, &item);
delete_item(item);
printf(” \n linked list after deletion”);
display();
break;
case 10: exit(0);
} } }
5./* Write a program
to add 6x^3+10x^2+0x+5 and 4x^2+2x+1 using Linked List */
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct polynomial
{
int coeff;
int power;
struct polynomial *LINK;
};
typedef struct polynomial NODE;
NODE *poly1= NULL, *poly2=NULL, *poly3= NULL;
NODE *create_poly();
NODE *add_poly(NODE *poly1, NODE *poly2);
void display_poly(NODE *ptr);
NODE *create_poly()
{
int flag;
int coeff, pow;
NODE *tmp_node= (NODE
*) malloc(sizeof(NODE));
NODE *poly= tmp_node;
do
{
printf(“\n enter coeff, power “);
scanf(“%d %d”, &coeff, &pow);
tmp_node-> coeff= coeff;
tmp_node-> power= pow;
tmp_node-> LINK= NULL;
printf(” do you want to add more item?(Y=
1/N=0):”);
scanf(“%d”, &flag);
if(flag==1)
{
tmp_node->LINK =
(NODE *) malloc(sizeof(NODE));
tmp_node=
tmp_node->LINK;
tmp_node->LINK=
NULL;
}
} while(flag);
return poly;
}
NODE *add_poly(NODE
*poly1, NODE *poly2)
{
NODE * tmp_node,
*poly;
tmp_node = (NODE *)
malloc(sizeof(NODE));
tmp_node->LINK=
NULL;
poly3= tmp_node;
while(poly1
&& poly2)
{
if(poly1->power > poly2->power)
{ tmp_node->power
= poly1->power;
tmp_node->coeff =
poly1->coeff;
poly1 =
poly1->LINK;
}
else
if(poly1->power < poly2->power)
{ tmp_node->power
= poly2->power;
tmp_node->coeff =
poly2->coeff;
poly2 =
poly2->LINK;
}
else
{ tmp_node->power
= poly1->power;
tmp_node->coeff =
poly1->coeff + poly2->coeff;
poly1 =
poly1->LINK;
poly2 =
poly2->LINK;
}
if(poly1 &&
poly2)
{ tmp_node->LINK =
(NODE *) malloc(sizeof(NODE));
tmp_node=
tmp_node->LINK;
tmp_node->LINK=
NULL;
}}
while(poly1 || poly2)
{ tmp_node->LINK = (NODE *) malloc(sizeof(NODE));
tmp_node=
tmp_node->LINK;
tmp_node->LINK=
NULL;
if(poly1)
{ tmp_node->power= poly1->power;
tmp_node->coeff= poly1->coeff;
poly1= poly1->LINK;
}
if(poly2)
{ tmp_node->power= poly2->power;
tmp_node->coeff= poly2->coeff;
poly2= poly2->LINK;
}
}
return poly;
}
void display_poly(NODE
*ptr)
{
while(ptr !=NULL)
{ printf(” %d x ^ %d”, ptr->coeff,
ptr->power);
ptr= ptr->LINK;
if(ptr !=NULL)
printf(“+”);
}}
int main()
{
clrscr();
printf(“create 1st polynomial\n”);
poly1= create_poly();
printf(” first polynomial expression: \n”);
display_poly(poly1);
printf(“create 2nd
polynomial\n”);
poly2= create_poly();
printf(” second polynomial expression: \n”);
display_poly(poly2);
add_poly(poly1, poly2);
printf(” addition oftwo polynomials are:\n”);
display_poly(poly3);
//return 0;
}
6./* Write a Program to push 5,9,34,17,32 into stack &
pop 3 times from stack also display the popped numbers.*/
#include<stdio.h>
#include<conio.h>
#define MAXSTK 5
int TOP= -1;
int S[MAXSTK];
main()
{
int ch;
clrscr();
while(1)
{
printf(“1.push,
2.pop, 3.display, 4.quit\n”);
printf(“enter your choice\n”);
scanf(“%d”, &ch);
switch(ch)
{
case 1:push(); break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(1);
default: printf(” invalid choice\n”);
} } }
push()
{
int item;
if (TOP== MAXSTK-1)
printf(” stack overflow\n”);
else
{
printf(“enter item to be pushed\n”);
scanf(“%d”, &item);
TOP= TOP+1;
S[TOP]= item;
}
return 0;
}
pop()
{
if(TOP== -1)
printf(“stack underflow\n”);
else
{
printf(“popped item is %d”, S[TOP]);
TOP= TOP-1;
}
return 0;
}
display()
{
int i;
if(TOP== -1)
printf(“stack is empty\n “);
else
{
printf(“stack items are\n”);
for(i=TOP;i>=0;i–)
printf(“%d\n”, S[i]);
}
return 0;
}
7./* Write a recursive program to find GCD of 4, 6, 8*/
#include<stdio.h>
#include<conio.h>
int gcd(int m, int n)
{
if(n==0)
return (m);
else if(n>m)
return gcd(n,m);
else
return (gcd(n, m % n));
}
void main()
{
int k,m,n;
clrscr();
printf(” enter three values \n”);
scanf(“%d %d %d”, &k, &m, &n);
printf(” gcd(%d %d %d) = %d \n”, k,m,n, gcd(k,
gcd(m,n)));
getch();
}
8./* Write a program to insert the elements {5,7,0,6,3,9}
into Circular queue & delete
6,9,5 using Linked list */
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct queue
{
int info;
struct queue *link;
};
struct queue *front= NULL, *rear= NULL;
void qinsert(int item)
{
struct queue *new_node;
new_node= (struct queue*)malloc (sizeof(struct queue));
new_node -> info= item;
new_node -> link= NULL;
if(front==NULL && rear==NULL)
{ front=rear=
new_node;
rear-> link= front;
}
else
{ rear-> link=
new_node;
rear= new_node;
rear->link= front;
} }
void qdelete()
{
struct queue *ptr;
ptr= front;
if(front==NULL && rear==NULL)
printf(” \n queue is empty”);
else if(front==rear)
{ front= rear= NULL;
printf(“value deleted is :%d”, ptr ->info);
free(ptr);
}else {
front= front -> link;
rear -> link= front;
printf(“value is deleted is :%d”, ptr ->info);
free(ptr);
} }
void display()
{
struct queue *ptr;
ptr= front;
if(front== NULL && rear== NULL)
printf(” queue is empty\n”);
else
{ printf(” queue
elements are \n”);
do {
printf(“%d\t”, ptr -> info);
ptr= ptr -> link;
} while(ptr!= front);
} }
void main()
{
int val , ch;
do
{
printf(“\n 1. insert”);
printf(“\n 2. delete”);
printf(“\n 3. display”);
printf(“\n 4. exit”);
printf(” \n enter your choice\n”);
scanf(“%d”, &ch);
switch(ch)
{
case 1: printf(”
insert an item into queue\n”);
scanf(“%d”,
&val);
qinsert(val);
break;
case 2: qdelete();
break;
case 3: display();
break;
} }
while(ch!= 4);
}
9./*Given s1={“flowers”}, s2= {“are
beautiful”}. write a program to perform string operations – len,
concatenate, substr, replace*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int length(char *str)
{
int length=0;
while(*str!= ‘\0’)
{ length++;
str++; }
return length;
}
void strconcat(char *str1, char *str2, char *result)
{
while(*str1!= ‘\0’)
{ *result= *str1;
str1++;
result++;
}
while(*str2!= ‘\0’)
{
*result= *str2;
str2++;
result++;
}
*result= ‘\0’;
}
void substr(char
*source, int start, int len, char *result)
{
int i;
for(i=0;i<len;i++)
{ result[i]= source[start + i];
}
result[i]= ‘\0’;
}
void strreplace(char
*source, char *target, char *replace, char *result)
{
char *found= strstr(source, target);
if(found)
{
int pos= found- source;
substr(source, 0, pos,result);
strconcat(result, replace, result);
strconcat(result, found+ strlen(target), result);
}
else
{ strcpy(result, source);
} }
int main()
{
char str1[100], str2[100],
result[100],substrresult[200], replacedresult[200];
int len, start;
char target[100], replace[100];
clrscr();
printf(” enter str1\n”);
fgets(str1, sizeof(str1), stdin);
str1[strcspn(str1,”\n”)] =’\0′;
printf(” enter str2 \n”);
fgets(str2, sizeof(str2), stdin);
str2[strcspn(str2, “\n”)]= ‘\0’;
printf(” length of str1- %d\n”, strlen(str1));
printf(” length of str2- %d\n”, strlen(str2));
strconcat(str1, str2, result);
printf(” concatenated string is: %s\n”, result);
printf(” enter pos of substr in str1\n”);
scanf(“%d”, &start);
printf(” enter length of substr\n”);
scanf(“%d”, &len);
substr(str1, start, len, substrresult);
printf(” substring is: %s\n”,substrresult);
printf(” enter substr to be removed\n”);
scanf(“%s”, target);
printf(” enter strto be replaced\n”);
scanf(“%s”, replace);
strreplace(str1, target, replace, replacedresult);
printf(” str after replacement: %s\n”,
replacedresult);
return 0;
}
10/* Write a program to convert infix to postfix expression
given X^Y/(5 * Z)+2 */
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 20
char s[MAX];
int top=0;
int precedence(char elem);
void push(char elem);
int pop();
void main()
{
char infix[MAX], postfix[MAX], ch, elem;
int i=0, j=0;
clrscr();
printf(” infix to postfix\n”);
printf(” enter infix expression\n”);
scanf(“%s”, infix);
push(‘#’);
for(i=0;i<strlen(infix);i++)
{
ch= infix[i];
if(isalnum(ch))
postfix[j++]= ch;
else if(ch=='(‘)
push(ch);
else if(ch==’)’)
{ while(s[top]!='(‘)
postfix[j++]= pop();
}
else
{ while(precedence(s[top])>=
precedence(ch))
postfix[j++]= pop();
push(ch); } }
while(s[top]!= ‘#’)
postfix[j++]= pop();
postfix[j]= ‘\0’;
printf(“postfix expression is: %s\n”, postfix);
}
int precedence(char elem)
{
switch(elem)
{
case ‘+’:
case ‘-‘: return (1);
case ‘*’:
case ‘/’: return (2);
case ‘^’: return (3);
case ‘(‘:
case ‘#’: return (0);
}
return 0;
}
void push(char elem)
{
++top;
s[top]= elem;
}
int pop()
{
char elem;
elem= s[top];
–top;
return(elem);
}
11./* Write a program to
evaluate a postfix expression 5 3
+ 8 2 – * */
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#define MAX 100
int s[MAX], top= -1;
int main()
{
char expression[]= “(2 3 + 4 *)”;
int result= evaluate(expression);
printf(“result=%d\n”, result);
return 0;
}
void push(int item)
{
if(top >= MAX -1)
{ printf(” stack
overflow\n”);
return ;
}
top++;
s[top]= item;
}
int pop()
{
int item;
if(top < 0)
{
printf(“stack underflow\n”);
return -1;
}
item = s[top];
top–;
return item;
}
int is_operator(char
symbol)
{
if (symbol== ‘+’ ||
symbol== ‘-‘ || symbol == ‘*’ || symbol== ‘/’)
{ return 1;
}
return 0;
}
int evaluate(char*
expression)
{
int i=0;
char symbol=
expression[i];
int op1, op2, res;
while(symbol!=’\0′)
{
if(symbol >=’0′
&& symbol<= ‘9’)
{
int num= symbol –
‘0’;
push(num);
}
else
if(is_operator(symbol))
{
op2= pop();
op1 = pop();
switch(symbol)
{
case ‘+’: res= op1 +
op2;
break;
case ‘-‘: res= op1 –
op2;
break;
case ‘*’: res= op1 *
op2;
break;
case ‘/’: res= op1 /
op2;
break;
}
push(res);
} i++;
symbol=
expression[i];
}
res= pop();
return res;
}
12./* WAP to create Binary tree with elements
18,15,40,50,30,17,41 and insert 45,19 delete 15,17,41. display the tree on each
insert & delete operation.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *left, *right;
};
typedef struct node NODE;
NODE *root= NULL;
void create(int item)
{
NODE *newnode, *currptr, *ptr;
newnode= (NODE *)malloc (sizeof(NODE));
newnode ->info= item;
newnode ->left= NULL;
newnode ->right= NULL;
if(root==NULL)
root= newnode;
else
{ currptr= root;
while(currptr !=NULL)
{ ptr= currptr;
currptr= (item> currptr-> info) ? currptr->right:
currptr->left;
}
if(item< ptr->info)
ptr->left= newnode;
else
ptr-> right= newnode;
} }
int disp(struct node *ptr, int level)
{
int i;
if(ptr!=NULL)
{
disp(ptr->right, level+1);
for(i=0;i<level;i++)
printf(”
“);
printf(“%2d\n”, ptr->info);
disp(ptr->left, level+1);
} return 0;
}
NODE *getInsuccessor(NODE *ptr)
{
while(ptr ->left!= NULL)
ptr= ptr -> left;
return ptr;
}
NODE *deletion(NODE *p, int item)
{
NODE *temp;
if(!p)
{ printf(” unable to delete, no key ele\n”);
return p;
}
else if(item> p ->info)
p ->right = deletion(p -> right, item);
else if(item< p ->info)
p->left = deletion(p-> left, item);
else
{ if(p ->left==NULL)
{ temp= p->right;
free(p);
return temp;
}
else if(p ->right==NULL)
temp= p-> left;
free(p);
return temp;
}
temp= getInsuccessor(p->right);
p->info= temp->info;
p->right= deletion(p->right, temp->info);
return p;
}
void main()
{
int item, ch, n,i;
clrscr();
while(1)
{
printf(” binary tree \n”);
printf(” 1.insert, 2.delete, 3.display,
4.exit \n”);
printf(” enter the choice\n”);
scanf(“%d”, &ch);
switch(ch)
{
case 1: printf(” enter no. of nodes\n”);
scanf(“%d”, &n);
for(i=0;i<n;i++)
{ printf(” enter element of node\n”);
scanf(“%d”, &item);
create(item);
} break;
case 2: printf(” enter item to be deleted\n”);
scanf(“%d”, &item);
root= deletion(root, item);
disp(root, 1);
break;
case 3: printf(” binary tree nodes are\n”);
disp(root, 1);
break;
case 4: exit(1);
} } }
13/* Write a program
to create binary search tree with elements{2,5,1,3,9,0,6} & perform inorder, preorder & postorder
traversal.*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *left, *right;
};
typedef struct node NODE;
NODE *root= NULL;
void create(int item)
{
NODE *newnode, *currptr, *ptr;
newnode= (NODE *)malloc (sizeof(NODE));
newnode ->info= item;
newnode ->left= NULL;
newnode ->right= NULL;
if(root==NULL)
root= newnode;
else
{ currptr= root;
while(currptr !=NULL)
{ ptr= currptr;
currptr= (item> currptr-> info) ? currptr->right:
currptr->left;
}
if(item< ptr->info)
ptr->left= newnode;
else
ptr-> right= newnode;
} }
int display(struct node *ptr, int level)
{
int i;
if(ptr!=NULL)
{
display(ptr->right, level+1);
for(i=0;i<level;i++)
printf(”
“);
printf(“%2d\n”, ptr->info);
display(ptr->left, level+1);
} return 0;
}
void pre_order(NODE *ptr)
{
if(ptr)
{ printf(”
%d”, ptr-> info);
pre_order(ptr-> left);
pre_order(ptr-> right);
} }
void in_order(NODE * ptr)
{
if(ptr)
{
in_order(ptr->left);
printf(“%d”, ptr->info);
in_order(ptr->right);
} }
void post_order(NODE *ptr)
{
if(ptr)
{
post_order(ptr->left);
post_order(ptr->right);
printf(“%d”, ptr->info);
} }
void main()
{
int item, ch, n,i;
clrscr();
while(1)
{
printf(” BST is\n”);
printf(“1. create, 2.display, 3.preordr, 4.inorder,
5.postorder, 6.exit \n”);
scanf(“%d”, &ch);
switch(ch)
{
case 1:printf(” enter no. of nodes\n”);
scanf(“%d”, &n);
for(i=0;i<n;i++)
{ printf(” enter element of node\n”);
scanf(“%d”, &item);
create(item);
} break;
case 2: printf(” binary tree nodes are\n”);
display(root, 1);
break;
case 3: printf(” preorder traversal \n”);
pre_order(root);
break;
case 4:printf(” inorder traversal \n”);
in_order(root); break;
case 5: printf(” postorder traversal \n”);
post_order(root);
break;
case 6: exit(0);
}
getch();
}
}
14./* Write a program to perform Heap sort {9,16,32,8,4,1,5,8,0}
#include<stdio.h>
#include<conio.h>
void heapify(int arr[], int n, int i)
{
int largest= i;
int left= 2*i+1;
int right= 2*i+2;
int temp;
if(left< n && arr[left] > arr[largest])
largest= left;
if(right< n && arr[right] > arr[largest])
largest= right;
if(largest!=i)
{ temp= arr[i];
arr[i]= arr[largest];
arr[largest]= temp;
heapify(arr, n, largest);
} }
void heapsort(int arr[], int n)
{
int i, temp;
for(i= n/2-1;i>=0;i–)
heapify(arr, n, i);
for(i=n-1;i>=0;i–)
{ temp= arr[0];
arr[0]= arr[i];
arr[i]= temp;
heapify(arr, i, 0);
} }
int main()
{
int arr[20];
int n,i;
clrscr();
printf(“enter the size of array\n”);
scanf(“%d”, &n);
printf(” enter the array elements\n”);
for(i=0;i<n;i++)
scanf(“%d”,&arr[i]);
heapsort(arr,n);
printf(” sorted array is\n”);
for(i=0;i<n;i++)
printf(“%d\t”, arr[i]);
getch();
return 0;
}
