Stack

typedef struct stack
{
char data;
struct stack *next;
} stack;
void init(stack **T)
{
*T=NULL;
}
int empty(stack *TOP)
{
if(TOP==NULL)
return(1);
return(0);
}
void push(stack **T,char x)
{
stack *P;
P=(stack *)malloc(sizeof(stack));
P->data=x;
P->next=*T;
*T=P;
}
char pop(stack **T)
{
char x;
stack * P;
P=*T;
*T=P->next;
x=P->data;
free(P);
return(x);
}
void print(stack *p)
 { printf("\n");
  while(p!=NULL)
   {printf("%c  ",p->data);
    p=p->next;
   }
}

Stack

#define MAX 10
typedef struct stack
{
char data[MAX];
int top;
}stack;
void init(stack *s)
{ s->top=-1;
}

int empty(stack *s)
{ if(s->top==-1)
return(1);
return(0);
}

int full(stack *s)
{ if(s->top==MAX-1)
return(1);
return(0);
}

void push(stack *s,char x)
{
s->top=s->top+1;
s->data[s->top]=x;
}

char pop(stack *s)
{
char x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}
void print(stack *s)
  { int i;
    printf("\n");
    for(i=s->top;i>=0;i--)
       printf("%c  ",s->data[i]);
  }

Minimum cost spanning tree

/* Program for constructing a minimum cost spanning tree  */

#define infinity 9999
#define MAX 20
#include<stdio.h>
#include<stdlib.h>
int G[MAX][MAX],spanning[MAX][MAX],n;

/**** Functions and structures used for Kruskal's Algorithm */
typedef struct edge
{ int u,v,w;
}edge;

typedef struct edgelist
 { edge data[30];
   int n;
 }edgelist;
edgelist elist,spanlist;
int find(int belongs[],int vertexno);
void sort();
void union1(int belongs[],int c1,int c2); //merging of two components
void print();
void kruskal();

int main()
{
int i,j,op;
do {
   printf("\n\n1)Create\n2)Kruskal\n3)Quit");
   printf("\nEnter Your Choice : ");
   scanf("%d",&op);
   switch(op)
    { case 1:
     printf("\nEnter No. of vertices : ");
     scanf("%d",&n);
     printf("\nEnter the adjacency matrix :");
     for(i=0;i<n;i++)
for(j=0;j<n;j++)
 scanf("%d",&G[i][j]);
      break;
case 2: kruskal();break;

     }
}while(op!=3);
}
void kruskal()
{  int belongs[MAX],i,j,cno1,cno2;
   /*create a list of edges */
   elist.n=0;
   for(i=0;i<n;i++)
     for(j=0;j<n;j++)
       if(G[i][j]!=0)
{ elist.data[elist.n].u=i;
  elist.data[elist.n].v=j;
  elist.data[elist.n].w=G[i][j];
  elist.n++;
}
   sort();
 // create the spanning tree with n components
 for(i=0;i<n;i++)
    belongs[i]=i;
 spanlist.n=0;
 // add edges one by one to spanning tree
 for(i=0;i<elist.n;i++)
  { cno1=find(belongs,elist.data[i].u);
    cno2=find(belongs,elist.data[i].v);
    if(cno1 != cno2) // if the edge does not cause a cycle
      { spanlist.data[spanlist.n++]=elist.data[i];
union1(belongs,cno1,cno2);
      }
   }
 //print the spanning tree
  print();
}

int find(int belongs[] ,int vertexno)
 { return(belongs[vertexno]);
 }

void union1(int belongs[], int c1 , int c2)
 { int i;
   for(i=0;i<n;i++)
    if(belongs[i]==c2) // merge two components
      belongs[i]=c1;
 }
void sort()
 { int i,j;
   edge temp;
   for(i=1;i<elist.n;i++)
     for(j=0;j<elist.n-i;j++)
       if(elist.data[j].w > elist.data[j+1].w)
 { temp=elist.data[j];
   elist.data[j]=elist.data[j+1];
   elist.data[j+1]=temp;
 }
  }

void print()
 { int i,cost=0;
   for(i=0;i<spanlist.n;i++)
     { printf("\n%d - %d cost= %d",spanlist.data[i].u,spanlist.data[i].v,
  spanlist.data[i].w);
       cost=cost+spanlist.data[i].w;
     }
   printf("\nCost of the spanning tree : %d",cost);
}

Minimum cost spanning tree using Prim's algorithm

/* Program for constructing a minimum cost spanning tree using Prim's algorithm */

#define infinity 9999
#define MAX 20
#include<stdio.h>
#include<stdlib.h>
int G[MAX][MAX],n;
void prims();
int main()
{
int i,j,op;
do {
   printf("\n\n1)Create\n2)Prim's\n3)Quit");
   printf("\nEnter Your Choice : ");
   scanf("%d",&op);
   switch(op)
    { case 1:
     printf("\nEnter No. of vertices : ");
     scanf("%d",&n);
     printf("\nEnter the adjacency matrix :");
     for(i=0;i<n;i++)
for(j=0;j<n;j++)
 scanf("%d",&G[i][j]);
      break;
case 2: prims();break;

     }
}while(op!=3);
}
void prims()
{
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
// create cost[][] matrix ,spanning[][]
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];

}
// initialise visited[],distance[] and from[]
distance[0]=0;visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}
min_cost=0;            //cost of spanning tree
no_of_edges=n-1;       //no.of edges to be added
while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0 && distance[i] < min_distance)
{
v=i;
min_distance=distance[i];
}
u=from[v];
printf("\nNext edge in spanning tree is:(%d,%d,%d)",u,v,distance[v]);
no_of_edges--;
visited[v]=1;
// update the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0 && cost[i][v] < distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
min_cost=min_cost+cost[u][v];
}

printf("\nTotal cost of spanning tree=%d",min_cost);
}

Dijkstra's algorith on a graph represented using adjacency list

 /*Dijkstra's algorith on a graph represented using adjacency list*/

#define INFINITY 9999
#include <stdio.h>
#include<stdlib.h>
#define MAX 10

typedef struct node
{
struct node *next;
int vertex,weight;
}node;

node *G[10];//adjacency list
int n;// Number of vertices
void readgraph();
void insert(int vi,int vj,int w);
void dijkstra( int startnode);

int main()
{
int u;
readgraph();
printf("\nEnter the starting node : ");
scanf("%d",&u);
dijkstra(u);

}

void dijkstra( int startnode)
{
int distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,nextnode,i,j;
/*pred[] stores the predecessor of each node
count gives the number of nodes seen so far*/
/* A node picked up for expansion is marked as visited[node no.]=1*/
       //initialize
node *p;
for(i=0;i<n;i++)
  {
distance[i]=INFINITY;
pred[i]=startnode;visited[i]=0;
  }
distance[startnode]=0;
count=0;
while(count<n-1)
  {
mindistance=INFINITY ;
// nextnode is the node at minimum distance
for(i=0;i<n;i++)
if(distance[i] < mindistance && !visited[i])
   {
mindistance=distance[i];
nextnode=i;
   }
//check if a better path exist through nextnode
visited[nextnode]=1;
for(p=G[nextnode];p!=NULL;p=p->next)
if(!visited[p->vertex])
if(mindistance+p->weight<distance[p->vertex])
   {
distance[p->vertex]=mindistance+p->weight;
pred[p->vertex]=nextnode;
   }
count++;
  }

 //print the path and distance of each node
for(i=0;i<n;i++)
if(i!=startnode)
  {
printf("\n Distance of %d = %d ",i,distance[i]);
printf("       Path = %d ",i);
j=i;
do
  {
j=pred[j];
printf("<- %d ",j);
  }while(j!=startnode);
  }

}

