C,C++/JAVA/BASH/ASM ARENA

वह प्रदीप जो दीख रहा है झिलमिल दूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है चिन्गारी बन गयी लहू की बून्द गिरी जो पग से चमक रहे पीछे मुड देखो चरण-चिनह जगमग से बाकी होश तभी तक, जब तक जलता तूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है अपनी हड्डी की मशाल से हृदय चीरते तम का, सारी रात चले तुम दुख झेलते कुलिश का। एक खेय है शेष, किसी विध पार उसे कर जाओ; वह देखो, उस पार चमकता है मन्दिर प्रियतम का। आकर इतना पास फिरे, वह सच्चा शूर नहीं है; थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है। दिशा दीप्त हो उठी प्राप्त कर पुण्य-प्रकाश तुम्हारा, लिखा जा चुका अनल-अक्षरों में इतिहास तुम्हारा। जिस मिट्टी ने लहू पिया, वह फूल खिलाएगी ही, अम्बर पर घन बन छाएगा ही उच्छ्वास तुम्हारा। और अधिक ले जाँच, देवता इतन क्रूर नहीं है। थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है।

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

Filed under: Uncategorized — whoami @ 18:53
//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;
}

Advertisements