Program on deque that implements a linked list.

Program on deque that implements a linked list.

#include ""
#include ""
#include ""

struct node
{
int data ;
struct node *link ;
} ;

struct dqueue
{
struct node *front ;
struct node *rear ;
} ;

void initdqueue ( struct dqueue * ) ;
void addqatend ( struct dqueue *, int item ) ;
void addqatbeg ( struct dqueue *, int item ) ;
int delqatbeg ( struct dqueue * ) ;
int delqatend ( struct dqueue * ) ;
void display ( struct dqueue ) ;
int count ( struct dqueue ) ;
void deldqueue ( struct dqueue * ) ;

void main( )
{
struct dqueue dq ;
int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;
addqatbeg ( &dq, 10 ) ;
addqatend ( &dq, 12 ) ;
addqatbeg ( &dq, 9 ) ;
addqatend ( &dq, 13 ) ;
addqatbeg ( &dq, 8 ) ;
addqatend ( &dq, 14 ) ;
addqatbeg ( &dq, 7 ) ;

display ( dq ) ;

n = count ( dq ) ;
printf ( "\nTotal elements: %d", n ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

display ( dq ) ;
n = count ( dq ) ;
printf ( "\nElements Left: %d", n ) ;

deldqueue ( &dq ) ;

getch( ) ;
}

/* initializes elements of structure */
void initdqueue ( struct dqueue *p )
{
p -> front = p -> rear = NULL ;
}

/* adds item at the end of dqueue */
void addqatend ( struct dqueue *p, int item )
{
struct node *temp ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) );
temp -> data = item ;
temp -> link = NULL ;

if ( p -> front == NULL )
p -> front = temp ;
else
p -> rear -> link = temp ;
p -> rear = temp ;
}

/* adds item at begining of dqueue */
void addqatbeg ( struct dqueue *p, int item )
{
struct node *temp ;
int *q ;
temp = ( struct node * ) malloc ( sizeof ( struct node ) );
temp -> data = item ;
temp -> link = NULL ;

if ( p -> front == NULL )
p -> front = p -> rear = temp ;
else
{
temp -> link = p -> front ;
p -> front = temp ;
}
}

/* deletes item from begining of dqueue */
int delqatbeg ( struct dqueue *p )
{
struct node *temp = p -> front ;
int item ;
if ( temp == NULL )
{
printf ( "\nQueue is empty." ) ;
return 0 ;
}
else
{
temp = p -> front ;
item = temp -> data ;
p -> front = temp -> link ;
free ( temp ) ;

if ( temp == NULL )
p -> rear = NULL ;
return ( item ) ;
}
}

/* deletes item from end of dqueue */
int delqatend ( struct dqueue *p )
{
struct node *temp , *rleft, *q ;
int item ;
temp = p -> front ;
if ( p -> rear == NULL )
{
printf ( "\nQueue is empty." ) ;
return 0 ;
}
else
{
while ( temp != p -> rear )
{
rleft = temp ;
temp = temp -> link ;
}
q = p -> rear ;
item = q -> data ;
free ( q ) ;
p -> rear = rleft ;
p -> rear -> link = NULL ;
if ( p -> rear == NULL )
p -> front = NULL ;
return ( item ) ;
}
}

/* displays the queue */
void display ( struct dqueue dq )
{
struct node *temp = dq.front ;

printf ( "\nfront -> " ) ;
while ( temp != NULL )
{
if ( temp -> link == NULL )
{
printf ( "\t%d", temp -> data ) ;
printf ( " <- rear" ) ;
}
else
printf ( "\t%d", temp -> data ) ;
temp = temp -> link ;
}
printf ( "\n" ) ;
}

/* counts the number of items in dqueue */
int count ( struct dqueue dq )
{
int c = 0 ;
struct node *temp = dq.front ;

while ( temp != NULL )
{
temp = temp -> link ;
c++ ;
}

return c ;
}

/* deletes the queue */
void deldqueue ( struct dqueue *p )
{
struct node *temp ;

if ( p -> front == NULL )
return ;

while ( p -> front != NULL )
{
temp = p -> front ;
p -> front = p -> front -> link ;
free ( temp ) ;
}
}

Program to find the shortest path

Program to find the shortest path

#include ""
#include ""

#define INF 9999

void main( )
{
int arr[4][4] ;
int cost[4][4] = {
7, 5, 0, 0,
7, 0, 0, 2,
0, 3, 0, 0,
4, 0, 1, 0
} ;
int i, j, k, n = 4 ;

clrscr( ) ;

for ( i = 0 ; i < n ; i++ )
{
for ( j = 0; j < n ; j++ )
{
if ( cost[i][j] == 0 )
arr[i][j] = INF ;
else
arr[i][j] = cost[i][j] ;
}
}

printf ( "Adjacency matrix of cost of edges:\n" ) ;
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0; j < n ; j++ )
printf ( "%d\t", arr[i][j] ) ;
printf ( "\n" ) ;
}

for ( k = 0 ; k < n ; k++ )
{
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
if ( arr[i][j] > arr[i][k] + arr[k][j] )
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}

printf ( "\nAdjacency matrix of lowest cost between the vertices:\n" ) ;
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0; j < n ; j++ )
printf ( "%d\t", arr[i][j] ) ;
printf ( "\n" ) ;
}

getch( ) ;
}

minimum cost of a spanning tree.

minimum cost of a spanning tree.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

struct lledge
{
int v1, v2 ;
float cost ;
struct lledge *next ;
} ;

int stree[5] ;
int count[5] ;
int mincost ;

struct lledge * kminstree ( struct lledge *, int ) ;
int getrval ( int ) ;
void combine ( int, int ) ;
void del ( struct lledge * ) ;

void main( )
{
struct lledge *temp, *root ;
int i ;

clrscr( ) ;

root = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

root -> v1 = 4 ;
root -> v2 = 3 ;
root -> cost = 1 ;
temp = root -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

temp -> v1 = 4 ;
temp -> v2 = 2 ;
temp -> cost = 2 ;
temp -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

temp = temp -> next ;
temp -> v1 = 3 ;
temp -> v2 = 2 ;
temp -> cost = 3 ;
temp -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

temp = temp -> next ;
temp -> v1 = 4 ;
temp -> v2 = 1 ;
temp -> cost = 4 ;
temp -> next = NULL ;

root = kminstree ( root, 5 ) ;

for ( i = 1 ; i <= 4 ; i++ )
printf ( "\nstree[%d] -> %d", i, stree[i] ) ;
printf ( "\nThe minimum cost of spanning tree is %d", mincost ) ;
del ( root ) ;

getch( ) ;
}
struct lledge * kminstree ( struct lledge *root, int n )
{
struct lledge *temp = NULL ;
struct lledge *p, *q ;
int noofedges = 0 ;
int i, p1, p2 ;

for ( i = 0 ; i < n ; i++ )
stree[i] = i ;
for ( i = 0 ; i < n ; i++ )
count[i] = 0 ;

while ( ( noofedges < ( n - 1 ) ) && ( root != NULL ) )
{
p = root ;

root = root -> next ;

p1 = getrval ( p -> v1 ) ;
p2 = getrval ( p -> v2 ) ;

if ( p1 != p2 )
{
combine ( p -> v1, p -> v2 ) ;
noofedges++ ;
mincost += p -> cost ;
if ( temp == NULL )
{
temp = p ;
q = temp ;
}
else
{
q -> next = p ;
q = q -> next ;
}
q -> next = NULL ;
}
}
return temp ;
}

int getrval ( int i )
{
int j, k, temp ;
k = i ;
while ( stree[k] != k )
k = stree[k] ;
j = i ;
while ( j != k )
{
temp = stree[j] ;
stree[j] = k ;
j = temp ;
}
return k ;
}

void combine ( int i, int j )
{
if ( count[i] < count[j] )
stree[i] = j ;
else
{
stree[j] = i ;
if ( count[i] == count[j] )
count[j]++ ;
}
}

void del ( struct lledge *root )
{
struct lledge *temp ;

while ( root != NULL )
{
temp = root -> next ;
free ( root ) ;
root = temp ;
}
}

Breadth first search algorithm.

Breadth first search algorithm.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

#define TRUE 1
#define FALSE 0
#define MAX 8

struct node
{
int data ;
struct node *next ;
} ;

int visited[MAX] ;
int q[8] ;
int front, rear ;

void bfs ( int, struct node ** ) ;
struct node * getnode_write ( int ) ;
void addqueue ( int ) ;
int deletequeue( ) ;
int isempty( ) ;
void del ( struct node * ) ;

