#define STACK_SIZE 100
#define STACK_INC 10
#define OK 1
#define ERROR 0

typedef struct BinNode
{
    char data;
    struct BinNode *lchild, *rchild;
}BiNode,*BiTree;
//建立二叉树
int CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if (ch=='.')
        *T=NULL;
    else
    {
        if (!(*T=(BiNode *)malloc(sizeof(BiNode))))
        {
            printf("存储空间分配失败");
            return 0;
        }
        //生成一个新节点
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
    return 1;
}
typedef BiTree Elem;

typedef struct
{
    Elem *base;
    Elem *top;
    int size;
}SqStack;

typedef int Status;

Status CreatStack(SqStack &S)
{
    S.base=(Elem *)malloc(STACK_SIZE*sizeof(Elem));
    S.top=S.base;
    S.size=STACK_SIZE;
    return OK;
}

Status StackEmpty(SqStack S)
{
    if (S.top!=S.base)
        return ERROR;
    return OK;
}

//进栈
Status Push(SqStack &S,Elem e)
{
    if (S.top-S.base>=S.size)
    {
        S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem));
        S.top=S.base+S.size;
        S.size+=STACK_INC;
    }
    *S.top=e;
    S.top+=1;
    return OK;
}

//出栈
Status Pop(SqStack &S,Elem &e)
{
    if (S.top==S.base) return ERROR;
    S.top-=1;
    e=*S.top;
    return OK;
}

//中序非递归遍历
void inOrder(BiTree t)
{
    SqStack s;
    CreatStack(s);
    while (t!=NULL||!StackEmpty(s))
    {
        while (t!=NULL)//走到左下角
        {
            Push(s,t);
            t=t->lchild;
        }
        if (!StackEmpty(s))
        {
            Pop(s,t);
            printf("%c",t->data);
            t=t->rchild;
        }
    }
}

//先序非递归遍历
void preOrder(BiTree t)
{
    SqStack s;
    CreatStack(s);
    while (t!=NULL||!StackEmpty(s))
    {
        while (t!=NULL)
        {
            printf("%c",t->data);
            Push(s,t);
            t=t->lchild;
        }
        if (!StackEmpty(s))
        {
            Pop(s,t);
            t=t->rchild;
        }
    }
}
//后序非递归遍历
void postOrder(BiTree t)
{
    BiTree stack[20];
    int visited[20];
    int top=0;
    while (t!=NULL||top>0)
    {
        while (t!=NULL)//扫描左节点
        {
            top++;
            stack[top] = t;
            visited[top]=0;//标记为未访问
            t=t->lchild;
        }
        t = stack[top];
        top-;
        if (visited[top+1] ==1)//
        {
            printf("%c",t->data);
            t=NULL;
        }
        else
        {
            top++;
            stack[top] = t;
            visited[top] = 1;                  //标记为访问
            t=t->rchild;

        }
    }
}
int main()
{
    BiTree T=NULL;
    printf("请输入一个先序扩展序列,节点数据为字符类型,\n且用句点表示空节点:");
    if (CreateBiTree(&T))
        printf("二叉树创建成功!\n");
    else
        printf("二叉树创建失败!\n");
    printf("\n中序非递归遍历为:\n");
    inOrder(T);
    printf("\n先序非递归遍历为:\n");
    preOrder(T);
    printf("\n后序非递归遍历为:\n");
    postOrder(T);
    system("pause");
}