#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;
}
No comments:
Post a Comment