void main( )
{
struct node *arr[MAX] ;
struct node *v1, *v2, *v3, *v4 ;
int i ;

clrscr( ) ;

v1 = getnode_write ( 2 ) ;
arr[0] = v1 ;
v1 -> next = v2 = getnode_write ( 3 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[1] = v1 ;
v1 -> next = v2 = getnode_write ( 4 ) ;
v2 -> next = v3 = getnode_write ( 5 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[2] = v1 ;
v1 -> next = v2 = getnode_write ( 6 ) ;
v2 -> next = v3 = getnode_write ( 7 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[3] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[4] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[5] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[6] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 4 ) ;
arr[7] = v1 ;
v1 -> next = v2 = getnode_write ( 5 ) ;
v2 -> next = v3 = getnode_write ( 6 ) ;
v3 -> next = v4 = getnode_write ( 7 ) ;
v4 -> next = NULL ;

front = rear = -1 ;
bfs ( 1, arr ) ;

for ( i = 0 ; i < MAX ; i++ )
del ( arr[i] ) ;

getch( ) ;
}

void bfs ( int v, struct node **p )
{
struct node *u ;

visited[v - 1] = TRUE ;
printf ( "%d\t", v ) ;
addqueue ( v ) ;

while ( isempty( ) == FALSE )
{
v = deletequeue( ) ;
u = * ( p + v - 1 ) ;

while ( u != NULL )
{
if ( visited [ u -> data - 1 ] == FALSE )
{
addqueue ( u -> data ) ;
visited [ u -> data - 1 ] = TRUE ;
printf ( "%d\t", u -> data ) ;
}
u = u -> next ;
}
}
}

struct node * getnode_write ( int val )
{
struct node *newnode ;
newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
return newnode ;
}

void addqueue ( int vertex )
{
if ( rear == MAX - 1 )
{
printf ( "\nQueue Overflow." ) ;
exit( ) ;
}

rear++ ;
q[rear] = vertex ;

if ( front == -1 )
front = 0 ;
}

int deletequeue( )
{
int data ;

if ( front == -1 )
{
printf ( "\nQueue Underflow." ) ;
exit( ) ;
}

data = q[front] ;

if ( front == rear )
front = rear = -1 ;
else
front++ ;

return data ;
}

int isempty( )
{
if ( front == -1 )
return TRUE ;
return FALSE ;
}

void del ( struct node *n )
{
struct node *temp ;

while ( n != NULL )
{
temp = n -> next ;
free ( n ) ;
n = temp ;
}
}

depth first search algorithm.

depth first search algorithm.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

#define TRUE 1
#define FALSE 0
#define MAX 8

struct node
{
int data ;
struct node *next ;
} ;

int visited[MAX] ;

void dfs ( int, struct node ** ) ;
struct node * getnode_write ( int ) ;
void del ( struct node * ) ;

void main( )
{
struct node *arr[MAX] ;
struct node *v1, *v2, *v3, *v4 ;
int i ;

clrscr( ) ;

v1 = getnode_write ( 2 ) ;
arr[0] = v1 ;
v1 -> next = v2 = getnode_write ( 3 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[1] = v1 ;
v1 -> next = v2 = getnode_write ( 4 ) ;
v2 -> next = v3 = getnode_write ( 5 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[2] = v1 ;
v1 -> next = v2 = getnode_write ( 6 ) ;
v2 -> next = v3 = getnode_write ( 7 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[3] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[4] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[5] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[6] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 4 ) ;
arr[7] = v1 ;
v1 -> next = v2 = getnode_write ( 5 ) ;
v2 -> next = v3 = getnode_write ( 6 ) ;
v3 -> next = v4 = getnode_write ( 7 ) ;
v4 -> next = NULL ;

dfs ( 1, arr ) ;

for ( i = 0 ; i < q =" *"> data - 1] == FALSE )
dfs ( q -> data, p ) ;
else
q = q -> next ;
}
}

struct node * getnode_write ( int val )
{
struct node *newnode ;
newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
return newnode ;
}

void del ( struct node *n )
{
struct node *temp ;

while ( n != NULL )
{
temp = n -> next ;
free ( n ) ;
n = temp ;
}
}

Program that creates random numbers in a given file

Program that creates random numbers in a given file.

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

void main( )
{
FILE *fp ;
char str [ 67 ] ;
int i, noofr, j ;

clrscr( ) ;

printf ( "Enter file name: " ) ;
scanf ( "%s", str ) ;

printf ( "Enter number of records: " ) ;
scanf ( "%d", &noofr ) ;

fp = fopen ( str, "wb" ) ;
if ( fp == NULL )
{
printf ( "Unable to create file." ) ;
getch( ) ;
exit ( 0 ) ;
}

randomize( ) ;

for ( i = 0 ; i < noofr ; i++ )
{
j = random ( 1000 ) ;
fwrite ( &j, sizeof ( int ), 1, fp ) ;
printf ( "%d\t", j ) ;
}

fclose ( fp ) ;

printf ( "\nFile is created. \nPress any key to continue." ) ;

getch( ) ;
}

External Sorting.

External Sorting.

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

void shownums ( char * ) ;
void split ( char * ) ;
void sort ( char * ) ;

void main( )
{
char str[67] ;

clrscr( ) ;

printf ( "Enter file name: " ) ;
scanf ( "%s", str ) ;

printf ( "Numbers before sorting:\n" ) ;
shownums ( str ) ;

split ( str ) ;
sort ( str ) ;

printf ( "\nNumbers after sorting:\n" ) ;
shownums ( str ) ;

getch( ) ;
}

/* Displays the contents of file */
void shownums ( char *p )
{
FILE *fp ;
int i ;

fp = fopen ( p, "rb" ) ;
if ( fp == NULL )
{
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 0 ) ;
}

while ( fread ( &i, sizeof ( int ), 1, fp ) != 0 )
printf ( "%d \t", i ) ;

fclose ( fp ) ;
}

/* Splits the original file into two files */
void split ( char *p )
{
FILE *fs, *ft ;
long int l, count ;
int i ;

fs = fopen ( p, "rb" ) ;
if ( fs == NULL )
{
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 0 ) ;
}

ft = fopen ( "temp1.dat", "wb" ) ;
if ( ft == NULL )
{
fclose ( fs ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 1 ) ;
}

fseek ( fs, 0L, SEEK_END ) ;
l = ftell ( fs ) ;
fseek ( fs, 0L, SEEK_SET ) ;

l = l / ( sizeof ( int ) * 2 ) ;

for ( count = 1 ; count <= l ; count++ )
{
fread ( &i, sizeof ( int ), 1, fs ) ;
fwrite ( &i, sizeof ( int ), 1, ft ) ;
}

fclose ( ft ) ;

ft = fopen ( "temp2.dat", "wb" ) ;
if ( ft == NULL )
{
fclose ( fs ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 2 ) ;
}

while ( fread ( &i, sizeof ( int ), 1, fs ) != 0 )
fwrite ( &i, sizeof ( int ), 1, ft ) ;

fcloseall ( ) ;
}

/* Sorts the file */
void sort ( char *p )
{
FILE *fp[4] ;
char *fnames[ ] =
{
"temp1.dat",
"temp2.dat",
"final1.dat",
"final2.dat"
} ;

int i, j = 1, i1, i2, flag1, flag2, p1, p2 ;
long int l ;

while ( 1 )
{
for ( i = 0 ; i <= 1 ; i++ )
{
fp[i] = fopen ( fnames[i], "rb+" ) ;
if ( fp[i] == NULL )
{
fcloseall( ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( i ) ;
}

fseek ( fp[i], 0L, SEEK_END ) ;
l = ftell ( fp[i] ) ;
if ( l == 0 )
goto out ;
fseek ( fp[i], 0L, SEEK_SET ) ;
}

for ( i = 2 ; i <= 3 ; i++ )
{
fp[i] = fopen ( fnames[i], "wb" ) ;
if ( fp[i] == NULL )
{
fcloseall( ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( i ) ;
}
}

i = 2 ;
i1 = i2 = 0 ;
flag1 = flag2 = 1 ;

while ( 1 )
{
if ( flag1 )
{
if ( fread ( &p1, sizeof ( int ), 1, fp[0] ) == 0 )
{
/* If first file ends then the whole content of second
file is written in the respective target file */
while ( fread ( &p2, sizeof ( int ), 1, fp[1] ) != 0 )
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
break ;
}
}

if ( flag2 )
{
if ( fread ( &p2, sizeof ( int ), 1, fp[1] ) == 0 )
{
/* If second file ends then the whole content of first
file is written in the respective target file */
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
while ( fread ( &p1, sizeof ( int ), 1, fp[0] ) != 0 )
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
break ;
}
}

if ( p1 < p2 )
{
flag2 = 0 ;
flag1 = 1 ;
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
i1++ ;
}
else
{
flag1 = 0 ;
flag2 = 1 ;
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
i2++ ;
}

if ( i1 == j )
{
flag1 = flag2 = 1 ;
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
for ( i2++ ; i2 < j ; i2++ )
{
if ( fread ( &p2, sizeof ( int ), 1, fp[1] ) != 0 )
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
}
i1 = i2 = 0 ;
i == 2 ? ( i = 3 ) : ( i = 2 ) ;
}

if ( i2 == j )
{
flag1 = flag2 = 1 ;
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
for ( i1++ ; i1 < j ; i1++ )
{
if ( fread ( &p1, sizeof ( int ), 1, fp[0] ) != 0 )
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
}
i1 = i2 = 0 ;
i == 2 ? ( i = 3 ) : ( i = 2 ) ;
}
}

fcloseall( ) ;
remove ( fnames[0] ) ;
remove ( fnames[1] ) ;
rename ( fnames[2], fnames[0] ) ;
rename ( fnames[3], fnames[1] ) ;
j *= 2 ;
}

out :

fcloseall( ) ;
remove ( p ) ;
rename ( fnames[0], p ) ;
remove ( fnames[1] ) ;
}

Merge Sort.

Merge Sort.

#include
#include

void main( )
{
int a[5] = { 11, 2, 9, 13, 57 } ;
int b[5] = { 25, 17, 1, 90, 3 } ;
int c[10] ;
int i, j, k, temp ;

clrscr( ) ;

printf ( "Merge sort.\n" ) ;

printf ( "\nFirst array:\n" ) ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", a[i] ) ;

printf ( "\n\nSecond array:\n" ) ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", b[i] ) ;

for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( a[i] > a[j] )
{
temp = a[i] ;
a[i] = a[j] ;
a[j] = temp ;
}
if ( b[i] > b[j] )
{
temp = b[i] ;
b[i] = b[j] ;
b[j] = temp ;
}
}
}

for ( i = j = k = 0 ; i <= 9 ; )
{
if ( a[j] <= b[k] )
c[i++] = a[j++] ;
else
c[i++] = b[k++] ;

if ( j == 5 || k == 5 )
break ;
}

for ( ; j <= 4 ; )
c[i++] = a[j++] ;

for ( ; k <= 4 ; )
c[i++] = b[k++] ;

printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", c[i] ) ;

getch( ) ;
}

