栈.h

实现构造一个二叉树、二叉树的遍历（递归与非递归方法）

#include<iostream>
using namespace std;
#define STACK_INIT_SIZE  100
#define STACKINCREMENT 10
#define  ERROR 0
#define  OK  1
#define TRUE  1
#define FALSE  0
#define OVERFLOW   -2
typedef int SElemType;
typedef int status;

typedef struct {
SElemType  *base;
SElemType  *top;
	int    stacksize;
}SqStack;

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 DestroyStack(SqStack &S)
{   //销毁栈S
	/*while(S.base!=S.top){
     *(S.top+1)=*S.top;
    free(S.top);
	*S.top=*++S.top;}*/
	free(S.base);
	S.top=S.base;
    return OK;

}	
status ClearStack(SqStack &S)
{   //把S置为空栈
     *S.top=*S.base;
     return OK;
}

status StackEmpty(SqStack &S)
{   //若栈S为空栈，则返回TURE，否则返回FALSE
	if(S.top==S.base)
      return TRUE;
   else
      return FALSE;
}

int StackLength(SqStack S)
{  //返回S的元素个数，即栈的长度
	int i=0;
	while(S.top!=S.base){
	--S.top;
	++i;
	
	}
	return i;
}
status GetTop(SqStack S,SElemType &e)
{   //若栈不空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR 
	if(S.top==S.base)
      return ERROR;
     e=*(S.top-1);
	 return OK;
}
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 e;
}
status StackTraverse(SqStack S,status(*visit)(SElemType))
{  //从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败，则操作失败
	if(S.top==S.base)
		return ERROR;
	while(S.top!=S.base)
	{  visit(*S.top);
	  --S.top;
	}
	return OK;
}