Binary Search Tree (BST)

//BINARY SEARCH TREE TRAVERSAL EXAMPLES
//EXAMPLE 1: PREORDER,INORDER POSTORDER,SEARCH


//
//binary search traversal by using recursive method
#include<iostream.h>
#include<conio.h>
#include<stdio.h>//null is macro, defined in stdio.h
template <class T>
class node
{
 node<T> * lchild;//lchild contain addrss of left child
 T data;//data field contains value
 node<T> * rchild;
 friend class tree<T>;//we can access lchild, data,rchild from tree class
//we can access lchild, data,rchild from these functions
 friend void rpreorder(node<T> *p);
 friend void rpostorder(node<T> *p);
 friend void rinorder(node<T> *p);
};

template<class T>
class tree
{
 private:
  node<T> *root;//root is a pointer to root node
 public:
   tree();
   ~tree();
  int isempty();
  void create();
  void traverse();
  void rpreorder();
  void rinorder();
  void rpostorder();
  node<t> * search(T x);
  void insert(node<T> *k);
};
template<class T>
tree<T>::tree()
{
 root=NULL;
}
template <class T>
int tree<T>::isempty()
{
 return(root==NULL);
}

//
template <class T>

void tree<T>::rpreorder(node<T> *p)
{
    if( p != NULL)
    {
        cout<<p->data);
        rpreorder(p->lchild);
        rpreorder(p->rchild);
    }
}
//rpreorder(root);
template <class T>

void tree<T>::rinorder(node<T> *p)
{
    if(p != NULL)
    {
        rinorder(p->left);
        cout<<p->data;
        rinorder(p->right);
    }
}

template <class T>

void tree<T>::rpostorder(node<T> *p)
{
    if( p != NULL)
    {
        rpostorder(p->left);
        rpostorder(p->right);
        cout<<p->data);
    }
}
template <class T>
node<T>* tree<T>::search(T x)//X IS VALUE 2 BE SEARCHD IN DA BINARY TREE
{
 node<t> *p;
 p=root;       //P POINTS TO ROOT NODE
 while(p!=NULL)//SEARCH FOR X IN THE TREE UNTIL BECOMES NULL
 {
  if(x==p->data) //IF X IS FOUND IN NODE P, RETURN ADRESS OF THT NODE
    return(p);
  else
  if(x<p->data)  //SEARCH FOR X IN LEFT SUB TREE
   p=p->lchild; // MOVE POINTER P TO LEFT CHILD
  else          //SEARCH FOR X IN THE RIGHT SUB TREE
   p=p->rchild; //MOVE POINTER TO RIGHT CHILD
 }
 return(NULL);//X IS NOT FOUND IN THE TREE
}

template<class T>
void tree<T>::insert(node,T> *k)//k is poiner to node to be inserted
{
 node<T> *p;
 if(isempty())//IF TREE IS EMPTY, NODE K IS ROOT NODE
 {
  root=k;//ROOT PTR TO THE NEW NODE
  return;//SKIP REST OF THE FUNCTION
 }
 p=root;//P POINTS TO ROOT NODE
 while(1)//ALWAYS TRUE
 {
  if(k->data<p->data)//INSERT NODE K IN THE LEFT SUB TREE
  {
   if(p->lchild!=NULL)//IF LEFT CHILD EXISTS, MOVE PTR P TO LEFTCHILD
 
    p=p->lchild;
 
   else//IF THERE IS NO LEFT CHILD, NODE K BECOMES LEFT CHILD OF P
   {
    p->lchild=k;//ATTACH NODE K AS LEFT CHILD OF P
    return;//COME OUT OF FUNCTION TO AVOID INFINITE LOOP
   }
  }
  else
  if(k-data>p->data)//INSERT NODE K IN THE RIGHT SUB TREE
  {
   if(p->rchild!=NULL)//IF RIGHT CHILD EXISTS,MOVE PTR P TO RIGHTCHILD
     p=p->rchild;
   else//IF THERE IS NO RIGHT CHILD K BECOMES RIGHT CHILD OF P
   {
    p->rchild=k;//ATTACH NODE K AS RIGHT CHILD OF P
    return;//COME OUT OF FUNCTION SOON AFTER INSERTION
   }//VALUE ALREADY EXISTS IN THE TREE
  }
  else
  {
   cout<<k->data<<"already exists. Insertion is not possible\n";
   return;
  }
}
}
}