Heap Sort.

Heap Sort.

#include "stdio.h"
#include "conio.h"

void makeheap ( int [ ], int ) ;
void heapsort ( int [ ], int ) ;

void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

clrscr( ) ;
printf ( "Heap Sort.\n" ) ;

makeheap ( arr, 10 ) ;

printf ( "\nBefore Sorting:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

heapsort ( arr, 10 ) ;

printf ( "\nAfter Sorting:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( );
}

void makeheap ( int x[ ], int n )
{
int i, val, s, f ;
for ( i = 1 ; i < n ; i++ )
{
val = x[i] ;
s = i ;
f = ( s - 1 ) / 2 ;
while ( s > 0 && x[f] < val )
{
x[s] = x[f] ;
s = f ;
f = ( s - 1 ) / 2 ;
}
x[s] = val ;
}
}

void heapsort ( int x[ ], int n )
{
int i, s, f, ivalue ;
for ( i = n - 1 ; i > 0 ; i-- )
{
ivalue = x[i] ;
x[i] = x[0] ;
f = 0 ;

if ( i == 1 )
s = -1 ;
else
s = 1 ;

if ( i > 2 && x[2] > x[1] )
s = 2 ;

while ( s >= 0 && ivalue < x[s] )
{
x[f] = x[s] ;
f = s ;
s = 2 * f + 1 ;

if ( s + 1 <= i - 1 && x[s] < x[s + 1] )
s++ ;
if ( s > i - 1 )
s = -1 ;
}
x[f] = ivalue ;
}
}

Binary Tree Sorting.

Binary Tree Sorting.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void inorder ( struct btreenode * ) ;

void main( )
{
struct btreenode *bt ;
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

bt = NULL ;

clrscr( ) ;

printf ( "Binary tree sort.\n" ) ;

printf ( "\nArray:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 0 ; i <= 9 ; i++ )
insert ( &bt, arr[i] ) ;

printf ( "\nIn-order traversal of binary tree:\n" ) ;
inorder ( bt ) ;

getch( ) ;
}

void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else
{
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}

void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;
printf ( "%d\t", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
}

Insertion sort.

Insertion sort.

#include "stdio.h"
#include "conio.h"

void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, k, temp ;

clrscr( ) ;

printf ( "Insertion sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 1 ; i <= 4 ; i++ )
{
for ( j = 0 ; j < i ; j++ )
{
if ( arr[j] > arr[i] )
{
temp = arr[j] ;
arr[j] = arr[i] ;

for ( k = i ; k > j ; k-- )
arr[k] = arr[k - 1] ;

arr[k + 1] = temp ;
}
}
}

printf ( "\n\nArray after sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( ) ;
}

Quick sort

Quick sort

#include "conio.h"
#include "stdio.h"

int split ( int*, int, int ) ;

void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

void quicksort ( int *, int, int ) ;

clrscr( ) ;

printf ( "Quick sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 9 ; i++ ) printf ( "%d\t", arr[i] ) ; quicksort ( arr, 0, 9 ) ; printf ( "\nArray after sorting:\n") ; for ( i = 0 ; i <= 9 ; i++ ) printf ( "%d\t", arr[i] ) ; getch( ) ; } void quicksort ( int a[ ], int lower, int upper ) { int i ; if ( upper > lower )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1 ) ;
quicksort ( a, i + 1, upper ) ;
}
}

int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;

p = lower + 1 ;
q = upper ;
i = a[lower] ;

while ( q >= p )
{
while ( a[p] <> i )
q-- ;

if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}

t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;

return q ;
}

Selection sort.

Selection sort.

#include ""
#include ""

void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, temp ;

clrscr( ) ;

printf ( "Selection sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}

printf ( "\n\nArray after sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( ) ;
}

Bubble sort.

Bubble sort.

#include
#include

void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, temp ;

clrscr( ) ;

printf ( "Bubble sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = 0 ; j <= 3 - i ; j++ )
{
if ( arr[j] > arr[j + 1] )
{
temp = arr[j] ;
arr[j] = arr[j + 1] ;
arr[j + 1] = temp ;
}
}
}

printf ( "\n\nArray after sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( ) ;
}

Binary search in a sorted array.

Binary search in a sorted array.
#include ""
#include ""

void main( )
{
int arr[10] = { 1, 2, 3, 9, 11, 13, 17, 25, 57, 90 } ;
int mid, lower = 0 , upper = 9, num, flag = 1 ;

clrscr( ) ;

printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;

for ( mid = ( lower + upper ) / 2 ; lower <= upper ;
mid = ( lower + upper ) / 2 )
{
if ( arr[mid] == num )
{
printf ( "The number is at position %d in the array.", mid ) ;
flag = 0 ;
break ;
}
if ( arr[mid] > num )
upper = mid - 1 ;
else
lower = mid + 1 ;
}

if ( flag )
printf ( "Element is not present in the array." ) ;

getch( ) ;
}

Linear search in a sorted array.

Linear search in a sorted array.

#include ""
#include ""

void main( )
{
int arr[10] = { 1, 2, 3, 9, 11, 13, 17, 25, 57, 90 } ;
int i, num ;

clrscr( ) ;

printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;

for ( i = 0 ; i <= 9 ; i++ )
{
if ( arr[9] < num || arr[i] >= num )
{
if ( arr[i] == num )
printf ( "The number is at position %d in the array.", i ) ;
else
printf ( "Number is not present in the array." ) ;
break ;
}
}

getch( ) ;
}

Linear search in an unsorted array.

Linear search in an unsorted array.

#include <"stdio.h">
#include ""

void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i, num ;

clrscr( ) ;

printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;

for ( i = 0 ; i <= 9 ; i++ )
{
if ( arr[i] == num )
break ;
}

if ( i == 10 )
printf ( "Number is not present in the array." ) ;
else
printf ( "The number is at position %d in the array.", i ) ;

getch( ) ;
}

Program to maintain a heap.

#include <"stdio.h">
#include <"conio.h">

void restoreup ( int, int * ) ;
void restoredown ( int, int *, int ) ;
void makeheap ( int *, int ) ;
void add ( int, int *, int * ) ;
int replace ( int, int *, int ) ;
int del ( int *, int * ) ;

void main( )
{
int arr [20] = { 1000, 7, 10, 25, 17, 23, 27, 16,
19, 37, 42, 4, 33, 1, 5, 11 } ;
int i, n = 15 ;

clrscr( ) ;
makeheap ( arr, n ) ;

printf ( "Heap:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

i = 24 ;
add ( i, arr, &n ) ;

printf ( "\n\nElement added %d.\n", i ) ;
printf ( "\nHeap after addition of an element:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

i = replace ( 2, arr, n ) ;
printf ( "\n\nElement replaced %d.\n", i ) ;
printf ( "\nHeap after replacement of an element:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

i = del ( arr, &n ) ;
printf ( "\n\nElement deleted %d.\n", i ) ;
printf ( "\nHeap after deletion of an element:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

getch( ) ;
}

void restoreup ( int i, int *arr )
{
int val ;
val = arr [i] ;
while ( arr [i / 2] <= val )
{
arr [i] = arr [i / 2] ;
i = i / 2 ;
}
arr [i] = val ;
}

void restoredown ( int pos, int *arr, int n )
{
int i, val ;
val = arr [pos] ;
while ( pos <= n / 2 )
{
i = 2 * pos ;
if ( ( i < n ) && ( arr [i] < arr [i + 1] ) )
i++ ;
if ( val >= arr [i] )
break ;
arr [pos] = arr [i] ;
pos = i ;
}
arr [pos] = val ;
}

void makeheap ( int *arr, int n )
{
int i ;
for ( i = n / 2 ; i >= 1 ; i-- )
restoredown ( i, arr, n ) ;
}

void add ( int val, int *arr, int *n )
{
( *n ) ++ ;
arr [*n] = val ;
restoreup ( *n, arr ) ;
}
int replace ( int i, int *arr, int n )
{
int r = arr [1] ;
arr [1] = i ;
for ( i = n / 2 ; i >= 1 ; i-- )
restoredown ( i, arr, n ) ;
return r ;
}

int del ( int *arr, int *n )
{
int val ;
val = arr [1] ;
arr [1] = arr [*n] ;
( *n ) -- ;
restoredown ( 1, arr, *n ) ;
return val ;
}

Program which maintains a B-tree of order 5.

#include <"stdio.h">
#include <"conio.h">
#include <"stdlib.h">
#include <"alloc.h">

#define MAX 4
#define MIN 2

struct btnode
{
int count ;
int value[MAX + 1] ;
struct btnode *child[MAX + 1] ;
} ;

struct btnode * insert ( int, struct btnode * ) ;
int setval ( int, struct btnode *, int *, struct btnode ** ) ;
struct btnode * search ( int, struct btnode *, int * ) ;
int searchnode ( int, struct btnode *, int * ) ;
void fillnode ( int, struct btnode *, struct btnode *, int ) ;
void split ( int, struct btnode *, struct btnode *,
int, int *, struct btnode ** ) ;
struct btnode * delete ( int, struct btnode * ) ;
int delhelp ( int, struct btnode * ) ;
void clear ( struct btnode *, int ) ;
void copysucc ( struct btnode *, int ) ;
void restore ( struct btnode *, int ) ;
void rightshift ( struct btnode *, int ) ;
void leftshift ( struct btnode *, int ) ;
void merge ( struct btnode *, int ) ;
void display ( struct btnode * ) ;

void main( )
{
struct node *root ;
root = NULL ;

clrscr( ) ;

root = insert ( 27, root ) ;
root = insert ( 42, root ) ;
root = insert ( 22, root ) ;
root = insert ( 47, root ) ;
root = insert ( 32, root ) ;
root = insert ( 2, root ) ;
root = insert ( 51, root ) ;
root = insert ( 40, root ) ;
root = insert ( 13, root ) ;

printf ( "B-tree of order 5:\n" ) ;
display ( root ) ;

root = delete ( 22, root ) ;
root = delete ( 11, root ) ;

printf ( "\n\nAfter deletion of values:\n" ) ;
display ( root ) ;

getch( ) ;
}

/* inserts a value in the B-tree*/
struct btnode * insert ( int val, struct btnode *root )
{
int i ;
struct btnode *c, *n ;
int flag ;

flag = setval ( val, root, &i, &c ) ;
if ( flag )
{
n = ( struct btnode * ) malloc ( sizeof ( struct btnode ) ) ;
n -> count = 1 ;
n -> value [1] = i ;
n -> child [0] = root ;
n -> child [1] = c ;
return n ;
}
return root ;
}

/* sets the value in the node */
int setval ( int val, struct btnode *n, int *p, struct btnode **c )
{
int k ;
if ( n == NULL )
{
*p = val ;
*c = NULL ;
return 1 ;
}
else
{
if ( searchnode ( val, n, &k ) )
printf ( "\nKey value already exists.\n" ) ;
if ( setval ( val, n -> child [k], p, c ) )
{
if ( n -> count < MAX )
{
fillnode ( *p, *c, n, k ) ;
return 0 ;
}
else
{
split ( *p, *c, n, k, p, c ) ;
return 1 ;
}
}
return 0 ;
}
}

/* searches value in the node */
struct btnode * search ( int val, struct btnode *root, int *pos )
{
if ( root == NULL )
return NULL ;
else
{
if ( searchnode ( val, root, pos ) )
return root ;
else
return search ( val, root -> child [*pos], pos ) ;
}
}

/* searches for the node */
int searchnode ( int val, struct btnode *n, int *pos )
{
if ( val < n -> value [1] )
{
*pos = 0 ;
return 0 ;
}
else
{
*pos = n -> count ;
while ( ( val < n -> value [*pos] ) && *pos > 1 )
( *pos )-- ;
if ( val == n -> value [*pos] )
return 1 ;
else
return 0 ;
}
}


/* adjusts the value of the node */
void fillnode ( int val, struct btnode *c, struct btnode *n, int k )
{
int i ;
for ( i = n -> count ; i > k ; i-- )
{
n -> value [i + 1] = n -> value [i] ;
n -> child [i + 1] = n -> child [i] ;
}
n -> value [k + 1] = val ;
n -> child [k + 1] = c ;
n -> count++ ;
}

/* splits the node */
void split ( int val, struct btnode *c, struct btnode *n,
int k, int *y, struct btnode **newnode )
{
int i, mid ;

if ( k <= MIN )
mid = MIN ;
else
mid = MIN + 1 ;

*newnode = ( struct btnode * ) malloc ( sizeof ( struct btnode ) ) ;

for ( i = mid + 1 ; i <= MAX ; i++ )
{
( *newnode ) -> value [i - mid] = n -> value [i] ;
( *newnode ) -> child [i - mid] = n -> child [i] ;
}

( *newnode ) -> count = MAX - mid ;
n -> count = mid ;

if ( k <= MIN )
fillnode ( val, c, n, k ) ;
else
fillnode ( val, c, *newnode, k - mid ) ;

*y = n -> value [n -> count] ;
( *newnode ) -> child [0] = n -> child [n -> count] ;
n -> count-- ;
}

/* deletes value from the node */
struct btnode * delete ( int val, struct btnode *root )
{
struct btnode * temp ;
if ( ! delhelp ( val, root ) )
printf ( "\nValue %d not found.", val ) ;
else
{
if ( root -> count == 0 )
{
temp = root ;
root = root -> child [0] ;
free ( temp ) ;
}
}
return root ;
}

/* helper function for delete( ) */
int delhelp ( int val, struct btnode *root )
{
int i ;
int flag ;
if ( root == NULL )
return 0 ;
else
{
flag = searchnode ( val, root, &i ) ;
if ( flag )
{
if ( root -> child [i - 1] )
{
copysucc ( root, i ) ;
flag = delhelp ( root -> value [i], root -> child [i] ) ;
if ( !flag )
printf ( "\nValue %d not found.", val ) ;
}
else
clear ( root, i ) ;
}
else
flag = delhelp ( val, root -> child [i] ) ;

if ( root -> child [i] != NULL )
{
if ( root -> child [i] -> count < MIN )
restore ( root, i ) ;
}
return flag ;
}
}

/* removes the value from the node and adjusts the values */
void clear ( struct btnode *node, int k )
{
int i ;
for ( i = k + 1 ; i <= node -> count ; i++ )
{
node -> value [i - 1] = node -> value [i] ;
node -> child [i - 1] = node -> child [i] ;
}
node -> count-- ;
}

/* copies the successor of the value that is to be deleted */
void copysucc ( struct btnode *node, int i )
{
struct btnode *temp ;

temp = node -> child [i] ;

while ( temp -> child[0] )
temp = temp -> child [0] ;

node -> value [i] = temp -> value [1] ;
}

/* adjusts the node */
void restore ( struct btnode *node, int i )
{
if ( i == 0 )
{
if ( node -> child [1] -> count > MIN )
leftshift ( node, 1 ) ;
else
merge ( node, 1 ) ;
}
else
{
if ( i == node -> count )
{
if ( node -> child [i - 1] -> count > MIN )
rightshift ( node, i ) ;
else
merge ( node, i ) ;
}
else
{
if ( node -> child [i - 1] -> count > MIN )
rightshift ( node, i ) ;
else
{
if ( node -> child [i + 1] -> count > MIN )
leftshift ( node, i + 1 ) ;
else
merge ( node, i ) ;
}
}
}
}

/* adjusts the values and children while shifting the value from parent to right
child */
void rightshift ( struct btnode *node, int k )
{
int i ;
struct btnode *temp ;

temp = node -> child [k] ;

for ( i = temp -> count ; i > 0 ; i-- )
{
temp -> value [i + 1] = temp -> value [i] ;
temp -> child [i + 1] = temp -> child [i] ;
}

temp -> child [1] = temp -> child [0] ;
temp -> count++ ;
temp -> value [1] = node -> value [k] ;

temp = node -> child [k - 1] ;
node -> value [k] = temp -> value [temp -> count] ;
node -> child [k] -> child [0] = temp -> child [temp -> count] ;
temp -> count-- ;
}

/* adjusts the values and children while shifting the value from parent to left
child */
void leftshift ( struct btnode *node, int k )
{
int i ;
struct btnode *temp ;

temp = node -> child [k - 1] ;
temp -> count++ ;
temp -> value [temp -> count] = node -> value [k] ;
temp -> child [temp -> count] = node -> child [k] -> child [0] ;

temp = node -> child [k] ;
node -> value [k] = temp -> value [1] ;
temp -> child [0] = temp -> child [1] ;
temp -> count-- ;

for ( i = 1 ; i <= temp -> count ; i++ )
{
temp -> value [i] = temp -> value [i + 1] ;
temp -> child [i] = temp -> child [i + 1] ;
}
}

/* merges two nodes */
void merge ( struct btnode *node, int k )
{
int i ;
struct btnode *temp1, *temp2 ;

temp1 = node -> child [k] ;
temp2 = node -> child [k - 1] ;
temp2 -> count++ ;
temp2 -> value [temp2 -> count] = node -> value [k] ;
temp2 -> child [temp2 -> count] = node -> child [0] ;

for ( i = 1 ; i <= temp1 -> count ; i++ )
{
temp2 -> count++ ;
temp2 -> value [temp2 -> count] = temp1 -> value [i] ;
temp2 -> child [temp2 -> count] = temp1 -> child [i] ;
}
for ( i = k ; i < node -> count ; i++ )
{
node -> value [i] = node -> value [i + 1] ;
node -> child [i] = node -> child [i + 1] ;
}
node -> count-- ;
free ( temp1 ) ;
}

/* displays the B-tree */
void display ( struct btnode *root )
{
int i ;

if ( root != NULL )
{
for ( i = 0 ; i < root -> count ; i++ )
{
display ( root -> child [i] ) ;
printf ( "%d\t", root -> value [i + 1] ) ;
}
display ( root -> child [i] ) ;
}
}

Program to maintain an AVL tree.

#include
#include
#include

#define FALSE 0
#define TRUE 1

struct AVLNode
{
int data ;
int balfact ;
struct AVLNode *left ;
struct AVLNode *right ;
} ;

struct AVLNode * buildtree ( struct AVLNode *, int, int * ) ;
struct AVLNode * deldata ( struct AVLNode *, int, int * ) ;
struct AVLNode * del ( struct AVLNode *, struct AVLNode *, int * ) ;
struct AVLNode * balright ( struct AVLNode *, int * ) ;
struct AVLNode * balleft ( struct AVLNode *, int * ) ;
void display ( struct AVLNode * ) ;
void deltree ( struct AVLNode * ) ;

void main( )
{
struct AVLNode *avl = NULL ;
int h ;

clrscr( ) ;

avl = buildtree ( avl, 20, &h ) ;
avl = buildtree ( avl, 6, &h ) ;
avl = buildtree ( avl, 29, &h ) ;
avl = buildtree ( avl, 5, &h ) ;
avl = buildtree ( avl, 12, &h ) ;
avl = buildtree ( avl, 25, &h ) ;
avl = buildtree ( avl, 32, &h ) ;
avl = buildtree ( avl, 10, &h ) ;
avl = buildtree ( avl, 15, &h ) ;
avl = buildtree ( avl, 27, &h ) ;
avl = buildtree ( avl, 13, &h ) ;

printf ( "\nAVL tree:\n" ) ;
display ( avl ) ;

avl = deldata ( avl, 20, &h ) ;
avl = deldata ( avl, 12, &h ) ;

printf ( "\nAVL tree after deletion of a node:\n" ) ;
display ( avl ) ;

deltree ( avl ) ;

getch( ) ;
}

/* inserts an element into tree */
struct AVLNode * buildtree ( struct AVLNode *root, int data, int *h )
{
struct AVLNode *node1, *node2 ;

if ( !root )
{
root = ( struct AVLNode * ) malloc ( sizeof ( struct AVLNode ) ) ;
root -> data = data ;
root -> left = NULL ;
root -> right = NULL ;
root -> balfact = 0 ;
*h = TRUE ;
return ( root ) ;
}

if ( data < root -> data )
{
root -> left = buildtree ( root -> left, data, h ) ;
/* If left subtree is higher */
if ( *h )
{
switch ( root -> balfact )
{
case 1:
node1 = root -> left ;
if ( node1 -> balfact == 1 )
{
printf ( "\nRight rotation along %d.", root -> data ) ;
root -> left = node1 -> right ;
node1 -> right = root ;
root -> balfact = 0 ;
root = node1 ;
}
else
{
printf ( "\nDouble rotation, left along %d",
node1 -> data ) ;
node2 = node1 -> right ;
node1 -> right = node2 -> left ;
printf ( " then right along %d.\n", root -> data ) ;
node2 -> left = node1 ;
root -> left = node2 -> right ;
node2 -> right = root ;
if ( node2 -> balfact == 1 )
root -> balfact = -1 ;
else
root -> balfact = 0 ;
if ( node2 -> balfact == -1 )
node1 -> balfact = 1 ;
else
node1 -> balfact = 0 ;
root = node2 ;
}
root -> balfact = 0 ;
*h = FALSE ;
break ;

case 0:
root -> balfact = 1 ;
break ;

case -1:
root -> balfact = 0 ;
*h = FALSE ;
}
}
}

if ( data > root -> data )
{
root -> right = buildtree ( root -> right, data, h ) ;
/* If the right subtree is higher */
if ( *h )
{
switch ( root -> balfact )
{
case 1:
root -> balfact = 0 ;
*h = FALSE ;
break ;

case 0:
root -> balfact = -1 ;
break;

case -1:
node1 = root -> right ;
if ( node1 -> balfact == -1 )
{
printf ( "\nLeft rotation along %d.", root -> data ) ;
root -> right = node1 -> left ;
node1 -> left = root ;
root -> balfact = 0 ;
root = node1 ;
}
else
{
printf ( "\nDouble rotation, right along %d",
node1 -> data ) ;
node2 = node1 -> left ;
node1 -> left = node2 -> right ;
node2 -> right = node1 ;
printf ( " then left along %d.\n", root -> data ) ;
root -> right = node2 -> left ;
node2 -> left = root ;

if ( node2 -> balfact == -1 )
root -> balfact = 1 ;
else
root -> balfact = 0 ;
if ( node2 -> balfact == 1 )
node1 -> balfact = -1 ;
else
node1 -> balfact = 0 ;
root = node2 ;
}
root -> balfact = 0 ;
*h = FALSE ;
}
}
}
return ( root ) ;
}

/* deletes an item from the tree */
struct AVLNode * deldata ( struct AVLNode *root, int data, int *h )
{
struct AVLNode *node ;

if ( !root )
{
printf ( "\nNo such data." ) ;
return ( root ) ;
}
else
{
if ( data < root -> data )
{
root -> left = deldata ( root -> left, data, h ) ;
if ( *h )
root = balright ( root, h ) ;
}
else
{
if ( data > root -> data )
{
root -> right = deldata ( root -> right, data, h ) ;
if ( *h )
root = balleft ( root, h ) ;
}
else
{
node = root ;
if ( node -> right == NULL )
{
root = node -> left ;
*h = TRUE ;
free ( node ) ;
}
else
{
if ( node -> left == NULL )
{
root = node -> right ;
*h = TRUE ;
free ( node ) ;
}
else
{
node -> right = del ( node -> right, node, h ) ;
if ( *h )
root = balleft ( root, h ) ;
}
}
}
}
}
return ( root ) ;
}

struct AVLNode * del ( struct AVLNode *succ, struct AVLNode *node, int *h )
{
struct AVLNode *temp = succ ;
if ( succ -> left != NULL )
{
succ -> left = del ( succ -> left, node, h ) ;
if ( *h )
succ = balright ( succ, h ) ;
}
else
{
temp = succ ;
node -> data = succ -> data ;
succ = succ -> right ;
free ( temp ) ;
*h = TRUE ;
}
return ( succ ) ;
}

/* balances the tree, if right sub-tree is higher */
struct AVLNode * balright ( struct AVLNode *root, int *h )
{
struct AVLNode *node1, *node2 ;

switch ( root -> balfact )
{
case 1:
root -> balfact = 0 ;
break;

case 0:
root -> balfact = -1 ;
*h = FALSE ;
break;

case -1:
node1 = root -> right ;
if ( node1 -> balfact <= 0 )
{
printf ( "\nLeft rotation along %d.", root -> data ) ;
root -> right = node1 -> left ;
node1 -> left = root ;
if ( node1 -> balfact == 0 )
{
root -> balfact = -1 ;
node1 -> balfact = 1 ;
*h = FALSE ;
}
else
{
root -> balfact = node1 -> balfact = 0 ;
}
root = node1 ;
}
else
{
printf ( "\nDouble rotation, right along %d", node1 -> data );
node2 = node1 -> left ;
node1 -> left = node2 -> right ;
node2 -> right = node1 ;
printf ( " then left along %d.\n", root -> data );
root -> right = node2 -> left ;
node2 -> left = root ;

if ( node2 -> balfact == -1 )
root -> balfact = 1 ;
else
root -> balfact = 0 ;
if ( node2 -> balfact == 1 )
node1 -> balfact = -1 ;
else
node1 -> balfact = 0 ;
root = node2 ;
node2 -> balfact = 0 ;
}
}
return ( root ) ;
}

/* balances the tree, if left sub-tree is higher */
struct AVLNode * balleft ( struct AVLNode *root, int *h )
{
struct AVLNode *node1, *node2 ;

switch ( root -> balfact )
{
case -1:
root -> balfact = 0 ;
break ;

case 0:
root -> balfact = 1 ;
*h = FALSE ;
break ;

case 1:
node1 = root -> left ;
if ( node1 -> balfact >= 0 )
{
printf ( "\nRight rotation along %d.", root -> data ) ;
root -> left = node1 -> right ;
node1 -> right = root ;
if ( node1 -> balfact == 0 )
{
root -> balfact = 1 ;
node1 -> balfact = -1 ;
*h = FALSE ;
}
else
{
root -> balfact = node1 -> balfact = 0 ;
}
root = node1 ;
}
else
{
printf ( "\nDouble rotation, left along %d", node1 -> data ) ;
node2 = node1 -> right ;
node1 -> right = node2 -> left ;
node2 -> left = node1 ;
printf ( " then right along %d.\n", root -> data ) ;
root -> left = node2 -> right ;
node2 -> right = root ;

if ( node2 -> balfact == 1 )
root -> balfact = -1 ;
else
root -> balfact = 0 ;
if ( node2-> balfact == -1 )
node1 -> balfact = 1 ;
else
node1 -> balfact = 0 ;
root = node2 ;
node2 -> balfact = 0 ;
}
}
return ( root ) ;
}

/* displays the tree in-order */
void display ( struct AVLNode *root )
{
if ( root != NULL )
{
display ( root -> left ) ;
printf ( "%d\t", root -> data ) ;
display ( root -> right ) ;
}
}

/* deletes the tree */
void deltree ( struct AVLNode *root )
{
if ( root != NULL )
{
deltree ( root -> left ) ;
deltree ( root -> right ) ;
}
free ( root ) ;
}

Program to maintain a threaded binary tree.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

enum boolean
{
false = 0,
true = 1
} ;

struct thtree
{
enum boolean isleft ;
struct thtree *left ;
int data ;
struct thtree *right ;
enum boolen isright ;
} ;

void insert ( struct thtree **, int ) ;
void delete ( struct thtree **, int ) ;
void search ( struct thtree **, int, struct thtree **,
struct thtree **, int * ) ;
void inorder ( struct thtree * ) ;
void deltree ( struct thtree ** ) ;

void main( )
{
struct thtree *th_head ;

th_head = NULL ; /* empty tree */

insert ( &th_head, 11 ) ;
insert ( &th_head, 9 ) ;
insert ( &th_head, 13 ) ;
insert ( &th_head, 8 ) ;
insert ( &th_head, 10 ) ;
insert ( &th_head, 12 ) ;
insert ( &th_head, 14 ) ;
insert ( &th_head, 15 ) ;
insert ( &th_head, 7 ) ;

clrscr( ) ;
printf ( "Threaded binary tree before deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 10 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 14 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 8 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 13 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

deltree ( &th_head ) ;

getch( ) ;
}

/* inserts a node in a threaded binary tree */
void insert ( struct thtree **s, int num )
{
struct thtree *p, *z, *head = *s ;

/* allocating a new node */
z = malloc ( sizeof ( struct thtree ) ) ;

z -> isleft = true ; /* indicates a thread */
z -> data = num ; /* assign new data */
z -> isright = true ; /* indicates a thread */

/* if tree is empty */
if ( *s == NULL )
{
head = malloc ( sizeof ( struct thtree ) ) ;

/* the entire tree is treated as a left sub-tree of the head node */
head -> isleft = false ;
head -> left = z ; /* z becomes leftchild of the head node */
head -> data = -9999 ; /* no data */
head -> right = head ; /* right link will always be pointing
to itself */
head -> isright = false ;

*s = head ;

z -> left = head ; /* left thread to head */
z -> right = head ; /* right thread to head */
}
else /* if tree is non-empty */
{
p = head -> left ;

/* traverse till the thread is found attached to the head */
while ( p != head )
{
if ( p -> data > num )
{
if ( p -> isleft != true ) /* checking for a thread */
p = p -> left ;
else
{
z -> left = p -> left ;
p -> left = z ;
p -> isleft = false ; /* indicates a link */
z -> isright = true ;
z -> right = p ;
return ;
}
}
else
{
if ( p -> data < num )
{
if ( p -> isright != true )
p = p -> right ;
else
{
z -> right = p -> right ;
p -> right = z ;
p -> isright = false ; /* indicates a link */
z -> isleft = true ;
z -> left = p ;
return ;
}
}
}
}
}
}

/* deletes a node from the binary search tree */
void delete ( struct thtree **root, int num )
{
int found ;
struct thtree *parent, *x, *xsucc ;

/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}

parent = x = NULL ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == false )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
if ( x -> isleft == false && x -> isright == false )
{
parent = x ;
xsucc = x -> right ;

while ( xsucc -> isleft == false )
{
parent = xsucc ;
xsucc = xsucc -> left ;
}

x -> data = xsucc -> data ;
x = xsucc ;
}

/* if the node to be deleted has no child */
if ( x -> isleft == true && x -> isright == true )
{
/* if node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = *root ;
( *root ) -> isleft = true ;

free ( x ) ;
return ;
}

if ( parent -> right == x )
{
parent -> isright = true ;
parent -> right = x -> right ;
}
else
{
parent -> isleft = true ;
parent -> left = x -> left ;
}

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> isleft == true && x -> isright == false )
{
/* node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = x -> right ;
free ( x ) ;
return ;
}

if ( parent -> left == x )
{
parent -> left = x -> right ;
x -> right -> left = x -> left ;
}
else
{
parent -> right = x -> right ;
x -> right -> left = parent ;
}

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> isleft == false && x -> isright == true )
{
/* the node to be deleted is a root node */
if ( parent == NULL )
{
parent = x ;
xsucc = x -> left ;

while ( xsucc -> right == false )
xsucc = xsucc -> right ;

xsucc -> right = *root ;

( *root ) -> left = x -> left ;

free ( x ) ;
return ;
}

if ( parent -> left == x )
{
parent -> left = x -> left ;
x -> left -> right = parent ;
}
else
{
parent -> right = x -> left ;
x -> left -> right = x -> right ;
}

free ( x ) ;
return ;
}
}

/* returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct thtree **root, int num, struct thtree **par,
struct thtree **x, int *found )
{
struct thtree *q ;

q = ( *root ) -> left ;
*found = false ;
*par = NULL ;

while ( q != *root )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = true ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
{
if ( q -> isleft == true )
{
*found = false ;
x = NULL ;
return ;
}
q = q -> left ;
}
else
{
if ( q -> isright == true )
{
*found = false ;
*x = NULL ;
return ;
}
q = q -> right ;
}
}
}

/* traverses the threaded binary tree in inorder */
void inorder ( struct thtree *root )
{
struct thtree *p ;

p = root -> left ;

while ( p != root )
{
while ( p -> isleft == false )
p = p -> left ;

printf ( "%d\t", p -> data ) ;

while ( p -> isright == true )
{
p = p -> right ;

if ( p == root )
break ;

printf ( "%d\t", p -> data ) ;

}
p = p -> right ;
}
}

void deltree ( struct thtree **root )
{
while ( ( *root ) -> left != *root )
delete ( root, ( *root ) -> left -> data ) ;
}

Program to insert and delete a node from the binary search tree.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

#define TRUE 1
#define FALSE 0

struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **,
struct btreenode **, int * ) ;
void inorder ( struct btreenode * ) ;

void main( )
{
struct btreenode *bt ;
int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;

bt = NULL ; /* empty tree */

clrscr( ) ;

while ( i <= 8 )
{
insert ( &bt, a[i] ) ;
i++ ;
}
clrscr( ) ;
printf ( "Binary tree before deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 10 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 14 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 8 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 13 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}

/* deletes a node from the binary search tree */
void delete ( struct btreenode **root, int num )
{
int found ;
struct btreenode *parent, *x, *xsucc ;

/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}

parent = x = NULL ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
if ( x -> leftchild != NULL && x -> rightchild != NULL )
{
parent = x ;
xsucc = x -> rightchild ;

while ( xsucc -> leftchild != NULL )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}

x -> data = xsucc -> data ;
x = xsucc ;
}

/* if the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;

free ( x ) ;
return ;
}
}

/*returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct btreenode **root, int num, struct btreenode **par, struct
btreenode **x, int *found )
{
struct btreenode *q ;

q = *root ;
*found = FALSE ;
*par = NULL ;

while ( q != NULL )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path has
already been traversed */
printf ( "%d\t", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
}

Program to implement a binary search tree.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void inorder ( struct btreenode * ) ;
void preorder ( struct btreenode * ) ;
void postorder ( struct btreenode * ) ;

void main( )
{
struct btreenode *bt ;
int req, i = 1, num ;

bt = NULL ; /* empty tree */

clrscr( ) ;
printf ( "Specify the number of items to be inserted: " ) ;
scanf ( "%d", &req ) ;

while ( i++ <= req )
{
printf ( "Enter the data: " ) ;
scanf ( "%d", &num ) ;
insert ( &bt, num ) ;
}

printf ( "\nIn-order Traversal: " ) ;
inorder ( bt ) ;

printf ( "\nPre-order Traversal: " ) ;
preorder ( bt ) ;

printf ( "\nPost-order Traversal: " ) ;
postorder ( bt ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
return ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
return ;
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path
has already been traversed */
printf ( "\t%d", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
else
return ;
}

/* traverse a binary search tree in a DLR (Data-Left-right) fashion */
void preorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
/* print the data of a node */
printf ( "\t%d", sr -> data ) ;
/* traverse till leftchild is not NULL */
preorder ( sr -> leftchild ) ;
/* traverse till rightchild is not NULL */
preorder ( sr -> rightchild ) ;
}
else
return ;
}


/* traverse a binary search tree in LRD (Left-Right-Data) fashion */
void postorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
postorder ( sr -> leftchild ) ;
postorder ( sr -> rightchild ) ;
printf ( "\t%d", sr -> data ) ;
}
else
return ;
}

Program to build a binary search tree from an array.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

struct node
{
struct node *left ;
char data ;
struct node *right ;
} ;

struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;

char a[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H', '\0',
'\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
} ;

void main( )
{
struct node *root ;

clrscr( ) ;

root = buildtree ( 0 ) ;
printf ( "In-order Traversal:\n" ) ;
inorder ( root ) ;

getch( ) ;
}
struct node * buildtree ( int n )
{
struct node *temp = NULL ;
if ( a[n] != '\0' )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( 2 * n + 1 ) ;
temp -> data = a[n] ;
temp -> right = buildtree ( 2 * n + 2 ) ;
}
return temp ;
}

void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}

