Monday 16 April 2012

Breadth First Search(BFS) of a Binary tree

/*
WORKING OF THE BFS FUNCTION CODE :


The root node is pushed into the queue so that the loop starts its iteration from the root. After that everytime the data is compared to check whether it is present. If not, the left and right nodes of the current node (same level) are pushed into the queue. This was all the nodes of the same level are pushed into the queue first and are popped out of the queue first.

*/

#include <iostream>
#include <queue>
using namespace std;
struct Node
{
     int m_data;
     Node * m_left;
     Node * m_right;
     Node(int data,Node * left,Node * right) : m_data(data),m_left(left),m_right(right)  {  }
     Node(int data) : m_data(data),m_left(NULL),m_right(NULL) { }
     Node() : m_data(0),m_left(NULL),m_right(NULL) {  }   //  m_data initialized to zero
};

bool BFS(Node * root,int data)
{
     queue<Node *> q;
     Node * temp;
     q.push(root);   // Push the parent in the queue, so that the loop starts from the parent.
     while(q.empty())
     {
          temp = q.front();
          q.pop();
          if(temp->m_data == data)
               return true;
          if(temp->left)
               q.push(temp->left);
          if(temp->right)
               q.push(temp->right);
          }
     return false;
}

int main()
{
     Node * root = new Node(3);
     root->left = new Node(4);
     root->right = new Node(5);
     root->left->left = new Node(2);
     if(BFS(root,2))
          cout<<"Node with data 2 found";
     else
          cout<<"Node with data 2 not found"
     return 0;
}

No comments: