How to maintain a Threaded Binary Tree

C 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 ) ;
}