Program to build a binary search tree from arrays.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

struct node
{
struct node *left ;
char data ;
struct node *right ;
} ;

struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;

char arr[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' } ;
int lc[ ] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 } ;
int rc[ ] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 } ;

void main( )
{
struct node *root ;

clrscr( ) ;

root = buildtree ( 0 ) ;
printf ( “In-order Traversal:\n” ) ;
inorder ( root ) ;

getch( ) ;
}

struct node * buildtree ( int index )
{
struct node *temp = NULL ;
if ( index != -1 )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( lc[index] ) ;
temp -> data = arr[index] ;
temp -> right = buildtree ( rc[index] ) ;
}
return temp ;
}

void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}

Program to insert and delete a node from the binary search tree

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

#define TRUE 1
#define FALSE 0

struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **,
struct btreenode **, int * ) ;
void inorder ( struct btreenode * ) ;

void main( )
{
struct btreenode *bt ;
int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;

bt = NULL ; /* empty tree */

clrscr( ) ;

while ( i <= 8 )
{
insert ( &bt, a[i] ) ;
i++ ;
}
clrscr( ) ;
printf ( "Binary tree before deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 10 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 14 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 8 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 13 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}

/* deletes a node from the binary search tree */
void delete ( struct btreenode **root, int num )
{
int found ;
struct btreenode *parent, *x, *xsucc ;

/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}

parent = x = NULL ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
if ( x -> leftchild != NULL && x -> rightchild != NULL )
{
parent = x ;
xsucc = x -> rightchild ;

while ( xsucc -> leftchild != NULL )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}

x -> data = xsucc -> data ;
x = xsucc ;
}

/* if the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;

free ( x ) ;
return ;
}
}

/*returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct btreenode **root, int num, struct btreenode **par, struct
btreenode **x, int *found )
{
struct btreenode *q ;

q = *root ;
*found = FALSE ;
*par = NULL ;

while ( q != NULL )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path has
already been traversed */
printf ( "%d\t", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
}

Program to reconstruct a binary search tree.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

#define MAX 101

struct node
{
struct node *left ;
int data ;
struct node *right ;
} ;

void insert ( struct node **, int ) ;
void preorder ( struct node * ) ;
void postorder ( struct node * ) ;
void inorder ( struct node * ) ;
struct node * recons ( int *, int *, int ) ;
void deltree ( struct node * ) ;

int in[MAX], pre[MAX], x ;

void main( )
{
struct node *t, *p, *q ;
int req, i, num ;

t = NULL ; /* empty tree */

clrscr( ) ;
printf ( "Specify the number of items to be inserted: " ) ;
while ( 1 )
{
scanf ( "%d", &req ) ;
if ( req >= MAX || req <= 0 )
printf ( "\nEnter number between 1 to 100.\n" ) ;
else
break ;
}

for ( i = 0 ; i < req ; i++ )
{
printf ( "Enter the data: " ) ;
scanf ( "%d", &num ) ;
insert ( &t, num ) ;
}

printf ( "\nIn-order Traversal:\n" ) ;
x = 0 ;
inorder ( t ) ;

printf ( "\nPre-order Traversal:\n" ) ;
x = 0 ;
preorder ( t ) ;

printf ( "\nPost-order Traversal:\n" ) ;
x = 0 ;
postorder ( t ) ;

deltree ( t ) ;
t = NULL ;
t = recons ( in, pre, req ) ;

printf ( "\n\nAfter reconstruction of the binary tree.\n" ) ;

x = 0 ;
printf ( "\nIn-order Traversal:\n" ) ;
inorder ( t ) ;

x = 0 ;
printf ( "\nPre-order Traversal:\n" ) ;
preorder ( t ) ;
x = 0 ;
printf ( "\nPost-order Traversal:\n" ) ;
postorder ( t ) ;

deltree ( t ) ;
getch( ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct node **sr, int num )
{
if ( *sr == NULL )
{
*sr = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

( *sr ) -> left = NULL ;
( *sr ) -> data = num ;
( *sr ) -> right = NULL ;
return ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> left ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> right ), num ) ;
}
}

