BFS (breadth first search) in BST (binary search tree)

BFS code in red color highlighted.  
1) Insertion in BST
2) Normal Searching in BST.
3) BFS in BST


#include<iostream.h>
#include<conio.h>
class Node{
private:
 int data;
 Node* right;
 Node* left;
public:
 Node(){
  root=NULL;
  right=left=NULL;
 }Node *root;

 void insert(int data){
  Node* newnode = new Node();
  newnode->data = data;
   if (root == NULL){
   root=newnode;
   return;
  }
  Node *p,*q;
  p=q=root;
  while (q!=NULL){
   p=q;
   if (newnode->data> q->data)
    q = q->right;
   else q = q->left;
  }
  if (newnode->data> p->data)
   p->right = newnode;
  else p->left = newnode;
 }


 void inorder(Node *root){
  if (root == NULL) return;
  else {
   cout << root->data <<" ";
   inorder(root->left);
  // cout << root->data <<"  ";
   inorder(root->right);
   }
 }



void search(Node *root,int v)
{
int flag=0;
Node *q=root;
while(v != q->data)
{
if(v < q->data && q->left != NULL)
{
flag=2;
q=q->left;
}
else if( v > q->data && q-right !=NULL)
{
flag=2;
q=q->right;
}else{
flag=1;
cout<<"\n Node value not found . "<<endl;
break;
}
}
if(flag == 0 || flag ==2){
cout<<"\nNode is  found= "<<q->data<<endl;
 }
}

void BFS(Node* root,int value){
 Node **arry=NULL;
 int i=0,j=0;
 arry[i]=root;
 if(root->data == value){
 cout<<root->data<<" ";
 }
 else{           i++;
 while(arry[j]->data != value){
 Node *a=arry[j];
 if(a->left != NULL)
 {
  arry[i]=a->left;i++;
if( a->left->data==value)
{break;}
 }
 if(a->right !=NULL)
{
 arry[i]=a->right;i++;
if(a->right->data==value)
{break;}
 }
   j++;}//end of loop
for(int x=0;x<=(sizeof(arry)/sizeof(*arry));x++){
cout<<arry[x]->data<<" ";
    }//end of for
  }//end of else
}//end of function

};

void main()
{
int c,A[]={8,4,5,1,12,11,13,3,14};
 Node b;
 clrscr();
 for(int i=0;i<=8;i++){
 b.insert(A[i]);
 }

 b.inorder(b.root);
 getch();

cout<<"\n\nEnter Value For Search ";cin>>c;
b.BFS(b.root,c);
getch();

// b.search(b.root,c);
//getch();

// cout<<"\n\nInsert a New Value ";cin>>c;
// b.insert(c);
// b.inorder(b.root);
// getch();

}


No comments

Powered by Blogger.