competitioncrackers.com

RANDOMIZED ALGORITHM

RANDOMIZED ALGORITHMAIM
To write a C program to implement randomized algorithm
ALGORITHM:
Step 1: Start the program
Step 2: Gives the input of some random numbers
Step 3: During the execution make some random choices
Step 4: Find the smallest and largest numbers of the input by randomly
Step 5: Print the output
Step 6: Stop the program
PROGRAM:

#include <stdio.h>
#include <stdlib.h> /* required for randomize () and random () */
#include <conio.h> /* required for clrscr() */
int gen_rand(void); /* note these are declarations of functions */
int find_max(int x, int y, int z);
int find_min(int x, int y, int z);
void main(void)
{
int num1, num2, num3, max, min;
clrscr(); /* clear the screen */
num1=gen_rand();
num2=gen_rand();
num3=gen_rand();
max=find_max(num1, num2, num3);
min=find_min(num1, num2, num3);
printf("Random numbers are %d, %d, and %d\n", num1, num2, num3);
printf("Largest is %d. Smallest is %d.\n", max, min);
}
int gen_rand(void)
/* returns random number in range of 0 to 99 */
{
int n;
n=random(100); /* n is random number in range of 0 - 99 */
return(n);
}
int find_max( int x, int y, int z)
/* returns largest number */
{
int max;
if ((x>=y) && (x>=z))
{
max = x;
}
else if ((y>=x) && (y>=z))
{
max = y;
}
else
{
max = z;
}
return(max);
}
int find_min( int x, int y, int z)
/* returns smallest number */
{
int min;
if ((x<=y) && (x<=z))
{
min = x;
}
else if ((y<=x) && (y<=z))
{
min = y;
}
else
{
min = y;
}
return(min);
}
OUTPUT
Random numbers are 1, 0, and 33
Largest is 33. Smallest is 0.

BRANCH AND BOUND ALGORITHM FOR TRAVELLING SALESPERSON PROBLEM

BRANCH AND BOUND ALGORITHM FOR TRAVELLING SALESPERSON PROBLEM

To write a C program to implement traveling sales man problem.
ALGORITHM:
Step 1: Start the program.
Step 2: First, find out all (n -1)! Possible solutions, where n is the number of cities.
Step 3: Determine the minimum cost by finding out the cost of everyone of these (n -1)! solutions
Step 4: Finally, keep the one with the minimum cost.
Step 5: Stop the program
PROGRAM:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
int n;
int a[10][10],list[20],bpath[20];
int i,j,bcost,tbcost;
void get();
void initialize();
void calc(int list[]);
void swap(int x,int y);
void perm(int,int);
void display();
void get()
{
printf("Enter the number of cities:");
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i!=j)
{
if(a[i][j]==-1)
{
printf("Enter the cost travelling from %d to %d is",i+1,j+1);
scanf("%d",&a[i][j]);
a[j][i]=a[i][j];
}
}
else a[i][j]=0;
}
for(i=0;i<n;i++)
list[i]=i;
}
void initialize()
{
for(i=0;i<10;i++)
for(j=0;j<10;j++)
a[i][j]=-1;
bcost=0;
}
void calc(int list[])
{
int t;
tbcost=0;
for(j=1;j<n;j++)
{
t=a[list[j-1]][list[j]];
if(t!=0)
tbcost=tbcost+a[list[j-1]][list[j]];
else
tbcost=bcost+1;
}
}
void swap(int x, int y)
{
int temp;
temp=x;
x=y;
y=temp;
}
void perm(int k,int m)
{
int temp,i,j;
if(k==m)
{
calc(list);
if(bcost==0)
bcost=tbcost+1;
if((tbcost<bcost)&&(a[0][list[n-1]])!=0)
{
bcost=tbcost;
for(j=0;j<n;j++)
bpath[j]=list[j];
}
}
else
{
for(i=k;i<=m;i++)
{
swap(list[k],list[i]);
perm(k+1,m);
swap(list[k],list[i]);
}
}
}
void display()
{
printf("The best path is: \n");
for(i=0;i<n;i++)
printf("%d --> ",bpath[i]+1);
printf("\nThe cost is %d ",bcost+a[0][bpath[n-1]]);
}
void main()
{
clrscr();
initialize();
get();
perm(1,n-1);
display();
getch();
}
OUTPUT
Enter the number of cities: 3
Enter the cost travelling from 1 to 2 is10
Enter the cost travelling from 1 to 3 is15
Enter the cost travelling from 2 to 3 is20
The best path is:
1 --> 2 --> 3 -->
The cost is 45

