#include < stdio.h >
#include < stdlib.h >
typedef char TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode * lchild,
*rchild;
}
BiTNode,
*BiTree;
typedef BiTree SElemType;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct {
SElemType * base;
SElemType * top;
int stacksize;
}
SqStack;
Status 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;
return OK;
}
Status StackEmpty(SqStack S) {
return ! (S.top - S.base);
}
Status GetTop(SqStack S, SElemType & e) {
if (S.top == S.base) return ERROR;
e = *(S.top - 1);
return OK;
}
Status Push(SqStack & S, SElemType 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) {
if (S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}
Status PrintElement(TElemType e) {
printf("%c", e);
return OK;
}
/*Status InOrderTraverse(BiTree T,Status (* Visit)(TElemType e))
{BiTree p;
SqStack S;
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);
}
}
return OK;
}*/
Status InOrderTraverse(BiTree T, Status( * Visit)(TElemType e)) {
BiTree p;
SqStack S;
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;
}
}
return OK;
}
Status CreateBiTree(BiTree & T) {
TElemType ch;
scanf("%c", &ch);
if (ch == ' ') T = NULL;
else {
if (! (T = (BiTNode * ) malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T - >data = ch;
CreateBiTree(T - >lchild);
CreateBiTree(T - >rchild);
}
return OK;
}
void main() {
BiTree T;
printf("\n");
CreateBiTree(T);
InOrderTraverse(T, PrintElement);
}
标签:Status,SElemType,return,SqStack,biTree,top,base From: https://blog.51cto.com/u_16076050/6195971