#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>
using namespace std;
struct Node
{
    int v;
    Node *leftChild,*rightChild;
    Node():leftChild(NULL),rightChild(NULL){}
    Node(int vv):leftChild(NULL),rightChild(NULL)
    {
        v=vv;
    }
};

void print(int v)
{
    cout<<v<<"   ";
}
void PreOrderTraverse(Node *n, void (* visit)(int))
{
    assert(n!=NULL&&visit!=NULL);
    (*visit)(n->v);
    if(n->leftChild!=NULL) PreOrderTraverse(n->leftChild,visit);
    if(n->rightChild!=NULL) PreOrderTraverse(n->rightChild,visit);
}

void InOrderTraverse(Node *n, void (* visit)(int))
{
    assert(n!=NULL&&visit!=NULL);
    if(n->leftChild!=NULL) InOrderTraverse(n->leftChild,visit);
    (*visit)(n->v);
    if(n->rightChild!=NULL) InOrderTraverse(n->rightChild,visit);
}

void PostOrderTraverse(Node *n, void (* visit)(int))
{
    assert(n!=NULL&&visit!=NULL);
    if(n->leftChild!=NULL) PostOrderTraverse(n->leftChild,visit);
    if(n->rightChild!=NULL) PostOrderTraverse(n->rightChild,visit);
    (*visit)(n->v);
}
//非遞歸版本，將遞歸改成非遞歸一般都要利用一個棧
//每次訪問一個結點后，在向左子樹遍歷下去之前，利用這個棧記錄該結點的右子女（如果有的話）結點的地址，
//以便在左子樹退回時可以直接從棧頂取得右子樹的根結點，繼續右子樹的遍歷
void PreOrder(Node *n, void (* visit)(int))
{
    stack<Node*> sta;
    sta.push(n);
    while(!sta.empty())
    {
        Node * t=sta.top();
        sta.pop();
        assert(t!=NULL);
        (*visit)(t->v);
        if(t->rightChild!=NULL) sta.push(t->rightChild);
        if(t->leftChild!=NULL) sta.push(t->leftChild);
    }
}

//非遞歸中序遍歷
void InOrder(Node * n , void (* visit) (int))
{
    stack<Node *> sta;
    sta.push(n);
    Node * p= n;
    while(!sta.empty()&&p!=NULL)
    {
        p=sta.top();
        while(p!=NULL&&!sta.empty())
        {
            sta.push(p->leftChild);
            p=p->leftChild;
        }
        sta.pop();//彈出空指針
        if(!sta.empty())
        {
            p=sta.top();
            sta.pop();
            (*visit)(p->v);
            sta.push(p->rightChild);
        }
    }
}

//非遞歸后續遍歷

struct StkNode
{
    Node * ptr;
    bool tag;//false=left and true=right
    StkNode():ptr(NULL),tag(false)
    {}
};
void PostOrder(Node * n ,void (*visit) (int))
{
    stack<StkNode> sta;
    StkNode w;
    Node * p = n;
    do {
        while(p!=NULL)
        {
            w.ptr=p;
            w.tag=false;
            sta.push(w);
            p=p->leftChild;
        }
        bool flag=true;
        while(flag&&!sta.empty())
        {
            w=sta.top();
            sta.pop();
            p=w.ptr;
            if(!w.tag)//left,如果從左子樹返回，則開始遍歷右子樹
            {
                w.tag=true;//標記右子樹
                sta.push(w);
                flag=false;
                p=p->rightChild;
            }
            else
            {
                (*visit)(p->v);
            }
        }
    } while(!sta.empty());
}

//層序遍歷，利用隊列
void LevelOrderTraverse(Node * n , void (* visit )(int))
{
    assert(n!=NULL&&visit!=NULL);
    queue<Node * > que;
    que.push(n);
    while(!que.empty())
    {
        Node * t=que.front();
        (*visit)(t->v);
        que.pop();
        if(t->leftChild!=NULL) que.push(t->leftChild);
        if(t->rightChild!=NULL) que.push(t->rightChild);
    }
}

int main()
{
    Node * head= new Node(0);
    Node * node1= new Node(1);
    Node * node2= new Node(2);
    Node * node3= new Node(3);
    Node * node4= new Node(4);
    Node * node5= new Node(5);
    Node * node6= new Node(6);

    head->leftChild=node1;
    head->rightChild=node2;   
    node1->leftChild=node3;
    node1->rightChild=node4;
    node2->rightChild=node5;
    node4->leftChild=node6;

   
/*    LevelOrderTraverse(head,print);
    cout<<endl;
    PreOrderTraverse(head,print);
    cout<<endl;*/
    InOrder(head,print);
    cout<<endl;
    InOrderTraverse(head,print);
    cout<<endl;

    PostOrder(head,print);
    cout<<endl;
    PostOrderTraverse(head,print);
    cout<<endl;
    return 0;
}