## DataStructure-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 ) ;

}