SabirSazzad

DFS & BFS travel using Link List

Feb 26th, 2017
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4.  
  5. struct Node
  6. {
  7.     int data;
  8.     Node *left;
  9.     Node *right;
  10. };
  11. Node *getnewnode(int data)
  12. {
  13.     Node *newnode = new Node();
  14.     newnode->data = data;
  15.     newnode->left = NULL;
  16.     newnode->right = NULL;
  17.  
  18.     return newnode;
  19. }
  20. Node *Insert(Node *root, int data)
  21. {
  22.     if(root==NULL)
  23.     {
  24.         root = getnewnode(data);
  25.     }
  26.     else if(data <= root->data)
  27.     {
  28.         root->left = Insert(root->left,data);
  29.     }
  30.     else
  31.     {
  32.         root->right = Insert(root->right,data);
  33.     }
  34.     return root;
  35. }
  36. void BFS_traversal(Node *node)
  37. {
  38.     queue<Node *> BFS;
  39.     BFS.push(node);
  40.     while(!BFS.empty())
  41.     {
  42.         node = BFS.front();
  43.         BFS.pop();
  44.         cout << node -> data << " ";
  45.         if(node->left != NULL)
  46.         {
  47.             BFS.push(node->left);
  48.         }
  49.         if(node->right != NULL)
  50.         {
  51.             BFS.push(node->right);
  52.         }
  53.     }
  54. }
  55. void DFS_traversal(Node *node)
  56. {
  57.     if(node==NULL)
  58.     {
  59.         return;
  60.     }
  61.     cout << node-> data << " ";
  62.     DFS_traversal(node->left);
  63.     DFS_traversal(node->right);
  64. }
  65.  
  66. int main()
  67. {
  68.     Node *root = NULL;
  69.     int limit,i,data,src;
  70.     cout<< "Input number of data: ";
  71.     cin >> limit;
  72.     for(i=1;i<=limit;i++)
  73.     {
  74.         cout << "Input data: ";
  75.         cin >> data;
  76.         root = Insert(root,data);
  77.     }
  78.     cout << "\nBreath First Traversal is....." <<endl;
  79.     BFS_traversal(root);
  80.     cout << "\nDepth First Traversal is....." <<endl;
  81.     DFS_traversal(root);
  82.  
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment