#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<algorithm>
#include<numeric>
using namespace std;

class node{
public:
    int val;
    node* left;
    node* right;
    node():val(0),left(NULL),right(NULL){}
};

node* createTree()
{
    node* head = new node[14];
    for(int i = 0;i<10;i++)
    {
        head[i].val = i;
        if(2*i+1 < 10)
        head[i].left = head + 2*i + 1;
        if(2*i+2 < 10)
        head[i].right = head + 2*i + 2;
    }
    return head;
}

void searchfirst(node* head) ///先序遍历，其实和中序差不多，还好些
{
    stack<node*> s;
    node* r = head;
    s.push(r);
    while(!s.empty())
    {
     while(NULL != r)
     {
         cout<<r->val<<" ";
         r = r->left;
         if(NULL != r) s.push(r);
     }

     r = s.top();
     s.pop();
     r = r->right;
     if(NULL != r) s.push(r);
    
    }
}

void searchmiddle(node* head)///先序遍历，其实和先序差不多，还好些
{
    stack<node*> s;
    node* r = head;
    s.push(r);
    while(!s.empty())
    {
     while(NULL != r)
     {
         r = r->left;
         if(NULL != r) s.push(r);
     }

     r = s.top();
     cout<<r->val<<" ";
     s.pop();
     r = r->right;
     if(NULL != r) s.push(r);
    
    }
}

void searchlast(node* head)
{
    stack<node* > s;
    stack<int> flags;
    int flag;
    node* p = head;
    s.push(p);
    flags.push(1);
    while(!s.empty())
    {
        while(NULL != p && NULL != p->left)///先比与前者，这个到最第的做节点就不再push了
        {
            p = p->left;
            s.push(p);
            flags.push(1);
        }

        flag = flags.top();
        flags.pop();
        p = s.top();

        if((NULL != p->right) && flag == 1)
        {
            flags.push(2);
            p = p->right;
            s.push(p);
            flags.push(1);
        }else{
            s.pop();
            cout<<p->val<<" ";
            p = NULL;
        }
    }
}

int main()
{
 node* t = createTree();
 searchfirst(t); cout<<endl;
 searchmiddle(t); cout<<endl;
 searchlast(t); cout<<endl;
}