#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define TRUE            1
#define FALSE           0
#define OK              1
#define ERROR           0
#define INFEASIBLE        -1
#define OVERFLOW        -2

#define MAXQSIZE 50

typedef int Status;
typedef char TElemType;/*数据类型*/

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,/*二叉链表节点*/
*BiTree;/*二叉树*/

/********部分基本操作的函数原型********/
Status CreateBiTree(BiTree *T);
Status LevelOrderTraverse(BiTree T, Status (*visit)(TElemType e));

Status operate(TElemType e);

/*********************栈**********************/
typedef BiTree SqStackElemType;

typedef struct
{
int top,base,count;
SqStackElemType container[100];/*ROW*COLUM];*/
}SqStack;

Status InitStack(SqStack *s);
Status StackEmpty(SqStack s);
Status Push(SqStack *s,SqStackElemType e);
Status Pop(SqStack *s,SqStackElemType *e);

/********栈的部分操作定义**********/
Status InitStack(SqStack *s)
{
s->top=-1;
s->base=0;
s->count=0;
}

Status StackEmpty(SqStack s)
{
if(s.count!=0)
{return FALSE;}
return TRUE;
}

Status Push(SqStack *s,SqStackElemType e)
{
s->top++;
s->container[s->top]=e;
s->count++;
return OK;
}

Status Pop(SqStack *s,SqStackElemType *e)
{
if(s->top<s->base)
{return ERROR;}
*e = s->container[s->top];
s->top--;
s->count--;
}

Status GetHead(SqStack s,SqStackElemType *e)
{
    if(s.top<s.base)
    {return ERROR;}
    *e = s.container[s.top];
}
/*********************END栈**********************/

/*********************队列(非循环顺序队列)************************/
typedef BiTree QElemType;

typedef struct SqQueue
{
    QElemType * base;
    int front;
    int rear;
}SqQueue;

Status InitQueue(SqQueue *Q)
{
    Q->base = (QElemType *)malloc(MAXQSIZE *sizeof(QElemType));
    if(!Q->base)
    {exit(OVERFLOW);}
    Q->front = Q->rear = 0;
    return OK;
}

int QueueLength(SqQueue Q)
{
    return Q.rear - Q.front;
}

Status QueueEmpty(SqQueue Q)
{
if(Q.front==Q.rear)
{return TRUE;}
return FALSE;
}

Status EnQueue(SqQueue *Q,QElemType e)
{
    if(Q->rear>(MAXQSIZE-1))/*队列满*/
    {
        printf("Something Wrong!");
        return ERROR;
    }
    Q->base[Q->rear]=e;
    (Q->rear)++;
    return OK;
}

Status DeQueue(SqQueue *Q,QElemType *e)
{
    if(Q->front == Q->rear)/*队列空*/
    {
        printf("Something Wrong!");
        return ERROR;
    }
    *e = Q->base[Q->front];
    (Q->front)++;
    return OK;
}
/****************END队列*******************/

/********部分基本操作的函数定义********/

Status CreateBiTree(BiTree *T)/*根据二叉树的广义表输入建树*/
{
    SqStack ss;
    BiTree bt,parent;
    int i,flag;
    char input[50];/*输入的数据*/

    InitStack(&ss);


    flag=0;/*0左,1右*/


    for(i=0;i<50;i++)
    {
        input[i]='\n';/*把空设置为'\n'*/
    }

    scanf("%s",input);

    for(i=0;i<50;i++)
    {
        if(input[i]!='\n'&&input[i]!='\x0')
        {
            switch(input[i])
            {
            case '(':
                {
                    flag=0;
                    Push(&ss,bt);
                    break;
                }
            case ')':
                {
                    flag=0;
                    Pop(&ss,&bt);
                    break;
                }
            case ',':
                {
                    flag=1;
                    break;
                }
            default:
                {
                    if(StackEmpty(ss))
                    {
                        (*T)=(BiTNode *)malloc(sizeof(BiTNode));
                        (*T)->data=input[i];
                        bt=(*T);

                        bt->lchild=0;/*左右子树初始为0*/
                        bt->rchild=0;
                    }
                    else
                    {
                        bt=(BiTNode *)malloc(sizeof(BiTNode));

                        bt->lchild=0;/*左右子树初始为0*/
                        bt->rchild=0;

                        bt->data=input[i];
                        GetHead(ss,&parent);
                        if(flag==0||flag==2)
                        {parent->lchild = bt;}
                        else
                        {parent->rchild = bt;}
                    }
                    break;
                }
            }
        }
        else
        {
            break;
        }
    }
}

Status LevelOrderTraverse(BiTree T, Status (*visit)(TElemType e))
{
    SqQueue sq;
    BiTree bt,cbt;

    InitQueue(&sq);
    EnQueue(&sq,T);
    while(!QueueEmpty(sq))
    {
        DeQueue(&sq,&bt);
        (*visit)(bt->data);

        if((bt->lchild)!=0)
        {
            cbt = bt->lchild;
            EnQueue(&sq, cbt);
        }
        if((bt->rchild)!=0)
        {
            cbt = bt->rchild;
            EnQueue(&sq, cbt);
        }
    }
}

Status operate(TElemType e)
{
    printf("%5c",e);
    return OK;
}

int main()
{
    BiTree bt;
    
    system("cls");
    CreateBiTree(&bt);
    LevelOrderTraverse(bt,operate);

    return 0;
}