fork download
copy 
  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<queue>
  4. using namespace std;
  5.  
  6.  
  7. class node
  8. {
  9.    public:
  10.  
  11.     node *left, *right;
  12.     int data;
  13.  
  14. };    
  15.  
  16. class Breadthfs
  17. {
  18.  
  19.  public:
  20.  
  21.  node *insert(node *, int);
  22.  void bfs(node *);
  23.  
  24. };
  25.  
  26.  
  27. node *insert(node *root, int data)
  28. // inserts a node in tree
  29. {
  30.  
  31.     if(!root)
  32.     {
  33.  
  34.    	 root=new node;
  35.    	 root->left=NULL;
  36.    	 root->right=NULL;
  37.    	 root->data=data;
  38.    	 return root;
  39.     }
  40.  
  41.     queue<node *> q;
  42.     q.push(root);
  43.  
  44.     while(!q.empty())
  45.     {
  46.  
  47.    	 node *temp=q.front();
  48.    	 q.pop();
  49.  
  50.    	 if(temp->left==NULL)
  51.    	 {
  52.  
  53.    		 temp->left=new node;
  54.    		 temp->left->left=NULL;
  55.    		 temp->left->right=NULL;
  56.    		 temp->left->data=data;    
  57.    		 return root;
  58.    	 }
  59.    	 else
  60.    	 {
  61.  
  62.    	 q.push(temp->left);
  63.  
  64.    	 }
  65.  
  66.    	 if(temp->right==NULL)
  67.    	 {
  68.  
  69.    		 temp->right=new node;
  70.    		 temp->right->left=NULL;
  71.    		 temp->right->right=NULL;
  72.    		 temp->right->data=data;    
  73.    		 return root;
  74.    	 }
  75.    	 else
  76.    	 {
  77.  
  78.    	 q.push(temp->right);
  79.  
  80.    	 }
  81.  
  82.     }
  83.  
  84. }
  85.  
  86.  
  87. void bfs(node *head)
  88. {
  89.  
  90.    	 queue<node*> q;
  91.    	 q.push(head);
  92.  
  93.    	 int qSize;
  94.  
  95.    	 while (!q.empty())
  96.    	 {
  97.    		 qSize = q.size();
  98.    		 #pragma omp parallel for
  99.             	//creates parallel threads
  100.    		 for (int i = 0; i < qSize; i++)
  101.    		 {
  102.    			 node* currNode;
  103.    			 #pragma omp critical
  104.    			 {
  105.    			   currNode = q.front();
  106.    			   q.pop();
  107.    			   cout<<"\t"<<currNode->data;
  108.  
  109.    			 }// prints parent node
  110.    			 #pragma omp critical
  111.    			 {
  112.    			 if(currNode->left)// push parent's left node in queue
  113.    				 q.push(currNode->left);
  114.    			 if(currNode->right)
  115.    				 q.push(currNode->right);
  116.    			 }// push parent's right node in queue   	 
  117.  
  118.    		 }
  119.    	 }
  120.  
  121. }
  122.  
  123. int main(){
  124.  
  125.     node *root=NULL;
  126.     int data;
  127.     char ans;
  128.  
  129.     do
  130.     {
  131.    	 cout<<"\n enter data=>";
  132.    	 cin>>data;
  133.  
  134.    	 root=insert(root,data);
  135.  
  136.    	 cout<<"do you want insert one more node?";
  137.    	 cin>>ans;
  138.  
  139.     }while(ans=='y'||ans=='Y');
  140.  
  141.     bfs(root);
  142.  
  143.     return 0;
  144. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 enter data=>do you want insert one more node?	32765
https://ideone.com/yrLUT5
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!