#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<process.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0


#define STACK_INIT_SIZE 10
#define STACKINCREAMENT 2

typedef int Status;

typedef struct BiTnode{
    char a[5];
    BiTnode *lchild,*rchild;
}BiTnode,*BiTree;

typedef BiTree Selemtype;
typedef struct SqStack{
    Selemtype *base;
    Selemtype *top;
    int stacksize;
}SqStack;

typedef BiTree QElemType;
typedef struct Qnode{
    QElemType data;
    Qnode *next;
}Qnode,*Queueptr;
typedef struct{
    Queueptr front;
    Queueptr rear;
}LinkQueue;

void Initqueue(LinkQueue &Q){
    if(!(Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode))))
        exit(OVERFLOW);
    Q.front->next=NULL;
}

Status Queueempty(LinkQueue Q){
    if(Q.front->next==NULL)
        return TRUE;
    else 
        return FALSE;
}

void Enqueue(LinkQueue &Q,QElemType e){
    Queueptr p;
    if(!(p=(Queueptr)malloc(sizeof(Qnode))))
        exit(OVERFLOW);
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
}

Status Dequeue(LinkQueue &Q,QElemType &e)//删除Q的队头元素
{
    Queueptr p;
    if(Q.front==Q.rear)
        return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return OK;
}
void Initstack(SqStack &s){
    
    s.base=(Selemtype *)malloc(STACK_INIT_SIZE*sizeof(Selemtype));
    if(!s.base)
        exit(OVERFLOW);
    
    s.top=s.base;
    s.stacksize=STACK_INIT_SIZE;
}

void push(SqStack &s,Selemtype e){
    if(s.top-s.base>=s.stacksize){
        s.base=(Selemtype *)realloc(s.base,(s.stacksize+STACKINCREAMENT)*sizeof(Selemtype));
        if(!s.base)
            exit(OVERFLOW);
        s.top=s.base+s.stacksize;
        s.stacksize+=STACKINCREAMENT;
    }
    *(s.top)++=e;

}

Status Stackempty(SqStack s){
    if(s.top==s.base)
        return TRUE;
    else return FALSE;
}

Status pop(SqStack &s,Selemtype &e){
    if(s.top==s.base)
        return ERROR;
    e=*--s.top;
    
    return OK;
}

Status Gettop(SqStack S,Selemtype &e){
    if(S.top>S.base)
    {
        e=*(S.top-1);
        return OK; 
    }
    
    else 
        return ERROR;
}

void creat(BiTree &T){
    char ch;

    scanf("%c",&ch);
    if(ch==' ') T=NULL;
    else{
        if(!(T=(BiTree)malloc(sizeof(BiTnode))))
            exit (OVERFLOW);
        T->a[2]=ch;T->a[1]=T->a[3]='#';T->a[0]=T->a[4]='0';
        creat(T->lchild);
        creat(T->rchild);
    }
    
}//先序建立

void print(char *p)
{
    int i;
    if(*p-'0'>0)
    {
        i=*p-'0';
        for(;i>0;i--)
        printf("%c",*(p+1));
    }
    printf("%c",*(p+2));
    if(*(p+4)-'0'>0){
        i=*(p+4)-'0';
        for(;i>0;i--)
            printf("%c",*(p+3));
    }
}

void inordertraverse(BiTree T,void(*visit)(char *))
{
    if(T){
        inordertraverse(T->lchild,visit);
        visit(T->a);
        inordertraverse(T->rchild,visit);
    }

}

void preordertraverse1(BiTree T,void(*visit)(char *))
{
    if(T){
        visit(T->a);
        preordertraverse1(T->lchild,visit);
        preordertraverse1(T->rchild,visit);
    }

}

void postordertraverse(BiTree T,void(*visit)(char *))
{
    if(T){
        postordertraverse(T->lchild,visit);
        postordertraverse(T->rchild,visit);
        visit(T->a);
    }
}


void leveltraverse(BiTree T,void(*visit)(char *)){
    LinkQueue Q;QElemType p;
    if(T){
        Initqueue(Q);
        Enqueue(Q,T);
        while(!Queueempty(Q))
        {
            Dequeue(Q,p);visit(p->a);
            if(p->lchild!=NULL)
                Enqueue(Q,p->lchild);
            if(p->rchild!=NULL)
                Enqueue(Q,p->rchild);
        }
    }

}


int i1=0;
void count1(char *p){
    //while(p!=' ')
        i1++;
}
Status count(BiTree T){
    inordertraverse(T,count1);
    return i1;
}