void preorder ( struct node *t )
{
if ( t != NULL )
{
printf ( "%d\t", pre[x++]= t -> data ) ;
preorder ( t -> left ) ;
preorder ( t -> right ) ;
}
}

void postorder ( struct node *t )
{
if ( t != NULL )
{
postorder ( t -> left ) ;
postorder ( t -> right ) ;
printf ( "%d\t", t -> data ) ;
}
}

void inorder ( struct node *t )
{
if ( t != NULL )
{
inorder ( t -> left ) ;
printf ( "%d\t", in[x++]= t -> data ) ;
inorder ( t -> right ) ;
}
}

struct node * recons ( int *inorder, int *preorder, int noofnodes )
{
struct node *temp, *left, *right ;
int tempin[100], temppre[100], i, j ;

if ( noofnodes == 0 )
return NULL ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> data = preorder[0] ;
temp -> left = NULL ;
temp -> right = NULL ;

if ( noofnodes == 1 )
return temp ;
for ( i = 0 ; inorder[i] != preorder[0] ; )
i++ ;

if ( i > 0 )
{
for ( j = 0 ; j <= i ; j++ )
tempin[j] = inorder[j] ;

for ( j = 0 ; j < i ; j++ )
temppre[j] = preorder[j + 1] ;
}

left = recons ( tempin, temppre, i ) ;
temp -> left = left ;

if ( i < noofnodes - 1 )
{
for ( j = i ; j < noofnodes - 1 ; j++ )
{
tempin[j - i] = inorder[j + 1] ;
temppre[j - i] = preorder[j + 1] ;
}
}

right = recons ( tempin, temppre, noofnodes - i - 1 ) ;
temp -> right = right ;

return temp ;
}

