#include "stdio.h"
#include "stdlib.h"

#define OK   1
#define ERROR   0
#define OVERFLOW   -1
/*符号常量的定义：OK  ERROR   OVERFLOW   ……*/
typedef  int  TElemType;
typedef  int  Status;
typedef struct BiTNode{
    TElemType    data;
    struct BiTNode   *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
#define STACK_INIT_SIZE 10 // 存储空间的初始分配量
#define STACKINCREMENT 5// 存储空间的分配增量
typedef struct {
    BiTree *base;
    BiTree *top;
int  stackSize;
} SqStack;
/*类型定义：TElemType   Status   结点类型   
结点指针类型    顺序栈类型……  */

/*自定义函数的声明：
  CreateBiTree、PreOrder、InOrder、
  PostOrder、PreOrder_S、InitStack、
  LeafCount、Depth、DeleteChild…… */
  

Status CreateBiTree(BiTree &T);
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
Status InOrder(BiTree T,Status(*Visit)(TElemType e));
Status PrintElement(TElemType e);
Status InitStack(SqStack &S);
Status Push (SqStack &S, BiTree e) ;
Status Pop (SqStack &S, BiTree &e) ;
Status StackEmpty(SqStack S);
  
/*main函数定义：
  在main函数中定义二叉树类型变量，
  通过调用自定义函数完成实验题目
 */
int main()
{
      int cord;BiTree T;TElemType e;
    printf("第一次使用必须输入先序遍历序列构造出二叉树！\n");
    do{
        printf("\n 主菜单 \n");
        printf("1 输入先序遍历序列构造二叉树\n ");
        printf("2 递归方法先序遍历二叉树\n ");
        printf("3 递归方法中序遍历二叉树 \n ");
        printf("4 递归方法后序遍历二叉树 \n ");
        printf("5 非递归方法后序遍历二叉树 \n ");
        printf("6 结束运行 \n ");
        printf("\n-------------------------------------------------------------------\n");
        printf("请输入您的选择( 1, 2, 3, 4,5,6)\n");
        scanf("%d",&cord);
        printf("\n");
        switch(cord){
        case 1:
            printf("输入先序序列：\n");
            CreateBiTree(T) ;
            break;
        case 2:
            PreOrderTraverse(T,PrintElement);
            break;
        case 3:
            InOrderTraverse(T,PrintElement);
            break;
        case 4:
            PostOrderTraverse(T,PrintElement);
            break;
        case 5:
            InOrder(T,PrintElement);
            break;
        case 6:
            exit(0);
}
}while (cord<=6);
return 0;
  system("pause");
      
}
  
Status CreateBiTree(BiTree &T)
{//根据输入的二叉树的先序遍历序列，构建二叉链表存储结构
 //遍历遇到空指针时，在遍历序列中加入代表空指针的字符 ^
 char ch ;
  getchar();
 scanf("%c",&ch);

 if(ch=='0')
      T=NULL;
 else
 {
     if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
     T->data=ch;              //生成根节点
     CreateBiTree(T->lchild);     //构造左子树
     CreateBiTree(T->rchild);   //构造右子树
 }

    return OK;
}

Status PrintElement(TElemType e)
{
    printf("%c\n",e);
    return OK;
}

Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
    if(T){
        if(Visit(T->data))
          if(PreOrderTraverse(T->lchild,Visit))
             if(PreOrderTraverse(T->rchild,Visit))  return OK;
       return ERROR;
    } else  return OK;
   
}

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
   
    if(T){  
        if(InOrderTraverse(T->lchild,Visit))
        if(Visit(T->data))
        if(InOrderTraverse(T->rchild,Visit))  return OK;
       return ERROR;
    } else  return OK;
   
}

Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
   
    if(T){
          if(PostOrderTraverse(T->lchild,Visit))
             if(PostOrderTraverse(T->rchild,Visit))
                 if(Visit(T->data))   return OK;
       return ERROR;
    } else  return OK;
   
   
}

Status InOrder(BiTree T,Status(*Visit)(TElemType e))
{
    SqStack S;BiTree p;
   InitStack(S);p=T;
   while(p||!StackEmpty(S))
   {
       if(p){Push(S,p);
          p=p->lchild;}//根指针进栈，遍历左子树
    else{//根指针退栈，访问根节点，遍历右子树
    Pop(S,p);   if(!Visit(p->data))  return ERROR;
    p=p->rchild ;
           } //else
   }//while
   return OK;
}

// 构造一个空栈 S
Status InitStack(SqStack S){
S.base= (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));
if(!S.base) exit (OVERFLOW);
S.top = S.base;
S.stackSize = STACK_INIT_SIZE;
return OK;
}

//入栈函数
Status Push (SqStack &S,BiTree e) {
if(S.top-S.base>=S.stackSize){
    S.base=(BiTree *) realloc( S.base,
                (S.stackSize+STACKINCREMENT) * sizeof(BiTree));
    if(!S.base) return ERROR;
    S.top=S.base+S.stackSize;
    S.stackSize+=STACKINCREMENT;
}
   *S.top++ = e;
    return OK;

}

//出栈函数
Status Pop (SqStack &S, BiTree &e) {

if(S.top==S.base)
   return ERROR;
   e=*--S.top;
return OK;
}

// 判栈 S 是否为空栈
Status StackEmpty(SqStack S){
if (S.top==S.base) return  OK;
else return  ERROR;
}