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, Web Developer, Student and Mechanical Engineer. He Enjoys writing articles, Blogging, Solving Errors and Social Networking. Feel Free to let me know any of your concerns about hacking or let me know if you need any more methods on hacking anything. Enjoy Learning

No comments:

Post a Comment