Tuesday, June 2, 2009

Program to implement a binary search tree.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void inorder ( struct btreenode * ) ;
void preorder ( struct btreenode * ) ;
void postorder ( struct btreenode * ) ;

void main( )
{
struct btreenode *bt ;
int req, i = 1, num ;

bt = NULL ; /* empty tree */

clrscr( ) ;
printf ( "Specify the number of items to be inserted: " ) ;
scanf ( "%d", &req ) ;

while ( i++ <= req )
{
printf ( "Enter the data: " ) ;
scanf ( "%d", &num ) ;
insert ( &bt, num ) ;
}

printf ( "\nIn-order Traversal: " ) ;
inorder ( bt ) ;

printf ( "\nPre-order Traversal: " ) ;
preorder ( bt ) ;

printf ( "\nPost-order Traversal: " ) ;
postorder ( bt ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
return ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
return ;
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path
has already been traversed */
printf ( "\t%d", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
else
return ;
}

/* traverse a binary search tree in a DLR (Data-Left-right) fashion */
void preorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
/* print the data of a node */
printf ( "\t%d", sr -> data ) ;
/* traverse till leftchild is not NULL */
preorder ( sr -> leftchild ) ;
/* traverse till rightchild is not NULL */
preorder ( sr -> rightchild ) ;
}
else
return ;
}


/* traverse a binary search tree in LRD (Left-Right-Data) fashion */
void postorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
postorder ( sr -> leftchild ) ;
postorder ( sr -> rightchild ) ;
printf ( "\t%d", sr -> data ) ;
}
else
return ;
}

No comments:

Post a Comment

Please Give Some Comment

Featured post

Sitecore 10 Installation on Docker