Advertisement
karbaev

STL DFS no recursion

Nov 4th, 2014
39
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <stack>
  2. struct BTNode
  3. {
  4.  
  5.     BTNode(int d)
  6.     {
  7.         data = d;
  8.     }
  9.  
  10.     int data;
  11.     BTNode* right;
  12.     BTNode* left;
  13. };
  14.  
  15.     void DFS(BTNode* root)
  16.     {
  17.         BTNode* tmp = root;
  18.         std::stack<BTNode*> stck;
  19.         stck.push(tmp);
  20.  
  21.         //Until the stack is not empty, it means there are nodes to traverse
  22.         while(stck.empty() == false)
  23.         {
  24.             while (tmp->left != 0)
  25.             {
  26.                 tmp = tmp->left;
  27.                 stck.push(tmp);
  28.             }
  29.             while(true)
  30.             {
  31.                 tmp = stck.top();
  32.                 stck.pop();
  33.                 std::cout << tmp->data;
  34.                 if(tmp->right != 0)
  35.                 {
  36.                     tmp = tmp->right;
  37.                     stck.push(tmp);
  38.                     break;
  39.                 }
  40.             }
  41.         }
  42.  
  43.  void CreateTreeExample(BTNode* root)
  44.     {
  45.         BTNode* b1= new BTNode(1);
  46.         BTNode* b2= new BTNode(2);
  47.         BTNode* b3= new BTNode(3);
  48.         BTNode* b4= new BTNode(4);
  49.         BTNode* b5= new BTNode(5);
  50.         BTNode* b6= new BTNode(6);
  51.         BTNode* b7= new BTNode(7);
  52.         BTNode* b8= new BTNode(8);
  53.         BTNode* b9= new BTNode(9);
  54.  
  55.         b2->left = b1;
  56.         b2->right = b4;
  57.         b6->left = b2;
  58.         b4->left = b3;
  59.         b4->right = b5;
  60.         b7->left = b6;
  61.         b7->right = b8;
  62.         b8->right = b9;
  63.         root = b7;
  64.     }
  65.  
  66. //To test the algorithm, make a simple binary tree by calling the method:
  67. //             7
  68. //            /  \
  69. //           6    8
  70. //          /      \  
  71. //        2         9
  72. //       /  \
  73. //      1    4
  74. //          /  \
  75. //         3    5
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement