#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiNode{//二叉樹 
    ElemType data;
    struct BiNode *lchild,*rchlid;
}BiNode,*BiTree;

typedef struct NodeStack{//鏈棧 
    BiTree data;
    struct NodeStack *next;
}NodeStack;

typedef struct Node{//隊列結點
    BiTree data;
    struct Node *next;
}Node;

typedef struct Queue{//鏈式隊列 
    struct Node *front,*rear;
}Queue;

BiTree Create_BiTree(BiTree T);//前序遍歷建立二叉樹
void PreOrder(BiTree T); //前序遍歷
void InOrder(BiTree T);//中序遍歷
void PostOrder(BiTree T); //後序遍歷
void visit(BiTree T);//訪問節點
void InOrder2(BiTree T);//中序遍歷非遞歸算法 
void PreOrder2(BiTree T);//先序遍歷非遞歸算法 
void PostOrder2(BiTree T);//後序遍歷非遞歸算法 
void LevelOrder(BiTree T);//層次遍歷 
void InQueue(Queue *q,BiTree t);//入隊 
BiTree OutQueue(Queue *q);//出隊 
void Push(NodeStack *head,BiTree t);//入棧 
BiTree Pop(NodeStack *head);//出棧 
BiTree GetTop(NodeStack *head);//得到棧頂元素 

int main()
{
    BiTree T;
    T=Create_BiTree(T);
    printf("先序遍歷非遞歸:\n");
    PreOrder2(T);
    printf("中序遍歷非遞歸:\n");
    InOrder2(T);
    printf("後序遍歷非遞歸:\n");
    PostOrder(T);
    printf("層次遍歷:\n");
    LevelOrder(T);
        
    return 0;
}

BiTree Create_BiTree(BiTree T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
    {
        T=NULL;
     } 
     else
     {
         T=(BiTree)malloc(sizeof(BiNode));
         T->data=ch;
         T->lchild=Create_BiTree(T->lchild);
         T->rchlid=Create_BiTree(T->rchlid);
     }
     return T;
}

void PreOrder(BiTree T)
{
    if(T!=NULL)
    {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchlid);
    }
}
void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchlid);
    }
}
void PostOrder(BiTree T)
{
    if(T!=NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchlid);
        visit(T);
    }
 } 
 
 void visit(BiTree T)
 {
     printf("%c\n",T->data);
 }
 
 void InOrder2(BiTree T)
 {
     //InitStack(S)
     NodeStack *s;
    s=(NodeStack*)malloc(sizeof(NodeStack));
    s->next=NULL;

    BiTree p=T;
    while(p||s->next!=NULL)
    {
        if(p)
        {
            Push(s,p);
            p=p->lchild;
        }
        else
        {
            p=Pop(s);
            visit(p);
            p=p->rchlid;
        }
    }    
 }
 
 void PreOrder2(BiTree T)
 {
     //InitStack(S)
     NodeStack *s;
    s=(NodeStack*)malloc(sizeof(NodeStack));
    s->next=NULL;
    
    BiTree p=T;
    while(p||s->next!=NULL)
    {
        if(p)
        {
            visit(p);
            Push(s,p);
            p=p->lchild;
        }
        else
        {
            p=Pop(s);
            p=p->rchlid;
        }
    }    
 }
 
 void PostOrder2(BiTree T)
 {
     NodeStack *s;
    s=(NodeStack*)malloc(sizeof(NodeStack));
    s->next=NULL;
    BiTree p=T,r=NULL;
    while(p||s->next!=NULL)
    {
        if(p)
        {
            Push(s,p);
            p=p->lchild;
        }
        else
        {
            p=GetTop(s);
            if(p->rchlid&&p->rchlid!=r)
            {
                p=p->rchlid;
                Push(s,p);
                p=p->lchild;
            }
            else
            {
                p=Pop(s);
                visit(p);
                r=p;
                p=NULL;
            }
        }
    }
 }
 
 void LevelOrder(BiTree T)
 {
     Queue Q;
     Q.front=Q.rear=(Node*)malloc(sizeof(Node));
    Q.front->next=NULL;
    
    BiTree p;
    InQueue(&Q,T);
    while(Q.front!=Q.rear)
    {
        p=OutQueue(&Q);
        visit(p);
        if(p->lchild!=NULL)
        {
            InQueue(&Q,p->lchild);
        }
        if(p->rchlid!=NULL)
        {
            InQueue(&Q,p->rchlid);
        }
    }
    
 }
 
 void Push(NodeStack *head,BiTree t)
{
    NodeStack *p=(NodeStack*)malloc(sizeof(NodeStack));
    p->data=t;
    p->next=head->next;
    head->next=p;
}

BiTree Pop(NodeStack *head)
{
    NodeStack *p=(NodeStack*)malloc(sizeof(NodeStack));
    p=head->next;
    head->next=p->next;
    return p->data;
}

void InQueue(Queue *q,BiTree t)
{
    Node *p=(Node*)malloc(sizeof(Node));
    p->data=t;
    p->next=NULL;
    q->rear->next=p;
    q->rear=p;
}

BiTree OutQueue(Queue *q)
{
    Node *p=q->front->next;
    q->front->next=p->next;
    if(q->rear==p)
    {
        q->rear=q->front;
    }
    return p->data;
}

BiTree GetTop(NodeStack *head)
{
    return head->next->data;
}

void PreOrder2(BiTree T)
 {
     //InitStack(S)
     NodeStack *s;
    s=(NodeStack*)malloc(sizeof(NodeStack));
    s->next=NULL;
    
    BiTree p=T;
    while(p||s->next!=NULL)
    {
        if(p)
        {
            visit(p);
            Push(s,p);
            p=p->lchild;
        }
        else
        {
            p=Pop(s);
            p=p->rchlid;
        }
    }    
 }