Tweet
#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 ** ) ;
main( )
{
struct thtree *th_head ;
th_head = NULL ; /* empty tree */
insert ( &th_head, 25 ) ;
insert ( &th_head, 94 ) ;
insert ( &th_head, 15 ) ;
insert ( &th_head, 85) ;
insert ( &th_head, 102 ) ;
insert ( &th_head, 125 ) ;
insert ( &th_head, 176 ) ;
insert ( &th_head, 159 ) ;
insert ( &th_head, 767 ) ;
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 ) ;
}
void insert ( struct thtree **s, int num )
{
struct thtree *p, *z, *head = *s ;
z = malloc ( sizeof ( struct thtree ) ) ;
z -> isleft = true ; /* indicates a thread */
z -> data = num ; /* assign new data */
z -> isright = true ; /* indicates a thread */
if ( *s == NULL )
{
head = malloc ( sizeof ( struct thtree ) ) ;
head -> isleft = false ;
head -> left = z ;
head -> data = -9999 ;
head -> right = head ;
head -> isright = false ;
*s = head ;
z -> left = head ;
z -> right = head ;
}
else
{
p = head -> left ;
while ( p != head )
{
if ( p -> data > num )
{
if ( p -> isleft != true )
p = p -> left ;
else
{
z -> left = p -> left ;
p -> left = z ;
p -> isleft = false ;
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 ;
z -> isleft = true ;
z -> left = p ;
return ;
}
}
}
}
}
}
void delete ( struct thtree **root, int num )
{
int found ;
struct thtree *parent, *x, *xsucc ;
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}
parent = x = NULL ;
search ( root, num, &parent, &x, &found ) ;
if ( found == false )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}
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 ( x -> isleft == true && x -> isright == true )
{
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 ( x -> isleft == true && x -> isright == false )
{
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 ( x -> isleft == false && x -> isright == true )
{
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 ;
}
}
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 ( 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 ;
}
}
}
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 ) ;
}
Threaded Binary Tree in C Programming