void deltree ( struct node *t )
{
if ( t != NULL )
{
deltree ( t -> left ) ;
deltree ( t -> right ) ;
}
free ( t ) ;
}

Program that implements a priority queue using an array.

#include <"stdio.h">
#include <"conio.h">

#define MAX 5

struct data
{
char job[MAX] ;
int prno ;
int ord ;
} ;

struct pque
{
struct data d[MAX] ;
int front ;
int rear ;
} ;

void initpque ( struct pque * ) ;
void add ( struct pque *, struct data ) ;
struct data delete ( struct pque * ) ;

void main( )
{
struct pque q ;
struct data dt, temp ;
int i, j = 0 ;

clrscr( ) ;

initpque ( &q ) ;

printf ( "Enter Job description (max 4 chars) and its priority\n" ) ;
printf ( "Lower the priority number, higher the priority\n" ) ;
printf ( "Job Priority\n" ) ;

for ( i = 0 ; i < MAX ; i++ )
{
scanf ( "%s %d", &dt.job, &dt.prno ) ;
dt.ord = j++ ;
add ( &q, dt ) ;
}
printf ( "\n" ) ;

printf ( "Process jobs prioritywise\n" ) ;
printf ( "Job\tPriority\n" ) ;

for ( i = 0 ; i < MAX ; i++ )
{
temp = delete ( &q ) ;
printf ( "%s\t%d\n", temp.job, temp.prno ) ;
}
printf ( "\n" ) ;

getch( ) ;
}