BACKTRACKING ALGORITHM – KNAPSACK PROBLEM

BACKTRACKING ALGORITHM – KNAPSACK PROBLEM

To write a C program to solve the knapsack problem using backtracking algorithm
ALGORITHM:
Step 1: Declare the variables, array size and functions
Step 2: Get the value of number of objects and size of knapsack
Step 3: Enter weight and profit of objects
Step 4: Assign the initial values
Step 5: Call the necessary function and display the profit
Step 6: End of program
PROGRAM:

#include<stdio.h>
#include<conio.h>
int c,cl,n,i,j,k;
int q[10],x[10][10],w[10],p[10],max;
void get();
void knapsack();
void display();
void get()
{
printf("Enter the number of objects:");
scanf("%d",&n);
printf("Enter the size of knapsack: ");
scanf("%d",&c);
printf("\nEnter the weight & profit of the objects\n");
for(i=1;i<=n;i++)
{
printf("Enter the weight %d:",i);
scanf("%d",&w[i]);
printf("\nEnter the profit of weight %d:",i);
scanf("%d",&p[i]);
}
}
void knapsack()
{
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
{
x[j][i]=0;
q[j]=0;
}
cl=c;
for(i=j;i<=n&&w[i]<=cl;i++)
{
x[j][i]=1;
cl=cl-w[i];
q[j]=q[j]+x[j][i]*p[i];
}
}
max=q[1];
for(i=1;i<=n;i++)
{
if(q[i]>max)
{
max=q[i];
k=i;
}
}}
void display()
{
printf("The optimal solution \t Profit \n");
for(i=1;i<=n;i++)
{
printf("\n");
for(j=1;j<=n;j++)
{
printf("%d\t",x[i][j]);
}
printf("%d\t",q[i]);
}
printf("\nThe maximum Profit is: %d",max);
}
void main()
{
clrscr();
get();
knapsack();
display();
getch();
}
OUTPUT
Enter the number of objects: 3
Enter the size of knapsack: 100
Enter the weight & profit of the objects
Enter the weight 1:60
Enter the profit of weight 1:30
Enter the weight 2:30
Enter the profit of weight 2:20
Enter the weight 3:10
Enter the profit of weight 3:10
The optimal solution Profit
1 1 1 60
0 1 1 30
0 0 1 10
The maximum Profit is: 60

PRIMS ALGORITHM

PRIMS ALGORITHM

To implement prim’s algorithm
ALGORITHM:
Step 1: Get the no of vertex in the graph
Step 2: Get the edge details from the user i.e from which source to which destination edge is present
Step 3: Get which algorithm to perform
i) If prims call prims algorithm display the result exit from the process
Step 4: continue to step-1 till the user request
Step 5: Exit from the process
PROGRAM:

#include<conio.h>
#include<stdio.h>
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999
struct node
{
int predecessor;
int dist; /*Distance from predecessor */
int status;
};
struct edge
{
int u;
int v;
};
int adj[MAX][MAX];
int n;
create_graph();
display();
maketree(struct edge tree[MAX] , int *);
all_perm(struct node state[MAX]);
main()
{
int i;
//int path[MAX];
int wt_tree,count;
struct edge tree[MAX];
create_graph();
printf("Adjacency matrix is :\n");
display();
count = maketree(tree,&wt_tree);
printf("Weight of spanning tree is : %d\n", wt_tree);
printf("Edges to be included in spanning tree are : \n");
for(i=1;i<=count;i++)
{
printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
return(0);
}
create_graph()
{
int i,max_edges,origin,destin,wt;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1)/2;
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d(0 0 to quit) : ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin > n || destin > n || origin<=0 || destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
{
adj[origin][destin]=wt;
adj[destin][origin]=wt;
}
}/*End of for*/
if(i<n-1)
{
printf("Spanning tree is not possible\n");
}
return(0);
}
display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%3d",adj[i][j]);
printf("\n");
}
return(0);
}
int maketree(struct edge tree[MAX],int *weight)
{
struct node state[MAX];
int i,min,count,current;
//int m;
int u1,v1;
*weight=0;
/*Make all nodes temporary*/
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].dist = infinity;
state[i].status = TEMP;
}
/*Make first node permanent*/
state[1].predecessor=0;
state[1].dist = 0;
state[1].status = PERM;
/*Start from first node*/
current=1;
count=0; /*count represents number of nodes in tree */
while( all_perm(state) != TRUE ) /*Loop till all the nodes become
PERM*/
{
for(i=1;i<=n;i++)
{
if ( adj[current][i] > 0 && state[i].status == TEMP )
{
if( adj[current][i] < state[i].dist )
{
state[i].predecessor = current;
state[i].dist = adj[current][i];
}
}
}/*End of for*/
/*Search for temporary node with minimum distance
and make it current node*/
min=infinity;
for(i=1;i<=n;i++)
{
if(state[i].status == TEMP && state[i].dist < min)
{
min = state[i].dist;
current=i;
}
}/*End of for*/
state[current].status=PERM;
/*Insert this edge(u1,v1) into the tree */
u1=state[current].predecessor;
v1=current;
count++;
tree[count].u=u1;
tree[count].v=v1;
/*Add wt on this edge to weight of tree */
*weight=*weight+adj[u1][v1];
}/*End of while*/
return (count);
}/*End of maketree()*/
/*This function returns TRUE if all nodes are permanent*/
int all_perm(struct node state[MAX] )
{
int i;
for(i=1;i<=n;i++)
if( state[i].status == TEMP )
return FALSE;
return TRUE;
}/*End of all_perm()*/
OUTPUT
Enter number of vertices: 3
Enter edge 1(0,0 to quit): 1
2
Enter weight for this edge:1
Enter edge 2(0,0 to quit): 2
3
Enter weight for this edge: 4
Enter edge 3(0,0 to quit): 3
1
Enter weight for this edge: 2
Adjacency matrix:
0 1 2
1 0 4
2 4 0
Weight of the spanning tree: 4
Edges to be included in spanning tree are:
1 3
1 2

DIJKSTRA’S ALGORITHM

DIJKSTRA’S ALGORITHM

To write a C program to implement dijikstra’s algorithm to find shortest path.
ALGORITHM:
Step 1: Include all the header files
Step 2: Call allSelected( )
Step 3: Call Shortpath( )
Step 4: Access the functions from main
Step 5: End
ALGORITHM for ALLSELECTED ( ):
Step 1: Initialise i=0
Step 2: Check whether i<max
Step 3: Check whether Selected[i]=0 Return 0
Step 4: Else Return 1
Step 5: Return
ALGORITHM for SHORTPATH ( ):
Step 1: Initialise i=0, Check i<max Distance[i]=INFINITE
Step 2: Assign selected [current].distance [0]=0, Current=0
Step 3: While (!allSelected(Selected)) Perform(Selected[i]= =0) Current=k Selected[current]=1 Print k
PROGRAM:

#include<stdio.h>
#include<conio.h>
#define infinity 999
#define max 10
int G[max][max],Q[max];
int n,path[max],p[max];
int dest,scr,y,z;
void display(int,int);
void main()
{
void buildgraph();
void dijkstra(int,int);
void insert(int,int);
void insertq(int);
int front,rear;
clrscr();
printf(“\nProgram for the shortest path algorithm using priority queue”);
printf(“\nEnter the number of the vertices:”);
scanf(“%d”,&n);
buildgraph();
printf(“\nEnter the source:”);
scanf(“%d”,&scr);
printf(“\nEnter the destination:”);
scanf(“%d”,&dest);
dijkstra(scr,dest);
for(y=1;y<=max;y++)
p[y]=infinity;
printf(“\nThe shortest path is:\n\t”);
display(dest,scr);
printf(“%d”,dest);
getch();
}
void display(int dest,int scr)
{
int z=1;
while(dest>scr)
{
int a;
a=path[dest];
if(a!=scr)
{
p[z]=a;
}
else
{
p[z]=a;
}
++z;
dest=a;
}
for(y=max;y>0;y--)
{
if(p[y]!=infinity)
{
printf(“%d”,p[y]);
}
}
}
void buildgraph()
{
int i,j,v1,v2;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“\nEnter the edge of v%d to v%d:”,i,j);
scanf(“%d”,&G[i][j]);
}
printf(“\n”);
}
}
void insertq(int index)
{
Q[index]=1;
}
void insert(int index,int vertex)
{
path[index]=vertex;
}
void dijkstra(int scr,int dest)
{
int small,dist[10],current,start,new1;
int temp,i,a[10];
void insertq(int);
for(i=0;i<=n;i++)
{
a[i]=0;
dist[i]=infinity;
}
Q[scr]=1;
dist[scr]=0;
current=scr;
while(current!=dest)
{
small=infinity;
start=dist[current];
for(i=1;i<=n;i++)
{
if(Q[i]==0)
{
new1=start+G[current][i];
if(new1<dist[i])
{
dist[i]=new1;
insert(i,current);
}
if(dist[i]<small)
{
small=dist[i];
temp=i;
}
}
}
current=temp;
insertq(current);
}
printf(“\nThe minimum cost is:%d”,small);
}
OUTPUT
Program for the shortest path algorithm using priority queue
Enter the number of the vertices: 3
Enter the edge of v1 to v1:0
Enter the edge of v1 to v2:4
Enter the edge of v1 to v3:5
Enter the edge of v2 to v1:2
Enter the edge of v2 to v2:0
Enter the edge of v2 to v3:3
Enter the edge of v3 to v1:4
Enter the edge of v3 to v2:2
Enter the edge of v3 to v3:0
Enter the source: 1
Enter the destination: 3
The minimum cost is: 5
The shortest path is: 1 3
 

