Code for Program to maintain a threaded binary tree in C Programming

Code for Program to maintain a 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 ** ) ;

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