Source Code : Program to implement a binary search tree.

_{/* Program to implement a binary search tree. */}

_#include

_#include

_#include

_{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 ;}

_}