int j=0;
Status countl(BiTree T)
{
    LinkQueue q;
    QElemType a;
    if(T){
        Initqueue(q);
        Enqueue(q,T);
        while(!Queueempty(q)){
            Dequeue(q,a);
            if((a->lchild==NULL)&&(a->rchild==NULL))
                j++;
            else{
                if(a->lchild)
                    Enqueue(q,a->lchild);
                if(a->rchild)
                    Enqueue(q,a->rchild);
            }
        }
        
    }
    return j;
}

Status Bitreedepth(BiTree T){
    SqStack s;Initstack(s);
    int level=0,height=0;
    BiTree p=T;Selemtype q;
    while((p!=NULL)||(!Stackempty(s))){
        if(p!=NULL){
            level=level+1;
            if(level>height)
                height=level;
            push(s,p);
            p=p->lchild;
        }
        else{
            Gettop(s,q);
            while((q->rchild==p)&&(level>=0)){
                pop(s,p);
                level=level-1;
                Gettop(s,q);
                p=q->rchild;
            }
        }
    }
    return height;
}

Status Widthbitree(BiTree T){
    BiTree s[20]={NULL};int i;
    for(i=0;i<20;i++){
        s[i]=(BiTree)malloc(sizeof(BiTnode));
        s[i]->lchild=s[i]->rchild=NULL;
    }
    int width[20]={0},top=0,height=0;
    Selemtype p=T,old=NULL;
    while((p!=NULL)||(top!=0)){
        if(p!=NULL)
        {
            top=top+1;
            width[top]=width[top]+1;
            s[top]=p;
            p=p->lchild;
            if(height<top)
                height=top;
        }
        while((top>0)&&((s[top]->rchild==old)||(s[top]->rchild==NULL))){
            old=s[top];
            top=top-1;
            p=s[top]->rchild;
        }
    }
    int k=1;
    for(i=2;i<=height;i++)
        if(width[k]<width[i])
            k=i;
        return (width[k]);
}

void   copytree(BiTree S,BiTree &T)
{
    
    BiTree lptr=NULL,rptr=NULL;
    if(!S) T=NULL;
    else{
        copytree(S->lchild,lptr);
        copytree(S->rchild,rptr);
        T=(BiTree)malloc(sizeof(BiTnode));        
        T->a[2]=S->a[2];
        T->lchild=lptr,T->rchild=rptr;
    }
    return;
}

void DestroyBitree(BiTree &T){
    if(T){
        if(T->lchild)
            DestroyBitree(T->lchild);
        if(T->rchild)
            DestroyBitree(T->rchild);
        free(T);
        T=NULL;
    }
}
void  visit1(char p){
    printf("%c",p);
}




char s[100]={0};char *q=s;int k=0;




void visit2(char *p){
    
    s[k]=*(p+2);
    k++;
}

char value(BiTree T){
    SqStack s1,s2;int i=0,m=0;
    postordertraverse(T,visit2);
     BiTree p[20];
     for(;m<20;m++)
      p[m]=(BiTree)malloc(sizeof(BiTnode));    
    Initstack(s1),Initstack(s2);
    for(;i<k;i++)
    {p[i]->a[2]=s[i];p[i]->a[1]=p[i]->a[3]='#';p[i]->a[0]=p[i]->a[4]='0';
    p[i]->lchild=p[i]->rchild=NULL;
    push(s1,p[i]);
    }
    Selemtype e,e1,e2;
    e=(BiTree)malloc(sizeof(BiTnode));
    e1=(BiTree)malloc(sizeof(BiTnode));
    e2=(BiTree)malloc(sizeof(BiTnode));
    while(s1.top-s1.base>0){
        pop(s1,e);
        if((e->a[2]=='+')||(e->a[2]=='-')||(e->a[2]=='*')||(e->a[2]=='/')){
            pop(s1,e1);
            pop(s1,e2);
            if(((e1->a[2]-'0'>=0)&&(e1->a[2]-'9'<=0))&&((e2->a[2]-'0'>=0)&&(e2->a[2]-'9'<=0))){
                switch(e->a[2]){
                case '+':e->a[2]=e2->a[2]+e1->a[2]-'0';
                    push(s2,e);break;
                case '-':e->a[2]=e2->a[2]-e1->a[2]+'0';
                    push(s2,e);break;
                case '*':e->a[2]=(e2->a[2]-'0')*(e1->a[2]-'0')+'0';
                    push(s2,e);break;
                case '/':e->a[2]=(e2->a[2]-'0')/(e1->a[2]-'0')+'0';
                    push(s2,e);break;
                }
            }
                else 
                {push(s1,e2);push(s1,e1);push(s2,e);}        
        }
        else push(s2,e);
    }
    while(s2.top-s2.base>0){
        if(s2.top-s2.base==1)
        return (*s2.base)->a[2];
        else{
            pop(s2,e);pop(s2,e1);pop(s2,e2);
            switch(e2->a[2]){
            case '+':e2->a[2]=e->a[2]+e1->a[2]-'0';
                push(s2,e2);break;
            case '-':e2->a[2]=e->a[2]-e1->a[2]+'0';
                push(s2,e2);break;
            case '*':e2->a[2]=(e->a[2]-'0')*(e1->a[2]-'0')+'0';
                push(s2,e2);break;
            case '/':e2->a[2]=(e->a[2]-'0')/(e1->a[2]-'0')+'0';
                push(s2,e2);break;
            }
        }
    }
}