template <class T>
void tree<T>::create()
{
 T x;
 node<T> *k;
 root=NULL;//initially tree is empty
 cout<<"ENTER VALUE TERMINATES BY -1 OR !\n";
 cin>>x;//read the 1st no's which is root node
 while(x!=-1&&x!='!')//execute loop until user types -1 or !
 {
  k=new node<T>; //create a node, k is pointer to it
  k->data=x;//store x in the new node data field
  k->lchild=k->rchild=NULL;//initially node k is leaf node
  insert(k);//isnert node k in binary tree in appropriate place
  cin>>x;//read next number
 }
}

void menu1()
{
 cout<<"1. rpreorder\n";  
 cout<<"2. rinorder\n";
 cout<<"3. rpostorder\n";
 cout<<"4. exit\n"; //levelorder() is not wrote
}

template <class T>
void tree<T>::traverse()
{
 int ch;
 clrscr();
 menu1();
 cout<<"enter ur choice\n";
 cin>>ch;
 while(ch<5)
 {
  switch(ch)
  {
   case 1: {
           rpreorder();//calling recursive() from intermediate fun
           break;
           }
   case 2: {
           rinorder();
           break;
           }
   case 3: {
           rpostorder();
           break;
           }
  }
  menu1();
  cout<<"enter ur choice\n";
  cin>>ch;
 }
}

void main()
{
 node<int> *p;
 int ch, x;
 tree<int>a;
 clrscr();
 a.create();
 clrscr();

 cout<<"enter ur choice 1. traverse \n 2. search";
 cin>>ch;
 while(ch<3)
 {
  switch(ch)
  {
    case 1: {
 //traverwse binary tree in tree, pose, inorder
//it is a intermediate function
            a.traverse();
            break;
    case 2: {
            cout<<"enter value to be searched \n";
            cin>>x;
            p=a.search(x);//it returns adres of dat node whre x is found
            if(p==NULL)
         
             cout<<"it is not found\n";
            else
              cout<,"it is found at address="<<p<<"\n";
            break;
            }
   }//switch
  cout<<"enter ur choice 1. traverse \n 2. search";
  cin>>ch;
}//while
getch();
}//


//EXAMPLE 2:




#include<iostream.h>
#include<conio.h>
#include<process.h>
class BST
{                                                              

  struct node
  {
   int data;
   node *rlink,*llink;
  };
  node *root,*temp,*n;
  public:BST()
  {
  root=NULL;
  }
  void insert(int);
  void search(int);
  void inorder(node *);
  void inordertrav();
}; // void inordertrav(int);
void BST::insert(int x)
{
  n=new node;
  n->data=x;
  n->llink=n->rlink=NULL;
  if(root==NULL)
    root=n;
  else
  {
    temp=root;
    while(temp!=NULL)
    {
     if(n->data<temp->data)
     {
       if(temp->llink!=NULL)
temp=temp->llink;
       else
       {
temp->llink=n;
temp=NULL;
       }
      }
      else
      {
       if(temp->rlink!=NULL)
temp=temp->rlink;
       else
       {
temp=n;
temp=NULL;
       }
      }
   }//outer if
 }//while
}//function
void BST::search(int s)
{
if(root==NULL)
cout<<"tree is empty"<<endl;
else
{
temp=root;
while(temp!=NULL)
{
if(s==temp->data)
{
cout<<"element found"<<endl;
break;
}
else
{
if(s<temp->data)
temp=temp->llink;
else
temp=temp->llink;
}
}
if(temp==NULL)
{
cout<<"element not found"<<endl;
}
}
}

void BST::inordertrav()
{
if(root==NULL)
{
cout<<"BST is empty"<<endl;
}
else
{
inorder(root);
}
}
void BST::inorder(node *temp)
{
inorder(temp->llink);
cout<<temp->data;
inorder(temp->rlink);
}
void main()
{
 int ch,x;
 BST b;
 clrscr();//clear
 cout<<"1.insertion\t 2.search\t 3.display(inorder)\t 4.exit\n";
 cout<<"enter ur choice\n";
 cin>>ch;
 do
 {
 switch(ch)
 {
 case 1:cout<<"enter elements\n";
 cin>>x;
 b.insert(x);
 break;
 case 2:cout<<"enter searching element\n";
 cin>>x;
 b.search(x);
 break;
 case 3:cout<<"BST elements(inorder)"<<endl;
 b.inordertrav();

 break;
 case 4:exit(0);
 }
 } while(ch<=4);
 getch();
}