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();
}
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();
}
Post a Comment