#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:10 ms
	Memory:1148 kb
****************************************************************/