Threaded Binary Tree in C Programming

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

Top