BFS in binary tree

I'm trying to write the codes for breadth-first search in binary tree. I've stored all the data in a queue, but I can't figure out how to travel to all nodes and consume all their children.

Here's my code in C:

void breadthFirstSearch (btree *bt, queue **q) {
   if (bt != NULL) {

      //store the data to queue if there is

      if (bt->left != NULL) enqueue (q, bt->left->data);
      if (bt->right != NULL) enqueue (q, bt->right->data);

      //recursive

      if (bt->left != NULL) bread开发者_StackOverflowthFirstSearch (bt->left, q);
      if (bt->right != NULL) breadthFirstSearch (bt->right, q);
   }
}

I've already enqueued the root data, but it's still not working. Can anyone point out my mistake?

---

A BFS can be easily written without recursion. Just use a queue to order your expansions:

void BFS(btree *start)
{
    std::deque<btree *> q;
    q.push_back(start);
    while (q.size() != 0)
    {
        btree *next = q.front();
        // you may want to print the current node here or do other processing
        q.pop_front();
        if (next->left)
            q.push_back(next->left);
        if (next->right)
            q.push_back(next->right);
    }
}

The key is that you don't need to traverse the tree recursively; you just let your data structure handle the order in which you visit nodes.

Note that I'm using the C++ deque here, but anything that lets you put items on the back and get them from the front will work fine.

---

void bfs_bintree (btree_t *head)
{
  queue_t *q;
  btree_t *temp;

  q = queue_allocate ();
  queue_insert (q, head);

  while (!queue_is_empty (q))
  {
    temp = queue_remove (q);

    if (temp->left)
      queue_insert (temp->left);

    if (temp->right)
      queue_insert (temp->right);
  }
  queue_free (q);
  return;
}

First the head node is inserted into the queue. The loop will iterate while the queue is not empty. Starting from the head node, in each iteration one node is removed and the non-null childs are inserted in the queue. In each iteration one node gets out and its non-null childs gets pushed. In the next iteration the next oldest discovered vertex, which is now at the front of the queue , is taken out (in the order they were discovered) and then they are processed to check their child.

                                A
                               / \
                              /   \
                             B     C
                            / \     \
                           /   \     \
                          D     E     F
                         / \         / \
                        /   \       /   \
                       G     H     I     J


iteration  Vertex Selection Discovery Queue State
 initial                    :  A
    1            A          :  B C     {A is removed and its children inserted}
    2            B          :  C D E   {B is removed and its only child inserted}
    3            C          :  D E F   {C is removed and its children inserted}
    4            D          :  E F G H {D is removed and its children inserted}
    5            E          :  F G H   {E is removed and has not children}
    6            F          :  G H I J {F is removed and its children inserted}
    7            G          :  H I J   {G is removed has no children}
    8            H          :  I J     {H is removed has no children}
    9            I          :  J       {I is removed has no children}
    10           J          :  (empty) {J is removed has no children}

Above the iteration stops when we get that there is no more discovered vertex which are waiting to be selected, in the queue, so all the vertices which were discovered in the binary tree (graph connected component) is selected.

I your code first you pass enqueue the nodes in queue and then traverse these childs again recursively, which creates a DFS pattern. If you have to do recursion, you need to check for if the queue is empty as the base condition. Also have a check how you are passing the queue, i think it may be incorrect. I would suggest an iterative solution.

---

You are not doing a breadth first traversal here. Instead you are enqueuing the left and right element inside the queue and moving to the left subtree. You are exhausting the left subtree first and then moving on to the right subtree.

Write a procedure to enqueue the node instead.

void breadthFirstSearch (btree *bt, queue **q) {
 btree *tmpNode;
 enqueue(q,bt); //Assuming your root node has data

 while (!isempty(q)) //Assume isempty returns false when queue is not empty
 {
  tmpNode = dequeue(q);
  //Do whatever you want to do with tmpNode->data
  enqueue(tmpNode->left);
  enqueue(tmpNode->right);
  /* If this is a acyclic graph(tree) then this procedure should do, else you have to mark the nodes you have visited in-order not to end in a cycle */
 }

}

int main()
{
breadthFirstSearch(bt,q)
return 0
}

---

This is a Static code for BFS to clear the concept of BFS. In this code I have used 2 array one in node array and another one is edge array. And by recursion I have printed all the Neighbour of each Node for a directed graph.

 Graph is:  A-->D-->E
            |\  |   | 
            v \ v   v     
            B-->C <-|
           
 There is a Edge from A to C    

This is the code:

enter code here
 #include<stdio.h>
 int NodeArr[5][3]={{'A',1,0},
               {'B',2,3},
               {'C',3,-1},
               {'D',4,4},
               {'E',-1,6}};

  int edgeArr[7][2]={
                 //For A Node
                {'B',1},
                {'C',2},
                {'D',-1},
                 //For B Node
                {'C',-1},
                  //As C Node has no directed neighbour 
                 //For D Node
                {'C',5},
                {'E',-1},
                 //For E Node
                {'C',-1},};

  void printcharacter(int edge_index){
    printf("%c ",edgeArr[edge_index][0]);
     if(edgeArr[edge_index][1]==-1)
        return;

    printcharacter(edgeArr[edge_index][1]);

  }

int main(){

 printf("Neighbour of All Nodes for Directed Graph");
for(int i=0;i<5;i++){
   if(NodeArr[i][2]!=-1){
    int edge_index=NodeArr[i][2];
    printf("Neighbour of %c are ",NodeArr[i][0]);
    printcharacter(edge_index);
    printf("\n");
       }
 
     }
 }