TOPOLOGICAL SORTING

TOPOLOGICAL SORTING
To write a C program to implement topological sort.
ALGORITHM:
Step 1: Start the program
Step 2: Find a vertex with no incoming edges.
Step 3: Delete it along with all the edges outgoing from it.
Step 4: If there are more than one such vertices then break the tie randomly.
Step 5: Note the vertices that are deleted.
Step 6: All these recorded vertices give topologically sorted list.
Step 7: Stop the program.
PROGRAM:

#include<stdio.h>
#define max 20
int n,adj[max][max];
int front=-1,rear=-1,queue[max];
void main()
{
int i,j=0,k;
int topsort[max],indeg[max];
clrscr();
create_graph();
printf("\nThe Adjacency Matrix is ::\n");
display();
for(i=1;i<=n;i++)
{
indeg[i]=indegree(i);
if(indeg[i]==0)
insert_queue(i);
}
while(front<=rear)
{
k=delete_queue();
topsort[j++]=k;
for(i=1;i<=n;i++)
{
if(adj[k][i]==1)
{
adj[k][i]=0;
indeg[i]=indeg[i]-1;
if(indeg[i]==0);
insert_queue(i);
}
}
}
printf("Nodes after topological sorting are ::\n");
for(i=0;i<=n;i++)
{
printf("%d",topsort[i]);
printf("\n");
}
}
create_graph()
{
int i,max_edges,origin,destin;
printf("Enter the number of Vertices::");
scanf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d(0,0 to quit): ",i);
scanf("%d%d",&origin,&destin);
if((origin==0)&&(destin==0))
break;
if(origin>n || destin>n || origin<=0 || destin<=0)
{
printf("Invalid Edge!!!\n");
i--;
}
else
adj[origin][destin]=1;
}
}
display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d",adj[i][j]);
printf("\n");
}
}
insert_queue(int node)
{
if(rear==max-1)
printf("Queue Overflow!!!\n");
else
{
if(front==-1)
front=0;
rear=rear+1;
queue[rear]=node;
}
}
delete_queue()
{
int del_item;
if(front==-1 || front>rear)
{
printf("Queue Overflow!!!\n");
return;
}
else
{
del_item=queue[front];
front=front+1;
return del_item;
}
}
int indegree(int node)
{
int i,in_deg=0;
for(i=1;i<=n;i++)
if(adj[i][node]==1)
in_deg++;
return in_deg;
}
OUTPUT
Enter the number of Vertices::7
Enter edge 1(0,0 to quit): 1 2
Enter edge 2(0,0 to quit): 1 3
Enter edge 3(0,0 to quit): 1 4
Enter edge 4(0,0 to quit): 4 3
Enter edge 5(0,0 to quit): 2 4
Enter edge 6(0,0 to quit): 2 5
Enter edge 7(0,0 to quit): 3 6
Enter edge 8(0,0 to quit): 4 6
Enter edge 9(0,0 to quit): 4 7
Enter edge 10(0,0 to quit): 5 4
Enter edge 11(0,0 to quit): 5 7
Enter edge 12(0,0 to quit): 7 6
Enter edge 13(0,0 to quit): 0 0
The Adjacency Matrix is:
0111000
0001100
0000010
0010011
0001001
0000000
0000010
Nodes after topological sorting are:
1
2
5
4
3
7
6

