Level Order Traversal(BFT) of a Binary Tree May 25, 2011

//level order traversal of a tree.
//here tree that is created is BST although it will work for every binary tree
#include<stdio.h>
#include<malloc.h>
#include<queue>
using namespace std;

struct node{
  int item;
  struct node *left;
  struct node *right;
};

struct node *root=(struct node *)malloc(sizeof(struct node));


void insert(int data)
{
  struct node *tmp=(struct node *)malloc(sizeof(struct node));
  struct node *tmp2;
  struct node *save=(struct node *)malloc(sizeof(struct node));

  tmp->item=data;
  tmp->right=NULL;
  tmp->left=NULL;

  tmp2=root;
  while(1)
  {
    if(tmp2==NULL) break; 
    if(data>tmp2->item)
    {
       save=tmp2;
       tmp2=tmp2->right;
    }
    else if(data<tmp2->item)
    {
       save=tmp2;
       tmp2=tmp2->left;
    }
  }
  if(save->item<data)
  {

     save->right=tmp;
  }
  else if(save->item>data)
  {
     save->left=tmp;
  }

}     

//////////////////level order traversal begins//////////////////////
void bfs()
{
  queue<struct node *>q1;
  queue<struct node *>q2;
  struct node *tmp;
  struct node *tmp2;
  q1.push(root);//root
  while(1)
  {
     
     while(!q1.empty())
     {
         tmp2=q1.front();
         if(tmp2->left!=NULL)
         {
           q2.push(tmp2->left); 
         }
         if(tmp2->right!=NULL)
         {
            q2.push(tmp2->right);
         }
         printf("%d ",tmp2->item); 
         q1.pop(); 
      }
      if(q2.empty()) break;
      printf("\n");
      
      while(!q2.empty())
      {
        q1.push(q2.front());
        q2.pop();
      }
   } 

}

//////////////////level order traversal end//////////////////////



int main()
{
  int data;
  
  //create binary search tree
  printf("enter the root element");
  scanf("%d",&data);
  root->item=data;
  root->left=NULL;
  root->right=NULL;
 
  while(1)
  {
    printf("enter -1 to stop");
    scanf("%d",&data);
    if(data==-1) break;
    insert(data);
  }

  bfs();//level order traversal

return 0;
}