#include<iostream>
#include<stdlib.h>
#include<queue>
using namespace std;
class node
{
public:
node *left, *right;
int data;
};
class Breadthfs
{
public:
node *insert(node *, int);
void bfs(node *);
};
node *insert(node *root, int data)
// inserts a node in tree
{
if(!root)
{
root=new node;
root->left=NULL;
root->right=NULL;
root->data=data;
return root;
}
queue<node *> q;
q.push(root);
while(!q.empty())
{
node *temp=q.front();
q.pop();
if(temp->left==NULL)
{
temp->left=new node;
temp->left->left=NULL;
temp->left->right=NULL;
temp->left->data=data;
return root;
}
else
{
q.push(temp->left);
}
if(temp->right==NULL)
{
temp->right=new node;
temp->right->left=NULL;
temp->right->right=NULL;
temp->right->data=data;
return root;
}
else
{
q.push(temp->right);
}
}
}
void bfs(node *head)
{
queue<node*> q;
q.push(head);
int qSize;
while (!q.empty())
{
qSize = q.size();
#pragma omp parallel for
//creates parallel threads
for (int i = 0; i < qSize; i++)
{
node* currNode;
#pragma omp critical
{
currNode = q.front();
q.pop();
cout<<"\t"<<currNode->data;
}// prints parent node
#pragma omp critical
{
if(currNode->left)// push parent's left node in queue
q.push(currNode->left);
if(currNode->right)
q.push(currNode->right);
}// push parent's right node in queue
}
}
}
int main(){
node *root=NULL;
int data;
char ans;
do
{
cout<<"\n enter data=>";
cin>>data;
root=insert(root,data);
cout<<"do you want insert one more node?";
cin>>ans;
}while(ans=='y'||ans=='Y');
bfs(root);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0ZGxpYi5oPgojaW5jbHVkZTxxdWV1ZT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgpjbGFzcyBub2RlCnsKICAgcHVibGljOgogICAgCiAgICBub2RlICpsZWZ0LCAqcmlnaHQ7CiAgICBpbnQgZGF0YTsKCn07ICAgIAoKY2xhc3MgQnJlYWR0aGZzCnsKIAogcHVibGljOgogCiBub2RlICppbnNlcnQobm9kZSAqLCBpbnQpOwogdm9pZCBiZnMobm9kZSAqKTsKIAp9OwoKCm5vZGUgKmluc2VydChub2RlICpyb290LCBpbnQgZGF0YSkKLy8gaW5zZXJ0cyBhIG5vZGUgaW4gdHJlZQp7CgogICAgaWYoIXJvb3QpCiAgICB7CiAgIAkgCiAgIAkgcm9vdD1uZXcgbm9kZTsKICAgCSByb290LT5sZWZ0PU5VTEw7CiAgIAkgcm9vdC0+cmlnaHQ9TlVMTDsKICAgCSByb290LT5kYXRhPWRhdGE7CiAgIAkgcmV0dXJuIHJvb3Q7CiAgICB9CgogICAgcXVldWU8bm9kZSAqPiBxOwogICAgcS5wdXNoKHJvb3QpOwogICAgCiAgICB3aGlsZSghcS5lbXB0eSgpKQogICAgewoKICAgCSBub2RlICp0ZW1wPXEuZnJvbnQoKTsKICAgCSBxLnBvcCgpOwogICAgCiAgIAkgaWYodGVtcC0+bGVmdD09TlVMTCkKICAgCSB7CiAgIAkJIAogICAJCSB0ZW1wLT5sZWZ0PW5ldyBub2RlOwogICAJCSB0ZW1wLT5sZWZ0LT5sZWZ0PU5VTEw7CiAgIAkJIHRlbXAtPmxlZnQtPnJpZ2h0PU5VTEw7CiAgIAkJIHRlbXAtPmxlZnQtPmRhdGE9ZGF0YTsgICAgCiAgIAkJIHJldHVybiByb290OwogICAJIH0KICAgCSBlbHNlCiAgIAkgewoKICAgCSBxLnB1c2godGVtcC0+bGVmdCk7CgogICAJIH0KCiAgIAkgaWYodGVtcC0+cmlnaHQ9PU5VTEwpCiAgIAkgewogICAJCSAKICAgCQkgdGVtcC0+cmlnaHQ9bmV3IG5vZGU7CiAgIAkJIHRlbXAtPnJpZ2h0LT5sZWZ0PU5VTEw7CiAgIAkJIHRlbXAtPnJpZ2h0LT5yaWdodD1OVUxMOwogICAJCSB0ZW1wLT5yaWdodC0+ZGF0YT1kYXRhOyAgICAKICAgCQkgcmV0dXJuIHJvb3Q7CiAgIAkgfQogICAJIGVsc2UKICAgCSB7CgogICAJIHEucHVzaCh0ZW1wLT5yaWdodCk7CgogICAJIH0KCiAgICB9CiAgICAKfQoKCnZvaWQgYmZzKG5vZGUgKmhlYWQpCnsKCiAgIAkgcXVldWU8bm9kZSo+IHE7CiAgIAkgcS5wdXNoKGhlYWQpOwogICAJIAogICAJIGludCBxU2l6ZTsKICAgCSAKICAgCSB3aGlsZSAoIXEuZW1wdHkoKSkKICAgCSB7CiAgIAkJIHFTaXplID0gcS5zaXplKCk7CiAgIAkJICNwcmFnbWEgb21wIHBhcmFsbGVsIGZvcgogICAgICAgICAgICAJLy9jcmVhdGVzIHBhcmFsbGVsIHRocmVhZHMKICAgCQkgZm9yIChpbnQgaSA9IDA7IGkgPCBxU2l6ZTsgaSsrKQogICAJCSB7CiAgIAkJCSBub2RlKiBjdXJyTm9kZTsKICAgCQkJICNwcmFnbWEgb21wIGNyaXRpY2FsCiAgIAkJCSB7CiAgIAkJCSAgIGN1cnJOb2RlID0gcS5mcm9udCgpOwogICAJCQkgICBxLnBvcCgpOwogICAJCQkgICBjb3V0PDwiXHQiPDxjdXJyTm9kZS0+ZGF0YTsKICAgCQkJICAgCiAgIAkJCSB9Ly8gcHJpbnRzIHBhcmVudCBub2RlCiAgIAkJCSAjcHJhZ21hIG9tcCBjcml0aWNhbAogICAJCQkgewogICAJCQkgaWYoY3Vyck5vZGUtPmxlZnQpLy8gcHVzaCBwYXJlbnQncyBsZWZ0IG5vZGUgaW4gcXVldWUKICAgCQkJCSBxLnB1c2goY3Vyck5vZGUtPmxlZnQpOwogICAJCQkgaWYoY3Vyck5vZGUtPnJpZ2h0KQogICAJCQkJIHEucHVzaChjdXJyTm9kZS0+cmlnaHQpOwogICAJCQkgfS8vIHB1c2ggcGFyZW50J3MgcmlnaHQgbm9kZSBpbiBxdWV1ZSAgIAkgCgogICAJCSB9CiAgIAkgfQoKfQoKaW50IG1haW4oKXsKCiAgICBub2RlICpyb290PU5VTEw7CiAgICBpbnQgZGF0YTsKICAgIGNoYXIgYW5zOwogICAgCiAgICBkbwogICAgewogICAJIGNvdXQ8PCJcbiBlbnRlciBkYXRhPT4iOwogICAJIGNpbj4+ZGF0YTsKICAgCSAKICAgCSByb290PWluc2VydChyb290LGRhdGEpOwogICAgCiAgIAkgY291dDw8ImRvIHlvdSB3YW50IGluc2VydCBvbmUgbW9yZSBub2RlPyI7CiAgIAkgY2luPj5hbnM7CiAgICAKICAgIH13aGlsZShhbnM9PSd5J3x8YW5zPT0nWScpOwogICAgCiAgICBiZnMocm9vdCk7CiAgICAKICAgIHJldHVybiAwOwp9