HASHING TECHNIQUES

HASHING TECHNIQUES

To implement hashing using Open Addressing
ALGORITHM:
Step 1: Get the Hash Size
Step 2: Get the element to placed inside the Hash Table perform open hashing place the element in the
particular position chain
Step 3: If the element is already in particular index, find next Empty Space
Step 4: If index is HashSize-1 then Index becomes 0.
Step 5: Continue step-2 till the user request otherwise exit from the process.
PROGRAM:

#include <stdio.h>
#include <conio.h>
#define HSIZE 7
void main()
{
int key[10],H[HSIZE]={0,0,0,0,0,0,0},hash[10],hash1,i,j,n;
clrscr();
printf("Enter no of elements:\n");
scanf("%d",&n);
printf("Enter Key values:\n");
for(j=0;j<n;j++)
{
scanf("%d",&key[j]);
}
printf("output:\n");
printf("Index\t\tHashtablevalue:\n");
printf("------------------------:\n");
for(j=0;j<n;j++)
{
hash[j]=key[j]%HSIZE;
hash1=hash[j];
printf("Index=%d\n",hash1);
if(H[hash1]==0)
{
H[hash1]=key[j];
}
else
{
if(hash1==HSIZE-1)
hash1=0;
for(i=hash1;i<HSIZE;i++)
{
if(H[i]==0)
{
H[i]=key[j];
break;
}
}
}
}
for(i=0;i<HSIZE;i++)
{
printf("%d\t\t%d\n",i,H[i]);
}
getch();
}

OUTPUT
Enter no of elements:
5
Enter Key values:
18
72
65
34
13
Index Hashtablevalue:
------------------------:
Index=4
Index=2
Index=2
Index=6
Index=6
0 13
1 0
2 72
3 65
4 18
5 0
6 34

QUEUE USING BINARY HEAPING

QUEUE USING BINARY HEAPING
To implement binary heap
ALGORITHM:Step 1: Get the choice which ADT to perform
i) If insert get the element to be inserted and pass it to insert function
ii) If delete call delete function
iii) If search get the element to be searched and pass it so search function
iv) If display call the display function
Step 2: Continue step 1 till the user request
Step 3: Exit from the process if the user don’t want to continue step 3
PRIORITY QUEUE:
PROGRAM

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<alloc.h>
insert();
del();
display();
struct node
{
int priority;
int info;
struct node *link;
}*front = NULL;
main()
{
int choice;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
default :
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
insert()
{
struct node *tmp,*q;
int added_item,item_priority;
tmp = (struct node *)malloc(sizeof(struct node));
printf("Input the item value to be added in the queue : ");
scanf("%d",&added_item);
printf("Enter its priority : ");
scanf("%d",&item_priority);
tmp->info = added_item;
tmp->priority = item_priority;
/*Queue is empty or item to be added has priority more than first
item*/
if( front == NULL || item_priority < front->priority )
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while( q->link != NULL && q->link->priority <= item_priority )
q=q->link;
tmp->link = q->link;
q->link = tmp;
}
return(0);
}
del()
{
struct node *tmp;
if(front == NULL)
printf("Queue Underflow\n");
else
{
tmp = front;
printf("Deleted item is %d\n",tmp->info);
front = front->link;
free(tmp);
}
return(0);
}
display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
printf("Queue is empty\n");
else
{ printf("Queue is :\n");
printf("Priority Item\n");
while(ptr != NULL)
{
printf("%5d %5d\n",ptr->priority,ptr->info);
ptr = ptr->link;
}
}
return(0);
}

OUTPUT
Enter your choice : 1
Input the item value to be added in the queue : 4
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 5
Enter its priority : 2
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 6
Enter its priority : 4
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority Item
1 2
2 5
3 4
4 6
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 2
Deleted item is 2
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority Item
2 5
3 4
4 6
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 4

AVL TREE

AVL TREE

To implement AVL Rotations
ALGORITHM:

Step 1: Get the element to be inserted
Step 2: Pass the element to be inserted to the add procedure which in turn invokes insert procedure and
places the element in correct position by maintaining the height factor
Step 3: Continue step-1 till the user request otherwise exit from the process.