void readgraph()
{ int i,j;
int adj[10][10];
printf("\nEnter no. of vertices :");
scanf("%d",&n);
printf("\nEnter Adjacency matrix :\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&adj[i][j]);
//initialise G[] with NULL
for(i=0;i<n;i++)
G[i]=NULL;

for(i=0;i<n;i++) //create adjacency list
for(j=0;j<n;j++)
      if(adj[i][j]!=0)
  insert(i,j,adj[i][j]);

}

void insert(int vi,int vj,int w)
{
node *p,*q;
//acquire memory for the new node
q=(node *)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
q->weight=w;
//insert the node in the linked list for the vertex no. vi
if(G[vi]==NULL)
G[vi]=q;
else
{
// go to the end of linked list
p=G[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}

Orthogonal list representation of a graph

/*Orthogonal list representation of a graph */

#include <stdio.h>
#include<stdlib.h>
typedef struct node
 {
int  u,v;
struct  node *next,*down;
 }node;

 node *rows[10],*cols[10];
 int nodecount=0;

 void insert(node *p)
   {
     //address of the node to be inserted is in p
     node *q;
     //insert the node pointed by p in the linked list of the row
     q=rows[p->u];//head of the linked list for the row to be used for insertion
     if(q==NULL || p->u < q->u)//first node
     {
p->next=q;
rows[p->u]=p;
     }
     else
     {
    //Locate the point of insertion
    while(q->next != NULL && p->u > q->next->u)
    q=q->next;

    p->next=q->next;
    q->next=p;

     }



 //insert the node pointed by p in the linked list of the column
     q=cols[p->v];//head of the linked list for the column to be used for insertion
     if(q==NULL || p->v < q->v)//first node
     {
p->down=q;
cols[p->v]=p;
     }
     else
     {
    //Locate the point of insertion
    while(q->down != NULL && p->v > q->down->v)
    q=q->down;

    p->down=q->down;
    q->down=p;

     }
  }


 int main()
   {
int edgecount=0,i,j,k;
node *p;
printf("\nEnter No of vertices : ");
scanf("%d",&nodecount);
for(i=0;i<nodecount;i++)
   rows[i]=cols[i]=NULL;
printf("\nEnter No. of edges  : ");
scanf("%d",&edgecount);
printf("\nEnter edges as (u,v) pair : ");
for(i=0;i<edgecount;i++)
 {     fflush(stdin);
p=(node*)malloc(sizeof(node));
scanf("%d%d",&p->u,&p->v);
p->next=p->down=NULL;
insert(p);
 }
//display the list
 printf("\nList(Row-wise):");

  for(i=0;i<nodecount;i++)
      {
printf("\nRow=%d",i);
for(p=rows[i];p!=NULL;p=p->next)
printf(" (%d,%d)",p->u,p->v);
      }
 printf("\n\nList(Column-wise):");

  for(i=0;i<nodecount;i++)
      {
printf("\nColumn=%d",i);
for(p=cols[i];p!=NULL;p=p->down)
printf(" (%d,%d)",p->u,p->v);
      }

  return(0);
}

Multi list representation of a graph

/*Multi list representation of a graph */
#include <stdio.h>
typedef struct edge
 {
char u,v;
int next;
 }edge;

 int main()
   {
edge list[10];
int edgecount=0,nodecount,i,j,k;
char heads[10][2];
printf("\nEnter No of vertices : ");
scanf("%d",&nodecount);
printf("\nEnter the name of each node(A,B....) : ");
for(i=0;i<nodecount;i++)
  {    fflush(stdin);
scanf("%c",&heads[i][0]);
      // heads[i][0]=getchar();
fflush(stdin);
heads[i][1]=-1;
  }
printf("\nEnter No. of edges  : ");
scanf("%d",&edgecount);

printf("\nEnter edges as (u,v) pair : ");
for(i=0;i<edgecount;i++)
 {     fflush(stdin);
scanf("%c%c",&list[i].u,&list[i].v);
list[i].next=-1;
 }
   //creation of multilist
for(i=0;i<nodecount;i++)
 {
j=0;
while( j < edgecount && heads[i][0] != list[j].u)
    j++;
if(j<edgecount)
 {
heads[i][1]=j;
for(k=j+1;k<edgecount;k++)
 {
if(list[k].u==list[j].u)
    {
list[j].next=k;
j=k;
    }
 }
  }
  }

//display the headers
printf("\nHeaders\n" );
for(i=0;i<nodecount;i++)
       printf("\n%c  %d",heads[i][0],heads[i][1]);
printf("\nAdjacency list(u,v,next): \n");
for(i=0;i<edgecount;i++)
       printf("\n%c  %c  %d ",list[i].u,list[i].v,list[i].next);
return(0);
}

SFS and BFS on Graph

/*DFS and BFS on graph represented using adjacency list */

#include<stdio.h>
#include<stdlib.h>
#define MAX 20

typedef struct Q
{
int data[MAX];
int R,F;
}Q;

typedef struct node
{
struct node *next;
int vertex;
}node;

void enqueue(Q *,int);
int dequque(Q *);
int empty(Q *);
int full(Q *);
void BFS(int);
void readgraph();     //create an adjecency list
void insert(int vi,int vj);     //insert an edge (vi,vj)in adj.list
void DFS(int i);
int visited[MAX];
node *G[20];         //heads of the linked list
int n;               // no of nodes

int main()
{
int i,op;
do
 { printf("\n\n1)Create\n2)BFS\n3)DFS\n4)Quit");
   printf("\nEnter Your Choice: ");
   scanf("%d",&op);
   switch(op)
    { case 1: readgraph();break;
      case 2: printf("\nStarting Node No. : ");
      scanf("%d",&i);
      BFS(i);break;
      case 3:  for(i=0;i<n;i++)
visited[i]=0;
      printf("\nStarting Node No. : ");
      scanf("%d",&i);
      DFS(i);break;
     }
  }while(op!=4);
}


void BFS(int v)
{
int w,i,visited[MAX];
Q q;

node *p;
q.R=q.F=-1;              //initialise
for(i=0;i<n;i++)
visited[i]=0;
enqueue(&q,v);
printf("\nVisit\t%d",v);
visited[v]=1;
while(!empty(&q))
{
v=dequeue(&q);
//insert all unvisited,adjacent vertices of v into queue
for(p=G[v];p!=NULL;p=p->next)
{
w=p->vertex;
if(visited[w]==0)
{
enqueue(&q,w);
visited[w]=1;
printf("\nvisit\t%d",w);
}
}
}
}

void DFS(int i)
{
node *p;
int stack[10],top=-1;
stack[++top]=i;
while(top != -1)
{
i=stack[top--];
if(!visited[i])
   {
visited[i]=1;
printf("%d   ",i);
for(p=G[i];p!=NULL;p=p->next)
if(!visited[p->vertex])
stack[++top]=p->vertex;
   }
}
 }

int empty(Q *P)
{
if(P->R==-1)
return(1);
return(0);
}

int full(Q *P)
{
if(P->R==MAX-1)

return(1);
return(0);
}

void enqueue(Q *P,int x)
{
if(P->R==-1)
{
P->R=P->F=0;
P->data[P->R]=x;
}
else
{
P->R=P->R+1;
P->data[P->R]=x;
}
}

int dequeue(Q *P)
{
int x;
x=P->data[P->F];
if(P->R==P->F)
{
P->R=-1;
P->F=-1;
}
else
P->F=P->F+1;
return(x);
}

void readgraph()
{ int i,j;
int adj[10][10];
printf("\nEnter no. of vertices :");
scanf("%d",&n);
printf("\nEnter Adjacency matrix :\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&adj[i][j]);
//initialise G[] with NULL
for(i=0;i<n;i++)
G[i]=NULL;

for(i=0;i<n;i++) //create adjacency list
for(j=0;j<n;j++)
      if(adj[i][j]!=0)
  insert(i,j);

}

void insert(int vi,int vj)
{
node *p,*q;
//acquire memory for the new node
q=(node *)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
//insert the node in the linked list for the vertex no. vi
if(G[vi]==NULL)
G[vi]=q;
else
{
// go to the end of linked list
p=G[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}

Graph

/*Indegree,Outdegree,total degree of each vertex and,
  BFS , DFS on a graph represented using adjacency matrix*/
#include<stdio.h>
#define MAX 10

typedef struct Q
{
int R,F;
int data[MAX];
}Q;

int empty(Q *P);
int full(Q *P);
void enqueue(Q *P,int x);
int dequeue(Q *P);
void BFS(int);
void DFS(int);
void degrees();
int G[MAX][MAX];
int n=0;
int visited[MAX];

void create()
 {
        int i,j;
printf("\nEnter no of vertices : ");
scanf("%d",&n);
printf("\nEnter the adjecendy matrix of  graph : ");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);

 }


int main()
{
int i,j,v,op;

do{
  printf("\n1)Read the graph");
  printf("\n\n2)DFS\n3)BFS\n4)Indegree/Outdegree/Total degree\n5)QUIT");
  printf("\nEnter Your choice : ");
  scanf("%d",&op);
  switch(op)
   {
     case 1:create();break;
     case 2:printf("\nEnter the starting vertex for DFS : ");
    scanf("%d",&v);
    for(i=0;i<n;i++)
  visited[i]=0;
    DFS(v);break;
     case 3:printf("\nEnter the starting vertex for BFS : ");
    scanf("%d",&v);
    BFS(v);break;

     case 4: degrees();break;

   }
 }while(op!=5);

}

void BFS(int v)
{
int visited[MAX],i;
Q q;
q.R=q.F=-1;
for(i=0;i<n;i++)
 visited[i]=0;
enqueue(&q,v);
printf("\n visit\n",v);
visited[v]=1;
while(!empty(&q))
{
v=dequeue(&q);
// visit and add adjecency vertices
for(i=0;i<n;i++)
if(visited[i]==0 && G[v][i]!=0)
{
enqueue(&q,i);
visited[i]=1;
printf("\n%d",i);
}
}
}

int empty(Q *P)
{
if(P->R==-1)
return(1);
return(0);
}

int full(Q *P)
{
if(P->R==MAX-1)
return(1);
return(0);
}

void enqueue(Q *P,int x)
{
if(P->R==-1)
{
P->R=P->F=0;
P->data[P->R]=x;
}
else
{
P->R=P->R+1;
P->data[P->R]=x;
}
}

int dequeue(Q *P)
{
int x;
x=P->data[P->F];
if(P->R==P->F)
{
P->R=-1;
P->F=-1;
}
else
P->F=P->F+1;
return(x);
}

void DFS(int i)
{
int j;
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j] && G[i][j]==1)
DFS(j);
}
void degrees()
 {
int idegree,odegree,i,j;
for(i=0;i<n;i++)
{
idegree=odegree=0;
for(j=0;j<n;j++)
 {
if(G[i][j]!=0)
odegree++;
if(G[j][i]!=0)
idegree++;
 }
printf("\nvertex : %d\tIndegree :%d\tOut degree:%d\tTotal Degree:%d",i,idegree,odegree,idegree+odegree);
}
 }

Huffman's Algorithm, Huffman Tree

/* Implementation of Huffman's Algorithm
    program for creation of huffman tree
*/
//   (1) trees are maintained in priority linked list,
//       ordered by weight
//   (2) Function insert() is used for inserting a tree
//       in priority linked list */

#include<stdlib.h>
#include<stdio.h>
#include<string.h>

// stucture of tree node
typedef struct treenode
{
float freq;
char data;
struct treenode *left,*right;
}treenode;

/* structure of node of linked list */
typedef struct node
{
treenode *data; //address of tree
struct node *next;
}node;

node *insert(node *,treenode *);
treenode *create();
void encode();
void decode(treenode *);
int n;
char alphabets[30];
char codes[30][10];

void preorder(treenode *p,int i ,char word[])
 {
if(p!=NULL)
  {
if(p->left==NULL && p->right==NULL)
  {
word[i]=0;
printf("\n%c --- %s",p->data,word);
alphabets[n]=p->data;
strcpy(codes[n++],word);
  }
word[i]='0';
preorder(p->left,i+1,word);
word[i]='1';
preorder(p->right,i+1,word);
  }
 }

int main()
 {
int op;char word[10];
treenode *root=NULL;
do
  {
printf("\n\n1)Create Huffman Tree ");
printf("\n2)Encode a Message ");
printf("\n3)Decode a message ");
printf("\n4)Quit");
printf("\nEnter Your Choice : ");
scanf("%d",&op);
switch(op)
  {
case 1: n=0;root=create();
printf("\nPrefix codes : \n");
preorder(root,0,word); // create the encoding sequence
break;
case 2: encode(); break;
case 3: decode(root);break;
  }
  }while(op!=4);
}

treenode *create()
{
treenode *p,*t1,*t2;
node *head;
int n,i;
char x;
float probability;
head=NULL;       //empty linked list
printf("\nEnter No. of alphabets :");
scanf("%d",&n);
for(i=0;i<n;i++)
  {
fflush(stdin);
printf("\nEnter alphabet :");
scanf("%c",&x);
fflush(stdin);
printf("\nEnter frequency :");
scanf("%f",&probability);
 /* create a new tree and insert it in
    the priority linked list */
p=(treenode*)malloc(sizeof(treenode));
p->left=p->right=NULL;
p->data=x;
p->freq=probability;
head=insert(head,p);
 }
/* create the final tree by merging of two trees
  of smaller weights (n-1) merges will be required*/
for(i=1;i<n;i++)
  {
t1=head->data;         //first tree
t2=head->next->data;   //second tree
head=head->next->next; /*remove first 2 trees
from linked list*/
 /*merge t1 and t2 with new tree in P */
p=(treenode *)malloc(sizeof(treenode));
p->left=t1;
p->right=t2;
p->freq=t1->freq+t2->freq;
head=insert(head,p); /*insert the new tree in the linked list*/
  }

return(head->data);
// preorder(head->data);
 //getch();
}

node *insert(node *head,treenode *t)
{
node *p,*q;
p=(node *)malloc(sizeof(node));
p->data=t;
p->next=NULL;
if(head==NULL)  //empty linked list
return(p);
if(t->freq<head->data->freq)
  {
p->next=head;
return(p);
  }
// locate the point of insertion
q=head;
while(q->next!=NULL && t->freq>q->next->data->freq)
q=q->next;
p->next=q->next;
q->next=p;
return(head);
}

void encode()
{
char word[30];int i,j;
fflush(stdin);
printf("\n Enter a Message : ");
gets(word);
printf("\n Encoded Message \n");
for(i=0;word[i]!='\0';i++)
 {
for(j=0;alphabets[j]!=word[i] && j<n;j++);
if(j<n)
printf("%s",codes[j]);
 }
}

void decode(treenode *p)
{
char word[90];int i;treenode *q;
fflush(stdin);
printf("\nEnter an Encoded message : ");
gets(word);
q=p;i=0;
printf("\nDecoded Message = ");
while(word[i]!='\0')
  {
if(word[i]=='0')
q=q->left;
else
q=q->right;
if(q->left==NULL && q->right==NULL)
   {
printf("%c",q->data);
q=p;
   }
i++;
  }

}

AVL Tree

 /*Program for AVL tree */
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{  int data;
   struct node *left,*right;
   int ht;
}node;


  node *insert(node *,int);//Recursive counterpart of insert
  node *Delete(node *,int);//Recursive counterpart of delete
  void  preorder(node *); //Recursive counterpart of preorder
  void  inorder(node *); //Recursive counterpart of inorder
  int   height( node *);
  node *rotateright(node *);
  node *rotateleft(node *);
  node *RR(node *);
  node *LL(node *);
  node *LR(node *);
  node *RL(node *);
  int BF(node *);
int main()
{
node *root=NULL;
int x,n,i,op;
do
{
printf("\n1)Create : ");
printf("\n2)Insert : ");
printf("\n3)Delete : ");
printf("\n4)Print  : ");
printf("\n5)Quit   : ");
printf("\nEnter Your Choice : ");
scanf("%d",&op);
switch(op)
   {
case 1:printf("\nEnter no.of elements :");
      scanf("%d",&n);
      printf("\n Enter tree data :");
      root=NULL;
      for(i=0;i<n;i++)
  {
scanf("%d",&x);
root=insert(root,x);
  }
      break;
case 2:printf("\nEnter a data : ");
      scanf("%d",&x);
      root=insert(root,x);
      break;
case 3:printf("\nEnter a data : ");
      scanf("%d",&x);
      root=Delete(root,x);
      break;
case 4: printf("\nPreorder sequence :\n");
preorder(root);
printf("\nInorder sequence :\n");
inorder(root);
break;
    }

}while(op!=5);

}
node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
if(x > T->data)                // insert in right subtree
{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x < T->left->data)
T=LL(T);
else
T=LR(T);
}
T->ht=height(T);
return(T);
}

node * Delete(node *T,int x)
{       node *p;

if(T==NULL)
{
return NULL;
}
else

if(x > T->data)                // insert in right subtree
{
T->right=Delete(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
if(x<T->data)
{
T->left=Delete(T->left,x);
if(BF(T)==-2)//Rebalance during windup
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
 {
   //data to be deleted is found
     if(T->right !=NULL)
 {  //delete its inorder succesor
     p=T->right;
     while(p->left != NULL)
 p=p->left;

     T->data=p->data;
     T->right=Delete(T->right,p->data);
     if(BF(T)==2)//Rebalance during windup
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
  }
     else
  return(T->left);

 }
T->ht=height(T);
return(T);
}

int height(node *T)
{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return(lh);
return(rh);
}
node * rotateright(node *x)
{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * RR(node *T)
{
T=rotateleft(T);
return(T);
}
node * LL(node *T)
{
T=rotateright(T);
return(T);
}
node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return(T);
}
node * RL(node *T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}
int BF(node *T)
{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
return(lh-rh);
}
void preorder(node *T)
{
if(T!=NULL)
{
printf(" %d(Bf=%d)",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}
void inorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
printf(" %d(Bf=%d)",T->data,BF(T));
inorder(T->right);
}
}

Various operations on binary search tree

// program showing various operations on binary search tree
#include<stdio.h>
#include<stdlib.h>
typedef struct BSTnode
{
int data;
struct BSTnode *left,*right;
}BSTnode;

typedef struct stack
  { BSTnode *data[20];
    int top;
  }stack;

void init(stack *s)
 { s->top=-1;
 }

BSTnode * pop(stack *s)
 { BSTnode *p;
   p=s->data[s->top];
   s->top=s->top-1;
   return(p);
 }

void  push(stack *s, BSTnode *p)
  { s->top=s->top+1;
    s->data[s->top]=p;
  }

int empty(stack *s)
 { if(s->top==-1)
     return(1);
   return(0);
 }
int full(stack *s)
  {  if(s->top==19)
return(1);
     return(0);
  }


BSTnode *insert(BSTnode *,int);
BSTnode *create();
void non_rec_preorder(BSTnode *T);
void non_rec_postorder(BSTnode *T);
void non_rec_inorder(BSTnode *T);

int main()
{
BSTnode *root=NULL,*p;
int x,op;
do
 { printf("\n\n1)Create\n2)Preorder(non-recursive)");
   printf("\n3)Inorder(non-recursive)\n4)Posorder(non-Recursive)");
   printf("\n5)Quit");
   printf("\nEnter Your Choice :");
   scanf("%d",&op);
    switch(op)
     {
case 1: root=create();break;
case 2: non_rec_preorder(root);break;
case 3: non_rec_inorder(root);break;
case 4: non_rec_postorder(root);break;
    }
}while(op!=5);
}


void non_rec_preorder(BSTnode *T)
 {
stack s;
init(&s);
printf("\n");
if(T==NULL)
return;
while(T!=NULL)
 {
printf("%d   ",T->data);
push(&s,T);
T=T->left;
 }
      while(!empty(&s))
{
T=pop(&s);
T=T->right;
while(T!=NULL)
 {
printf("%d   ",T->data);
push(&s,T);
T=T->left;
 }
}

 }

 void non_rec_postorder(BSTnode *T)
  {
stack s,s1;
BSTnode *flag;
init(&s);init(&s1);
printf("\n");
if(T==NULL)
   return;
while(T!=NULL)
  {
push(&s,T);push(&s1,NULL);
T=T->left;
  }
while(!empty(&s))
  {
T=pop(&s);flag=pop(&s1);
if(flag!=NULL)
printf("%d   ",T->data);
else
 {
push(&s,T);push(&s1,(BSTnode*)1);
T=T->right;
while(T!=NULL)
  {
push(&s,T);push(&s1,NULL);
T=T->left;
  }
}
  }
  }




void non_rec_inorder(BSTnode *T)
 {   stack s;
     init(&s);
     printf("\n");
     if(T==NULL)
      return;
      while(T!=NULL)
       { push(&s,T);
T=T->left;
       }
      while(!empty(&s))
       { T=pop(&s);
printf("%d   ",T->data);
T=T->right;
while(T!=NULL)
 { push(&s,T);
   T=T->left;
 }
       }
 }

BSTnode *insert(BSTnode *T,int x)
{
BSTnode *r;
// acquire memory for the new node
if(T==NULL)
 {
r=(BSTnode*)malloc(sizeof(BSTnode));
r->data=x;
r->left=NULL;
r->right=NULL;
return(r);
 }


if(x>T->data)
 {
T->right=insert(T->right,x);
return(T);
 }
else
if(x<T->data)
 {
T->left=insert(T->left,x);
return(T);
 }
else //duplicate data
return(T);
 }

BSTnode *create()
{
int n,x,i;
BSTnode *root;
root=NULL;
printf("\nEnter no. of nodes :");
scanf("%d",&n);
printf("\nEnter tree values :");
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
return(root);
}