BST

/* bst.cpp*/
#include<iostream.h>
#include<conio.h>
#include<process.h>

struct rec
{
long num;
struct rec *left;
struct rec *right;
};

struct rec *tree;

class ctree{
public: struct rec *delnum(long,struct rec *);
struct rec *insert(struct rec *,long);
struct rec *deletenode(long,struct rec *);
void search(struct rec *,long);
void preorder(struct rec *);
void inorder(struct rec *);
void postorder(struct rec *);
int select();
ctree()
{
tree=NULL;
}
};

void main()
{
int choice;
long digit;
int element;
ctree ct;
clrscr();
do
 {
choice=ct.select();
switch(choice)
{
  case 1: cout<<"Enter integer: To quit enter 0"<<endl;
  cin>>digit;
  while(digit!=0)
{
  tree=ct.insert(tree,digit);
  cin>>digit;
}continue;
  case 2: cout<<"Enter the number to be search";
  cin>>digit;
  ct.search(tree,digit);
  continue;
  case 3: cout<<endl<<"preorder traversing TREE";
  ct.preorder(tree);continue;
  case 4: cout<<endl<<"inorder traversing TREE";
  ct.inorder(tree);continue;
  case 5: cout<<endl<<"postorder traversing TREE";
  ct.postorder(tree);continue;
  case 6: cout<<"Enter element which do you want delete from  the BST";
   cin>>digit;
  ct.deletenode(digit,tree);continue;
  case 7: cout<<"END";
  exit(0);
}
}while(choice!=7);
}

int ctree::select()
{
int selection;
do
 {
cout<<endl<<"Enter 1: Insert a node in the BST";
cout<<endl<<"Enter 2: Search a node in BST";
cout<<endl<<"Enter 3: Display(preorder)the BST";
cout<<endl<<"Enter 4: Display(inorder)the BST";
cout<<endl<<"Enter 5: Display(postorder) the BST";
cout<<endl<<"Enter 6: Delete the element";
cout<<endl<<"Enter 7: END";
cout<<endl<<"Enter your choice ";
cin>>selection;
    if((selection<1)||(selection>7))
{
 cout<<"wrong choice:Try again";
 getch(); }
  }while((selection<1)||(selection>7));
  return (selection);
}

struct rec * ctree::insert(struct rec *tree,long digit)
{
if(tree==NULL)
 {
tree=new(struct rec);
tree->left=tree->right=NULL;
tree->num=digit;
 }
     else
 if(digit<tree->num)
tree->left=insert(tree->left,digit);
     else
 if(digit>tree->num)
tree->right=insert(tree->right,digit);
     else if(digit==tree->num)
   {
      cout<<"Duplicate node:program exited";
      exit(0);
   }
   return(tree);
}

//copy from here
struct rec * ctree::delnum(long digit,struct rec *r)
{
struct rec *q;
if(r->right!=NULL)delnum(digit,r->right);
else
q->num=r->num;
q=r;
r=r->left;
}

struct rec * ctree::deletenode(long digit,struct rec *tree)
{
struct rec *r,*q;
if(tree==NULL)
{
cout<<endl<<"Tree is empty.";
exit(0);
}
if(digit<tree->num)
deletenode(digit,tree->left);
else
if(digit>tree->num)deletenode(digit,tree->right);
q=tree;
if((q->right==NULL)&&(q->left==NULL))
q=NULL;
else
if(q->right==NULL)tree=q->left;else
if(q->left==NULL)tree=tree=q->right;else
delnum(digit,q->left);
delete(q);
}

void ctree::search(struct rec *tree,long digit)
{
if(tree==NULL)
  cout<<"The number does not exits"<<endl;
   else
if(digit==tree->num)
cout<<endl<<"Number is "<<digit;
   else
if(digit<tree->num)
  search(tree->left,digit);
   else
 search(tree->right,digit);
}

void ctree::preorder(struct rec *tree)
{
if(tree!=NULL)
 {
cout<<endl<<tree->num;
preorder(tree->left);
preorder(tree->right);
 }
}

void ctree::inorder(struct rec *tree)
{
if(tree!=NULL)
   {
inorder(tree->left);
cout<<endl<<tree->num;
inorder(tree->right);
   }
}

void ctree::postorder(struct rec *tree)
{
if(tree!=NULL)
 {
postorder(tree->left);
postorder(tree->right);
cout<<endl<<tree->num;
 }

}

/*The output of the above program is:-

Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 1
Enter integer: To quit enter 0
82
77
90
346
0

Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 2

Number is 35
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 3

preorder traversing TREE
82
77
35
90
346
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 4

inorder traversing TREEE
35
77
82
90
346
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 5

postorder traversing TREE
35
77
346
90
82
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 6
Enter element which do you want delete from  the BST82

Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 7*/
------------------------------------------------------------------------------------------------------------


//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);
};
//t7(3).wav
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);
}

//t8(3).wav
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;
  }
}
}
}
//t8(6).wav
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
}
//t8(4)
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;
 }
}
//a.traverse();
//t10.wav(2)
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();
}//destructor is called before object a is lost