#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>

using namespace std;

typedef struct node
{
    node():data(‘ ‘), lchild(NULL), rchild(NULL) {}
    char data;
    struct node* lchild;
    struct node* rchild;
} BinTreeNode, *BinTree;

void Preorder(BinTree t)
{
    if(t)
    {
        putchar(t->data);
        Preorder(t->lchild);
        Preorder(t->rchild);
    }
}

void Non_Preorder(BinTree t)
{
    BinTree T=t;
    stack<BinTree> S;
    while(T || !S.empty())
    {
        while(T)
        {
            putchar(T->data);
            S.push(T);
            T=T->lchild;
        }
        if(!S.empty())
        {
            T=S.top();
            S.pop();
            T=T->rchild;
        }
    }
}

void Inorder(BinTree t)
{
    if(t)
    {
        Inorder(t->lchild);
        putchar(t->data);
        Inorder(t->rchild);
    }
}

void Non_Inorder(BinTree t)
{
    BinTree T=t;
    stack<BinTree> S;
    while(T || !S.empty())
    {
        while(T)
        {
            S.push(T);
            T=T->lchild;
        }
        if(!S.empty())
        {
            T=S.top();
            putchar(T->data);
            S.pop();
            T=T->rchild;
        }
    }
}

void Posorder(BinTree t)
{
    if(t)
    {
        Posorder(t->lchild);
        Posorder(t->rchild);
        putchar(t->data);
    }
}
/**要保证根结点在左孩子和右孩子访问之后才能访问，
因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，
则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，
则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候
，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。**/
void Non_Posorder(BinTree t)
{
    BinTree T=t, pre=NULL;
    stack<BinTree> S;

    S.push(T);
    while(!S.empty())
    {
        T=S.top();
        if((T->lchild==NULL&&T->rchild==NULL) || (pre!=NULL&&(pre==T->lchild || pre==T->rchild)))
        {
            putchar(T->data);
            S.pop();
            pre=T;
        }
        else
        {
            if(T->rchild!=NULL)
                S.push(T->rchild);
            if(T->lchild!=NULL)
                S.push(T->lchild);
        }
    }
}

void Leveorder(BinTree t)
{
    BinTree T=t;
    if(!T)return ;
    queue<BinTree> Q;
    Q.push(T);

    while(!Q.empty())
    {
        T=Q.front();
        Q.pop();
        putchar(T->data);
        if(T->lchild)
            Q.push(T->lchild);
        if(T->rchild)
            Q.push(T->rchild);
    }
}
void CreatBinTree(BinTree &T)
{
    char ch;
    scanf("%c", &ch);
    if(ch==‘#‘)
        T=NULL;
    else
    {
        T=new BinTreeNode;
        T->data=http://www.mamicode.com/ch;
        CreatBinTree(T->lchild);
        CreatBinTree(T->rchild);
    }
}

int main()
{
    BinTree T;
    CreatBinTree(T);

    printf("前序递归遍历二叉树：\n");
    Preorder(T);
    puts("");
    printf("前序非递归遍历二叉树：\n");
    Non_Preorder(T);
    puts("");

    printf("中序递归遍历二叉树：\n");
    Inorder(T);
    puts("");
    printf("中序非递归遍历二叉树：\n");
    Non_Inorder(T);
    puts("");

    printf("后序递归遍历二叉树：\n");
    Posorder(T);
    puts("");
    printf("后序非递归遍历二叉树：\n");
    Non_Posorder(T);
    puts("");

    printf("层次遍历二叉树：\n");
    Leveorder(T);
    puts("");

    return 0;
}
/*
ab#d##c#e##
abd##e##cf##g##
*/