/* initialises data members */
void initpque ( struct pque *pq )
{
int i ;

pq -> front = pq -> rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
{
strcpy ( pq -> d[i].job, '\0' ) ;
pq -> d[i].prno = pq -> d[i].ord = 0 ;
}
}

/* adds item to the priority queue */
void add ( struct pque *pq, struct data dt )
{
struct data temp ;
int i, j ;

if ( pq -> rear == MAX - 1 )
{
printf ( "\nQueue is full." ) ;
return ;
}

pq -> rear++ ;
pq -> d[pq -> rear] = dt ;

if ( pq -> front == -1 )
pq -> front = 0 ;

for ( i = pq -> front ; i <= pq -> rear ; i++ )
{
for ( j = i + 1 ; j <= pq -> rear ; j++ )
{
if ( pq -> d[i].prno > pq -> d[j].prno )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
else
{
if ( pq -> d[i].prno == pq -> d[j].prno )
{
if ( pq -> d[i].ord > pq -> d[j].ord )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
}
}
}
}
}

/* removes item from priority queue */
struct data delete ( struct pque *pq )
{
struct data t ;
strcpy ( t.job, "" ) ;
t.prno = 0 ;
t.ord = 0 ;

if ( pq -> front == -1 )
{
printf ( "\nQueue is Empty.\n" ) ;
return t ;
}

t = pq -> d[pq -> front] ;
pq -> d[pq -> front] = t ;
if ( pq -> front == pq -> rear )
pq -> front = pq -> rear = -1 ;
else
pq -> front++ ;

return t ;
}

Program that implements deque using an array.

#include <"stdio.h">
#include <"conio.h">

#define MAX 10

void addqatbeg ( int *, int, int *, int * ) ;
void addqatend ( int *, int, int *, int * ) ;
int delqatbeg ( int *, int *, int * ) ;
int delqatend ( int *, int *, int * ) ;
void display ( int * ) ;
int count ( int * ) ;