PROGRAM:

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<alloc.h>
typedef enum { FALSE ,TRUE } bool;
struct node
{
int info;
int balance;
struct node *lchild;
struct node *rchild;
};
struct node *insert (int , struct node *, int *);
struct node* search(struct node *,int);
inorder(struct node *);
display(struct node *,int n);
main()
{
int ht_inc;
int info ;
int choice;
struct node *root = (struct node *)malloc(sizeof(struct node));
root = NULL;
while(1)
{
printf("1.Insert\n");
printf("2.Display\n");
printf("3.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the value to be inserted : ");
scanf("%d", &info);
if( search(root,info) == NULL )
root = insert(info, root, &ht_inc);
else
III SEM EEE EE2209-Data Structures and Algorithms
37
printf("Duplicate value ignored\n");
break;
case 2:
if(root==NULL)
{
printf("Tree is empty\n");
continue;
}
printf("Tree is :\n");
display(root, 1);
printf("\n\n");
printf("Inorder Traversal is: ");
inorder(root);
printf("\n");
break;
case 3:
exit(1);
default:
printf("Wrong choice\n");
}
}
}
struct node* search(struct node *ptr,int info)
{
if(ptr!=NULL)
if(info < ptr->info)
ptr=search(ptr->lchild,info);
else if( info > ptr->info)
ptr=search(ptr->rchild,info);
return(ptr);
}/*End of search()*/
struct node *insert (int info, struct node *pptr, int *ht_inc)
{
struct node *aptr;
struct node *bptr;
if(pptr==NULL)
{
pptr = (struct node *) malloc(sizeof(struct node));
pptr->info = info;
pptr->lchild = NULL;
pptr->rchild = NULL;
pptr->balance = 0;
*ht_inc = TRUE;
return (pptr);
}
if(info < pptr->info)
{
pptr->lchild = insert(info, pptr->lchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case -1: /* Right heavy */
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0: /* Balanced */
pptr->balance = 1;
break;
case 1: /* Left heavy */
aptr = pptr->lchild;
if(aptr->balance == 1)
{
printf("Left to Left Rotation\n");
pptr->lchild= aptr->rchild;
aptr->rchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf("Left to right rotation\n");
bptr = aptr->rchild;
aptr->rchild = bptr->lchild;
bptr->lchild = aptr;
pptr->lchild = bptr->rchild;
bptr->rchild = pptr;
if(bptr->balance == 1 )
pptr->balance = -1;
else
pptr->balance = 0;
if(bptr->balance == -1)
aptr->balance = 1;
else
aptr->balance = 0;
bptr->balance=0;
pptr=bptr;
}
*ht_inc = FALSE;
}/*End of switch */
}/*End of if */
}/*End of if*/
if(info > pptr->info)
{
pptr->rchild = insert(info, pptr->rchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case 1: /* Left heavy */
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0: /* Balanced */
pptr->balance = -1;
break;
case -1: /* Right heavy */
aptr = pptr->rchild;
if(aptr->balance == -1)
{
printf("Right to Right Rotation\n");
pptr->rchild= aptr->lchild;
aptr->lchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf("Right to Left Rotation\n");
bptr = aptr->lchild;
aptr->lchild = bptr->rchild;
bptr->rchild = aptr;
pptr->rchild = bptr->lchild;
bptr->lchild = pptr;
if(bptr->balance == -1)
pptr->balance = 1;
else
pptr->balance = 0;
if(bptr->balance == 1)
aptr->balance = -1;
else
aptr->balance = 0;
bptr->balance=0;
pptr = bptr;
}/*End of else*/
*ht_inc = FALSE;
}/*End of switch */
}/*End of if*/
}/*End of if*/
return(pptr);
}/*End of insert()*/
display(struct node *ptr,int level)
{
int i;
if ( ptr!=NULL )
{
display(ptr->rchild, level+1);
printf("\n");
for (i = 0; i < level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}
return(0);
}
inorder(struct node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf("%d ",ptr->info);
inorder(ptr->rchild);
}
return(0);
}
OUTPUT
1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 10
Right to Right Rotation
1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 12
Right to Right Rotation
1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 14
Right to Right Rotation
1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 16
1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 18
Right to Right Rotation
1.Insert
2.Display
3.Quit
Enter your choice : 2
Tree is :
18
16
14
12
10
8
6
4
2
Inorder Traversal is: 2 4 6 8 10 12 14 16 18
1.Insert
2.Display
3.Quit
Enter your choice : 3