/*要求: 
  a.输入二叉树的先序序列，用#代表虚结点（空指针），
如"ABD###CE##F##"建立二叉树，实现先序、中序和后序以及按层次遍历序列。
  b. 求该二叉树的所有叶子。
先序序列产生二叉树的二叉链表*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 20    //存储空间初始分配量
#define STACKINCREMENT 10  //存储空间分配增量
#define MAXQSIZE 20
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
 
typedef  struct { 
     BiTree *base;
     BiTree  *top;
     int     stacksize;
}SqStack;
typedef struct {
      BiTree   *base;    //初始化动态分配空间
       int       front;
       int       rear;
} SqQueue;

void InitStack(SqStack &S)
{// 构造一个空栈S
   S.base=(BiTree*) malloc (STACK_INIT_SIZE *sizeof(BiTree));
   if (!S.base) exit (0);   //存储分配失败
   S.top=S.base;                 //空表长度为0
   S.stacksize=STACK_INIT_SIZE;     //初始存储容量
}//InitStack

int StackEmpty(SqStack S)
{// 判断栈S是否是空栈，是返回1，否则返回0
    if(S.top==S.base)      return 1;
    else   return 0;
}//StcakEmpty

void Push(SqStack &S, BiTree e)
{// 插入元素e为新的栈顶元素,
   if (S.top-S.base>=S.stacksize)
   {
       S.base=( BiTree* ) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof( BiTree));
           if (!S.base) exit (0);      //存储分配失败
           S.top=S.base +S.stacksize;
           S.stacksize+=STACKINCREMENT;
   }
    
  *S.top++=e;
 }//Push

void Pop(SqStack &S,  BiTree &e)
{//若栈不空则删除S的栈顶元素，并用e返回其值
    if (S.top==S.base)    exit(0);     //栈为空
    e=*--S.top;
 }//Pop

int GetTop(SqStack  S,  BiTree &e)
{//若栈不空则用e返回S的栈顶元素
   if (S.top==S.base)    return 0;      //栈为空
   e=*(S.top-1);
   return 1;
 }//GetTop
 
void InitQueue(SqQueue &Q)
{//构造一个空队列
    Q.base=(BiTree*)malloc(MAXQSIZE*sizeof( BiTree));
    if ( ! Q.base)   
        exit (0);
   Q.front=Q.rear=0;
   
}//InitQueue
int QueueEmpty(SqQueue Q)
{//判断队列是否为空
    if(Q.front==Q.rear)
        return 1;
    else 
        return 0;
}//QueueEmpty

void EnQueue(SqQueue &Q,  BiTree e)
{//插入元素e为Q的新的对尾元素
  if ((Q.rear+1)%MAXQSIZE == Q.front) 
      exit(0);
  Q.base[Q.rear]=e;
  Q.rear=(Q.rear+1) % MAXQSIZE;
}//EnQueue

void DeQueue(SqQueue &Q,  BiTree &e)
{// 删除Q的队头元素, 并用e返回其值
   if(Q.front == Q.rear) 
       exit(0);
   e = Q.base[Q.front];
   Q.front = (Q.front+1) % MAXQSIZE;
  
}

void visit (char e)
{//访问元素
    printf("%3c",e);
}//visit

void CreatBiTree(BiTree &bt)
{//根据给定二叉树的先序遍历序列建立二叉树
    char ch;
    ch=getchar();
    if(ch=='#')
       bt=NULL;
    else
    {
           bt=(BiTNode*)malloc(sizeof(BiTNode));
        bt->data=ch;
           CreatBiTree(bt->lchild);
        CreatBiTree(bt->rchild);
    }//else
}//CreatBiTree

void PreOrderTraverse(BiTree bt  )
{//对于以bt为根结点的二叉树进行先序遍历
    BiTNode *p;
    SqStack S;
    if(bt)
    {
        InitStack(S);
        Push(S,bt);
        while(!StackEmpty(S))
        {
            while(GetTop(S,p)&& p)
            {
                visit(p->data);
            
                Push(S,p->lchild);
            }
            Pop(S,p);
            if(!StackEmpty(S))
            {
                Pop(S,p);
                Push(S,p->rchild);
            }//if
        }
    }

}

void InOrderTraverse(BiTree bt)
{//对于以bt为根结点的二叉树进行先序遍历
    BiTNode *p;
    SqStack S;
    if(bt)
    {
        InitStack(S);
        Push(S,bt);
        while(!StackEmpty(S))
        {
            while(GetTop(S,p)&&p)
            Push(S,p->lchild);
            Pop(S,p);
            if(!StackEmpty(S))
            {
                Pop(S,p);
                visit(p->data);
                Push(S,p->rchild);
            }//if
        }//while
    }//if
}//InorderTraverse

void PostOrderTraverse(BiTree bt)
{//后序遍历
    BiTNode *p,*q;
    SqStack S;
    if(bt)
    {
        InitStack(S);
        Push(S,bt);
        while(!StackEmpty(S))
        {
            while(GetTop(S,p)&&p)
                Push(S,p->lchild);
            Pop(S,p);
            if(!StackEmpty(S))
            {
                GetTop(S,p);
                Push(S,p->rchild);
                if(!p->rchild)
                {
                    Pop(S,p);
                    Pop(S,p);
                    visit(p->data);
                    while(!StackEmpty(S)&&GetTop(S,q)&&q->rchild==p)
                    {
                        Pop(S,p);
                        visit(p->data);
                    }
                    if(!StackEmpty(S))
                        Push(S,q->rchild);
                }
            }
        }
    }
}
int LrlOrderTraverse(BiTree bt)
{//对以bt为根的二叉树进行层次遍历,并返回二叉树的结点数
    SqQueue Q;
    BiTNode *p;
    int i=0;
    
    if(!bt) 
        i=0;
    else
    {
        InitQueue(Q);
        EnQueue(Q,bt);
        while(!QueueEmpty(Q))
        {
            DeQueue(Q,p);
            visit(p->data);
            i++;
            if(p->lchild)
                EnQueue(Q,p->lchild);
            if(p->rchild)
                EnQueue(Q,p->rchild);
        }
    }
   return i;

}

void LeavesBiT(BiTree T)
{
    if(T)
    {
        LeavesBiT(T->lchild);
        if(!T->rchild&&!T->lchild)
            visit(T->data);
        else
            LeavesBiT(T->rchild);
    }
}

void main()
{
    BiTree bt;
    int count;
    printf("输入二叉树的先序遍历的序列:\n");
    CreatBiTree(bt);
    printf("该二叉树的先序遍历序列为：\n");
    PreOrderTraverse(bt);
    printf("\n该二叉树的中序遍历序列为：\n");
    InOrderTraverse(bt);
    printf("\n该二叉树的后序遍历序列为：\n");
    PostOrderTraverse(bt);
    printf("\n该二叉树的层次遍历序列为：\n");
    count=LrlOrderTraverse(bt);
    printf("\n该二叉树的所有叶子结点为：\n");
    LeavesBiT(bt);
    printf("\n该二叉树的节点总数是:%d\n" ,count);
}