void main( )
{
int arr[MAX] ;
int front, rear, i, n ;

clrscr( ) ;

/* initialises data members */
front = rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
arr[i] = 0 ;

addqatend ( arr, 17, &front, &rear ) ;
addqatbeg ( arr, 10, &front, &rear ) ;
addqatend ( arr, 8, &front, &rear ) ;
addqatbeg ( arr, -9, &front, &rear ) ;
addqatend ( arr, 13, &front, &rear ) ;
addqatbeg ( arr, 28, &front, &rear ) ;
addqatend ( arr, 14, &front, &rear ) ;
addqatbeg ( arr, 5, &front, &rear ) ;
addqatend ( arr, 25, &front, &rear ) ;
addqatbeg ( arr, 6, &front, &rear ) ;
addqatend ( arr, 21, &front, &rear ) ;
addqatbeg ( arr, 11, &front, &rear ) ;

printf ( "\nElements in a deque: " ) ;
display ( arr ) ;

n = count ( arr ) ;
printf ( "\nTotal number of elements in deque: %d", n ) ;

i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;

i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted:%d", i ) ;

i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted:%d", i ) ;

i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;

printf ( "\nElements in a deque after deletion: " ) ;
display ( arr ) ;

addqatend ( arr, 16, &front, &rear ) ;
addqatend ( arr, 7, &front, &rear ) ;

printf ( "\nElements in a deque after addition: " ) ;
display ( arr ) ;

i = delqatend ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;

i = delqatend ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;

printf ( "\nElements in a deque after deletion: " ) ;
display ( arr ) ;

n = count ( arr ) ;
printf ( "\nTotal number of elements in deque: %d", n ) ;

getch( ) ;
}

/* adds an element at the beginning of a deque */
void addqatbeg ( int *arr, int item, int *pfront, int *prear )
{
int i, k, c ;

if ( *pfront == 0 && *prear == MAX - 1 )
{
printf ( "\nDeque is full.\n" ) ;
return ;
}

if ( *pfront == -1 )
{
*pfront = *prear = 0 ;
arr[*pfront] = item ;
return ;
}

if ( *prear != MAX - 1 )
{
c = count ( arr ) ;
k = *prear + 1 ;
for ( i = 1 ; i <= c ; i++ )
{
arr[k] = arr[k - 1] ;
k-- ;
}
arr[k] = item ;
*pfront = k ;
( *prear )++ ;
}
else
{
( *pfront )-- ;
arr[*pfront] = item ;
}
}

/* adds an element at the end of a deque */
void addqatend ( int *arr, int item, int *pfront, int *prear )
{
int i, k ;

if ( *pfront == 0 && *prear == MAX - 1 )
{
printf ( "\nDeque is full.\n" ) ;
return ;
}

if ( *pfront == -1 )
{
*prear = *pfront = 0 ;
arr[*prear] = item ;
return ;
}

if ( *prear == MAX - 1 )
{
k = *pfront - 1 ;
for ( i = *pfront - 1 ; i < *prear ; i++ )
{
k = i ;
if ( k == MAX - 1 )
arr[k] = 0 ;
else
arr[k] = arr[i + 1] ;
}
( *prear )-- ;
( *pfront )-- ;
}
( *prear )++ ;
arr[*prear] = item ;
}

/* removes an element from the *pfront end of deque */
int delqatbeg ( int *arr, int *pfront, int *prear )
{
int item ;

if ( *pfront == -1 )
{
printf ( "\nDeque is empty.\n" ) ;
return 0 ;
}

item = arr[*pfront] ;
arr[*pfront] = 0 ;

if ( *pfront == *prear )
*pfront = *prear = -1 ;
else
( *pfront )++ ;

return item ;
}

/* removes an element from the *prear end of the deque */
int delqatend ( int *arr, int *pfront, int *prear )
{
int item ;

if ( *pfront == -1 )
{
printf ( "\nDeque is empty.\n" ) ;
return 0 ;
}

item = arr[*prear] ;
arr[*prear] = 0 ;
( *prear )-- ;
if ( *prear == -1 )
*pfront = -1 ;
return item ;
}

/* displays elements of a deque */
void display ( int *arr )
{
int i ;

printf ( "\n front->" ) ;
for ( i = 0 ; i < MAX ; i++ )
printf ( "\t%d", arr[i] ) ;
printf ( " <-rear" ) ;
}

/* counts the total number of elements in deque */
int count ( int *arr )
{
int c = 0, i ;

for ( i = 0 ; i < MAX ; i++ )
{
if ( arr[i] != 0 )
c++ ;
}
return c ;
}

Program that implements circular queue as an array.

#include <"stdio.h">
#include <"conio.h">

#define MAX 10

void addq ( int *, int, int *, int * ) ;
int delq ( int *, int *, int * ) ;
void display ( int * ) ;

void main( )
{
int arr[MAX] ;
int i, front, rear ;

clrscr( ) ;

/* initialise data member */
front = rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
arr[i] = 0 ;

addq ( arr, 14, &front, &rear ) ;
addq ( arr, 22, &front, &rear ) ;
addq ( arr, 13, &front, &rear ) ;
addq ( arr, -6, &front, &rear ) ;
addq ( arr, 25, &front, &rear ) ;

printf ( "\nElements in the circular queue: " ) ;
display ( arr ) ;

i = delq ( arr, &front, &rear ) ;
printf ( "Item deleted: %d", i ) ;

i = delq ( arr, &front, &rear ) ;
printf ( "\nItem deleted: %d", i ) ;

printf ( "\nElements in the circular queue after deletion: " ) ;
display ( arr ) ;

addq ( arr, 21, &front, &rear ) ;
addq ( arr, 17, &front, &rear ) ;
addq ( arr, 18, &front, &rear ) ;
addq ( arr, 9, &front, &rear ) ;
addq ( arr, 20, &front, &rear ) ;

printf ( "Elements in the circular queue after addition: " ) ;
display ( arr ) ;

addq ( arr, 32, &front, &rear ) ;

printf ( "Elements in the circular queue after addition: " ) ;
display ( arr ) ;

getch( ) ;
}

/* adds an element to the queue */
void addq ( int *arr, int item, int *pfront, int *prear )
{
if ( ( *prear == MAX - 1 && *pfront == 0 ) || ( *prear + 1 == *pfront ) )
{
printf ( "\nQueue is full." ) ;
return ;
}

if ( *prear == MAX - 1 )
*prear = 0 ;
else
( *prear )++ ;

arr[*prear] = item ;

if ( *pfront == -1 )
*pfront = 0 ;
}

/* removes an element from the queue */
int delq ( int *arr, int *pfront, int *prear )
{
int data ;

if ( *pfront == -1 )
{
printf ( "\nQueue is empty." ) ;
return NULL ;
}

data = arr[*pfront] ;
arr[*pfront] = 0 ;

if ( *pfront == *prear )
{
*pfront = -1 ;
*prear = -1 ;
}
else
{
if ( *pfront == MAX - 1 )
*pfront = 0 ;
else
( *pfront )++ ;
}
return data ;
}

/* displays element in a queue */
void display ( int * arr )
{
int i ;
printf ( "\n" ) ;
for ( i = 0 ; i < MAX ; i++ )
printf ( "%d\t", arr[i] ) ;
printf ( "\n" ) ;
}

Program that implements queue as a linked list.

#include
#include

struct node
{
int data ;
struct node *link ;
} ;

struct queue
{
struct node *front ;
struct node *rear ;
} ;

void initqueue ( struct queue * ) ;
void addq ( struct queue *, int ) ;
int delq ( struct queue * ) ;
void delqueue ( struct queue * ) ;

void main( )
{
struct queue a ;
int i ;

clrscr( ) ;

initqueue ( &a ) ;

addq ( &a, 11 ) ;
addq ( &a, -8 ) ;
addq ( &a, 23 ) ;
addq ( &a, 19 ) ;
addq ( &a, 15 ) ;
addq ( &a, 16 ) ;
addq ( &a, 28 ) ;

i = delq ( &a ) ;
printf ( "\nItem extracted: %d", i ) ;

i = delq ( &a ) ;
printf ( "\nItem extracted: %d", i ) ;

i = delq ( &a ) ;
printf ( "\nItem extracted: %d", i ) ;

delqueue ( &a ) ;

getch( ) ;
}

/* initialises data member */
void initqueue ( struct queue *q )
{
q -> front = q -> rear = NULL ;
}

/* adds an element to the queue */
void addq ( struct queue *q, int item )
{
struct node *temp ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
if ( temp == NULL )
printf ( "\nQueue is full." ) ;

temp -> data = item ;
temp -> link = NULL ;

if ( q -> front == NULL )
{
q -> rear = q -> front = temp ;
return ;
}

q -> rear -> link = temp ;
q -> rear = q -> rear -> link ;
}

/* removes an element from the queue */
int delq ( struct queue * q )
{
struct node *temp ;
int item ;

if ( q -> front == NULL )
{
printf ( "\nQueue is empty." ) ;
return NULL ;
}

item = q -> front -> data ;
temp = q -> front ;
q -> front = q -> front -> link ;
free ( temp ) ;
return item ;
}

/* deallocates memory */
void delqueue ( struct queue *q )
{
struct node *temp ;

if ( q -> front == NULL )
return ;

while ( q -> front != NULL )
{
temp = q -> front ;
q -> front = q -> front -> link ;
free ( temp ) ;
}
}