BINARY_SEARCH_TREE

BINARY SEARCH TREE

HOME
/*PROGRAM
TO IMPLEMENT BINARY SEARCH TREE*/


#include<iostream.h>
#include<conio.h>

class
tree;

class
stack  //CLASS
DECLARATION

{
  
 tree* pointer;

  
 stack *top;

public:
  
 stack()

  
 {

  
     top=NULL;

  
 }

  
 void push(tree* i)

  
 {

  
     stack *p;

  
     p= new stack;

  
     p->pointer =i;

  
     p->top = top;

  
     top = p;

  
 }

  
 tree* pop()

  
 {

  
     tree* temp;

  
     stack *tempp;

  
     temp  =
top->pointer;

  
     tempp = top->top;

  
     delete top;

  
     top = tempp;

  
     return temp;

  
 }

  
 int empty();

};

int
stack::empty()

{
  
 if(top == NULL)

  
     return 1;

  
 return 0;

}

class
tree

{
  
 int data;

  
 tree* left;

  
 tree* right;

public:
  
 tree()

  
 {

  
     left = NULL;

  
     right = NULL;

  
     data =0;

  
 }

  
 void in_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

  
 while(p != NULL || !s.empty())

  
 {

  
 while( p!= NULL)

  
 {

  
 s.push(p);

  
 p = p->left;

  
 }

  
 if(!s.empty())

  
 {

  
 p = s.pop();

  
 cout<<p->data<<” “;

  
 p = p->right;

  
 }

       
}

  
 }

  
 void pre_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 s.push(this);

  
 while(!s.empty())

  
 {

  
 p = s.pop();

  
 while(p != NULL)

  
 {

  
 cout<<p->data<< ” “;

  
 if(p->right != NULL)

  
 s.push(p->right);

  
 p = p->left;

  
 }

  
 }

  
 }

  
 void post_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

  
 while(1)

  
 {

  
 while( p != NULL)

  
 {

  
 p->data = -p->data;

  
 s.push(p);

  
 p = p->left;

  
 }

  
         

    
if(s.empty())

  
 return;

  
 p = s.pop();

  
 while(p->data > 0)

  
 {

  
 cout<<p->data<<” “;

  
 if(s.empty())

  
 return;

  
 p= s.pop();

  
 }

  
 p->data = -p->data;

  
 s.push(p);

  
 p = p->right;

  
 }

  
 }

  
 

  
 void deletion(int i)

  
 {

  
 int flag=0;

  
 tree *p,*q;

  
 p = this;

  
 while( p!= NULL)

  
 {

  
  if(i < p->data)

  
 {

  
 q=p;

  
 p= p->left;

  
 }

       
else if(i > p->data)

  
 {

  
 q=p;

  
 p=p->right;

  
 }

  
  else if(i== p->data)

  
 {

  
 flag=1;

  
 break;

  
 }

       
}

  
 if(flag == 0)

  
 {

  
 cout<<endl<<i<<”
not in the list.

          &nb

sp;           &n

bsp; 
no deletion performed.”;
  
 return;

  
 }

          &nb

sp;   // if deleting
element is root

  
 if(i == data)    

  
 {

  
 if(p->right == NULL)

  
 {//replace
with in-order predecessor

  
 int temp;

  
 temp =p->left->max();

  
 p->deletion(temp);

  
 p->data = temp;

  
 return;

  
 }

  
 else if(p->left == NULL)

  
 {//replace
with in-order successor

  
 int temp;

  
 temp = p->right->min();

  
 p->deletion(temp);

  
 p->data = temp;

  
 return;

  
 }

  
 }

  
 // p has no
children.

  
 if(p->right == NULL && p->left
== NULL)

  
 {

  
 if(q->right == p)

  
 q->right = NULL;

  
 else

  
 q->left  = NULL;

  
 delete p;

  
 }

  
 //p has
only one child.

  
 else if( p->right == NULL)

  
 {

  
 if(q->right == p)

  
 q->right = p->left;

  
 else

  
 q->left  = p->left;

  
 delete p;

  
 }

  
 else if( p->left == NULL)

  
 {

  
 if(q->right == p)

  
 q->right = p->right;

  
 else

  
 q->left  = p->right;

  
 delete p;

  
 }

  
 //p have
both children.

  
 else

  
 {

  
  int temp;

  
  temp = p->left->max();

  
  p->deletion(temp);

  
  p->data = temp;

  
 }

  
 }

  
 int max()

  
 {

  
 tree *p = this;

  
 while(p->right != NULL)

  
       
 p = p->right;

  
 return p->data;

  
 }

  
 int min()

  
 {

  
 tree *p = this;

  
     

  
 while(p->left != NULL)

  
       
 p = p->left;

  
 return p->data;

  
 }

  
 void insert(int i)

  
 {

  
 if(data == 0)//null
tree checking

  
 {

  
 data = i;

  
 return;

  
 }

  
 tree *p = this;

  
 tree *q = this;

  
 tree *temp;

  
 while(p != NULL)

  
 {

  
 q = p;

  
 if(i < p->data )

  
 p = p->left;

  
 else if(i > p->data)

  
 p = p->right;

  
 else

  
 return;

  
 }

  
 temp = new tree;

  
 temp->data = i;

  
 if(i < q->data)

  
 q->left = temp;

  
 else

  
 q->right = temp;

  
 }

};
void
main()

{
  
 tree t;

  
 int i,n,num;

cout<<endl<<“ENTER
THE NO OF  ELEMENTS

          &nb

sp; 
IN THE BINARY SEARCH TREE: “;
  
 cin >>n;

cout<<“ENTER
THE ELEMENTS:\t”;

  
 for(i=0; i<n; i++)

  
 {

  
     cin>>num;

  
     t.insert(num);

  
 }

cout<<“THE
ELEMENTS IN

          &nb

sp;
THE INORDER TRAVERSAL”;
  
 t.in_order();

cout<<“THE
ELEMENTS IN

          
THE POSTORDER TRAVERSAL\n”;

  
 t.post_order();

cout<<“THE
ELEMENTS IN

         
THE PREORDER TRAVERSAL”;

  
 t.pre_order();

  
 

cout<<“ENTER
THE

          &nb

sp;
ELEMENT TO BE DELETE: “;
  
 cin >>num;

  
 t.deletion(num);

cout<<endl<<“AFTER
DELETION: “;

  
 t.in_order();

}
//program ends
/* output:

ENTER
THE NO OF ELEMENTS IN THE BINARY SEARCH TREE: 5

ENTER
THE ELEMENTS:     1

45
2
67
9

THE
ELEMENTS IN THE INORDER TRAVERSAL

1
2 9 45 67

THE
ELEMENTS IN THE POSTORDER TRAVERSAL

9
2 67 45 1

THE
ELEMENTS IN THE PREORDER TRAVERSAL

1
45 2 9 67 ENTER THE ELEMENT TO BE DELETE: 1

AFTER
DELETION:

2
9 45 67 Press any key to continue

*/

HOME

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: