#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef int Status; /* 函数结果状态代码,如OK等 */
typedef char TElemType;
typedef struct BiTNode {
        TElemType data;
        struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */
typedef struct SqStack {
        SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
        SElemType *top; /* 栈顶指针 */
        int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
TElemType Nil=' '; /* 字符型以空格符为空 */
Status InitStack(SqStack *S) { /* 构造一个空栈S */
        (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
        if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */
        (*S).top=(*S).base;
        (*S).stacksize=STACK_INIT_SIZE;
        return OK;
}
Status StackEmpty(SqStack S) { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
        if(S.top==S.base)
                return TRUE;
        else
                return FALSE;
}
Status Push(SqStack *S,SElemType e) { /* 插入元素e为新的栈顶元素 */
        if((*S).top-(*S).base>=(*S).stacksize) { /* 栈满，追加存储空间 */
                (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
                if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */
                (*S).top=(*S).base+(*S).stacksize;
                (*S).stacksize+=STACKINCREMENT;
        }
        *((*S).top)++=e;
        return OK;
}
Status Pop(SqStack *S,SElemType *e) {
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
        if((*S).top==(*S).base) return ERROR;
        *e=*--(*S).top;
        return OK;
}
Status GetTop(SqStack S,SElemType *e) {
/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
        if(S.top>S.base) {
                *e=*(S.top-1);
                return OK;
        } else
                return ERROR;
}
Status InitBiTree(BiTree *T) { /* 操作结果: 构造空二叉树T */
        *T=NULL;
        return OK;
}
void CreateBiTree(BiTree *T) {
/* 算法6.4:按先序次序输入二叉树中结点的值（可为字符型或整型，在主程序 */
/* 中定义），构造二叉链表表示的二叉树T。变量Nil表示空（子）树。 */
        TElemType ch;
        scanf("%c",&ch);
        if(ch==Nil) { /* 空 */
                *T=NULL;
        } else {
                *T=(BiTree)malloc(sizeof(BiTNode));
                if(!*T) exit(OVERFLOW);
                (*T)->data=ch; /* 生成根结点 */
                CreateBiTree(&(*T)->lchild); /* 构造左子树 */
                CreateBiTree(&(*T)->rchild); /* 构造右子树 */
        }
}
Status visitT(TElemType e) {
        printf("%c ",e);
        return OK;
}
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)) {
/* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1，有改动 */
/* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
        if(T) { /* T不空 */
                Visit(T->data); /* 先访问根结点 */
                PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树 */
                PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树 */
        }
}
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType)) {
/* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
        SqStack S;
        InitStack(&S);
        while(T||!StackEmpty(S)) {
                if(T) { /* 根指针进栈,遍历左子树 */
                        Push(&S,T);
                        T=T->lchild;
                } else { /* 根指针退栈,访问根结点,遍历右子树 */
                        Pop(&S,&T);
                        if(!Visit(T->data))
                        return ERROR;
                        T=T->rchild;
                }
        }
        printf("\n");
        return OK;
}
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType)) {
/* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
        SqStack S;
        BiTree p;
        InitStack(&S);
        Push(&S,T); /* 根指针进栈 */
        while(!StackEmpty(S)) {
                while(GetTop(S,&p)&&p)
                        Push(&S,p->lchild); /* 向左走到尽头 */
                Pop(&S,&p); /* 空指针退栈 */
                if(!StackEmpty(S)) { /* 访问结点,向右一步 */
                        Pop(&S,&p);
                        if(!Visit(p->data)) return ERROR;
                        Push(&S,p->rchild);
                }
        }
        printf("\n");
        return OK;
}
int main() {
        int i;
        BiTree T,p,c;
        TElemType e1,e2;
        InitBiTree(&T);
        CreateBiTree(&T);
        PreOrderTraverse(T,visitT); puts("");
        InOrderTraverse1(T,visitT);
        InOrderTraverse2(T,visitT);
        return 0;
}
/**************************************************************
	Problem: 2154
	User: admin
	Language: C
	Result: Accepted
	Time:16 ms
	Memory:1148 kb
****************************************************************/