C Program to implement a Binary Search Tree

      /* Program to implement a binary search tree. */
        #include <stdio.h>
        #include <stdlib.h>

        struct treenode
        {
            int data;
            struct treenode  *left;
            struct treenode  *right;
        };
        typedef struct treenode *tnode;
     
     tnode makeempty( tnode t )
        {
            if( t != NULL )
            {
                makeempty( t->left );
                makeempty( t->right );
                free( t );
            }
            return NULL;
        }

     tnode find( int x, tnode t )
        {
            if( t == NULL )
                return NULL;
            if( x < t->data )
                return find( x, t->left );
            else
            if( x > t->data )
                return find( x, t->right );
            else
                return t;
        }

     tnode findmin( tnode t )
        {
            if( t == NULL )
                return NULL;
            else
            if( t->left == NULL )
                return t;
            else
                return findmin( t->left );
        }

     tnode findmax( tnode t )
        {
            if( t != NULL )
                while( t->right != NULL )
                    t = t->right;

            return t;
        }

       




tnode insert( int x, tnode t )
        {
/* 1*/      if( t == NULL )
            {
                /* Create and return a one-node tree */
/* 2*/          t = malloc( sizeof( struct treenode ) );
/* 3*/          if( t == NULL )
/* 4*/              printf( "Out of space!!!" );
                else
                {
/* 5*/              t->data = x;
/* 6*/              t->left = t->right = NULL;
                }
            }
            else
/* 7*/      if( x < t->data )
/* 8*/          t->left = insert( x, t->left );
            else
/* 9*/      if( x > t->data )
/*10*/          t->right = insert( x, t->right );
            /* Else x is in the tree already; we'll do nothing */
            //printf("\nlast statement in insert\n");
/*11*/      return t;  /* Do not forget this line!! */
        }

     tnode delete( int x, tnode t )
        {
            tnode tmpCell;

            if( t == NULL )
                printf( "data not found" );
            else
            if( x < t->data )  /* Go left */
                t->left = delete( x, t->left );
            else
            if( x > t->data )  /* Go right */
                t->right = delete( x, t->right );
            else  /* Found data to be deleted */
            if( t->left && t->right )  /* two children */
            {
                /* Replace with smallest in right subtree */
                tmpCell = findmin( t->right );
                t->data = tmpCell->data;
                t->right = delete( t->data, t->right );
            }
            else  /* One or zero children */
            {
                tmpCell = t;
                if( t->left == NULL ) /* Also handles 0 children */
                    t = t->right;
                else if( t->right == NULL )
                    t = t->left;
                free( tmpCell );
            }

            return t;
        }


       
int retrieve( tnode p )
        {
            return p->data;
        }
        /* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
     void inorder (tnode sr )
        {
            if ( sr != NULL )
            {
                  inorder ( sr -> left ) ;
       
/* print the data of the node whose leftchild is NULL or the path has already been traversed */
                  printf ( "\t%d", sr -> data ) ;
        
                  inorder ( sr -> right ) ;
            }
            else
                  return ;
        }
main( )
{
    tnode t,p;
    int i;
    int j = 7;

    t = makeempty( NULL );
    for( i = 0; i < 10; i++, j = ( j + 7 ) % 10 )
        t = insert( j, t );
    inorder (t);
    for( i = 0; i < 10; i += 2 )
        {
        printf( " \n delete %d from BST tree \n", i );
        t = delete( i, t );
        }
    inorder (t);
    for( i = 1; i < 10; i += 2 )
        if( ( p = find( i, t ) ) == NULL || retrieve( p ) != i )
            printf( "Error at %d\n", i );
    for( i = 0; i < 10; i += 2 )
        if( ( p = find( i, t ) ) != NULL )
            printf( "Error at %d\n", i );
    printf( "\nMin is %d, Max is %d\n", retrieve( findmin( t ) ),
               retrieve( findmax( t ) ) );


    return 0;
}
Bhanu Namikaze

Bhanu Namikaze is an Ethical Hacker, Security Analyst, Blogger, Web Developer and a Mechanical Engineer. He Enjoys writing articles, Blogging, Debugging Errors and Capture the Flags. Enjoy Learning; There is Nothing Like Absolute Defeat - Try and try until you Succeed.

No comments:

Post a Comment