int im=0,m,ic;
void mid(BiTree T){
    if(T->lchild!=NULL&&T->rchild!=NULL){
        if(im<m){
            im++;BiTree B;;
            if((T->a[2]=='+')||(T->a[2]=='-')){
                B=T;ic++;
                while(B->lchild!=NULL)
                    B=B->lchild;
                B->a[1]='(';B->a[0]++;
                B=T;
                while(B->rchild!=NULL)
                    B=B->rchild;
                B->a[3]=')';    B->a[4]++;
            }        
        }
            mid(T->lchild);
            mid(T->rchild);
    }
    return;
}

void main()
{
    BiTree L[2]={NULL};
   
    
    int i,j,k1,k2;
    printf("*****0:退出\n");
    printf("*****1:创建二叉树\n");
    printf("*****2:遍历二叉树\n");
    printf("*****3:计算结点树\n");
    printf("*****4:计算叶子树\n");
    printf("*****5:计算二叉树深度\n");
    printf("*****6:复制二叉树\n");
    printf("*****7:销毁二叉树\n");
    printf("*****8:求二叉树宽度\n");
    printf("*****9:二叉树求值\n");
    printf("*****10:还原中缀表达式\n");
    for(;;){
        printf("请选者操作:(0-10)\n");
        scanf("%d",&m);
        switch(m)
        {
        case 0: exit(0);
        case 1: printf("请输入想要创建二叉树的位置(0-1):");
            scanf("%d",&i);
            printf("请输入节点:");
            getchar(); creat(L[i]);
            break;
        case 2: printf("请输入想要遍历二叉树的位置(0-1):");
            scanf("%d",&i);
            printf("请输入想要遍历二叉树的方法(0-3):\n");
            scanf("%d",&i1);
            switch(i1){
            case 0:printf("先序遍历:\n");
                preordertraverse1(L[i],print);printf("\n");break;
            case 1:printf("中序遍历:\n");
                inordertraverse(L[i],print);printf("\n");break;
            case 2:printf("后序遍历\n");
                postordertraverse(L[i],print);printf("\n");break;
            case 3:printf("层序遍历:\n");
                leveltraverse(L[i],print);printf("\n");break;
            }
            break;
            case 3: printf("请输入求结点二叉树位置(0-1):\n");
                scanf("%d",&i);
                i1=0;k1=count(L[i]);
                printf("结点数为:%d\n",k1);
                break;
            case 4:printf("输入求的叶子数位置(0-1)\n");
                scanf("%d",&i); 
                k2=countl(L[i]);
                printf("叶子数为:%d\n",k2);
                break;     
            case 5:
                printf("输入求深度的位置(0-1)\n");
                scanf("%d",&i);     
                j=Bitreedepth(L[i]);
                printf("深度为:%d\n",j);
                break;                                                                                                            
            case 6:printf("复制二叉树:\n");
                copytree(L[0],L[1]);
                preordertraverse1(L[1],print);
                printf("\n");
                break;                                                                                     
            case 7:printf("输入销毁二叉树的位置:(0-1)\n");
                scanf("%d",&i);     
                DestroyBitree(L[i]);
                break;             
            case 8:printf("输入求二叉树宽度的位置(0-1):\n");
                scanf("%d",&i);
                printf("二叉树宽度为%d\n",Widthbitree(L[i]));
                break;  
            case 9:printf("输入求值二叉树的位置:(0-1)\n");
                scanf("%d",&i);
                printf("二叉树值为:%c\n", value(L[i]));
                break; 
            
            case 10:m=k1-k2;                
                mid(L[0]);
                printf("中缀表达式为:\n");
                inordertraverse(L[0],print);
                printf("\n");break;
        }
    }
}























[em2][em2][em2]