fork download
copy 
  1. //print paths in a tree without recursion
  2. #include<iostream>
  3. #include<vector>
  4. #include<stack>
  5. using namespace std;
  6. struct node                         
  7. {
  8.        int data;
  9.        vector<node*>children;
  10. };
  11. int visited[100];
  12. stack <node*> st;
  13. int count=0;
  14. int n;      
  15. void printpath(node * root)                               //dfs starts here
  16. {
  17.      st.push(root);
  18.      while(visited[0]==0)
  19.      {
  20.          node* v=st.top();
  21.          if(visited[v->data]!=0)                 // leaf nodes or nodes whose all children 
  22.             st.pop();                            // are visited are only popped from the stack
  23.          if(visited[v->data])
  24.             continue;
  25.          cout<<v->data<<" ";
  26.          int flag=0;
  27.          for(int i=0;i<v->children.size();i++)      /*check if any of the children have not been visited*/
  28.          {
  29.                  if(visited[v->children[i]->data]==0)
  30.                  {
  31.                       flag=flag||1;
  32.                       st.push(v->children[i]);
  33.                  }
  34.                  else
  35.                        flag=flag||0;
  36.          }
  37.  
  38.          /*if this is the leaf node then mark it visited and
  39.          along with other intermediate nodes whose all the   
  40.          children have been visited.this is continued till we
  41.          reach root which has the value 0 in its data*/
  42.  
  43.          if(flag==0)
  44.          {                                      
  45.                  visited[v->data]=1;                       
  46.                   while(v->data!=0)                         
  47.                   {
  48.                      v=st.top();
  49.                      int flag=0;
  50.                      for(int i=0;i<v->children.size();i++)
  51.                      {
  52.                         if(visited[v->children[i]->data]==0)
  53.                           flag=flag||1;
  54.                        else
  55.                          flag=flag||0;
  56.                      }
  57.                         if(flag==0 && v->children.size()!=0)
  58.                           visited[v->data]=1;
  59.                         if(v->data!=0)
  60.                           st.pop();
  61.                   }
  62.                   cout<<endl;
  63.          }
  64.      }
  65. }
  66. main()
  67. {
  68.    n=8;
  69.    for(int i=0;i<9;i++)
  70.        visited[i]=0;
  71.    node*root = new node();                         //tree construction
  72.    root->data=0;
  73.    node* d = new node();
  74.    d->data=1;
  75.    node* m = new node();
  76.    m->data=2;
  77.    node* n = new node();
  78.    n->data=3;
  79.    root->children.push_back(d);
  80.    root->children.push_back(m);
  81.    root->children.push_back(n);
  82.    node* x = new node();
  83.    x->data=4;
  84.    node* y = new node();
  85.    y->data=5;
  86.    node* z = new node();
  87.    z->data=6;
  88.    d->children.push_back(x);
  89.    d->children.push_back(y);
  90.    d->children.push_back(z);
  91.    node* o = new node();
  92.    o->data=7;
  93.    node* p = new node();
  94.    p->data=8;
  95.    n->children.push_back(o);
  96.    n->children.push_back(p);
  97.    printpath(root);
  98. }
  99.  
  100.  
Success #stdin #stdout 0.01s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 3 8 
0 3 7 
0 2 
0 1 6 
0 1 5 
0 1 4
https://ideone.com/a6xHq
language:
C++ (gcc 8.3)
created:
11 years 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!