tstack1.h

与清华大学版的《数据结构》匹配二叉树的实现：BITREE1.CPP：为主程序

# include "iostream.h"
# include "stdlib.h"
# include "stdio.h"
# define TRUE        1
# define FALSE       0
# define OK		     1
# define ERROR       0
# define INFEASIBLE  -1
# define OVERFLOW    -2
# define NULL        0
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10
# define Status int

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


typedef struct
{
  BiTNode **base;
  BiTNode **top;
  char *d;
  int stacksize;
}SqStack;

Status InitStack(SqStack &S)
{
  S.base=(BiTNode **)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
  S.d=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
  S.top=S.base;
  S.stacksize=STACK_INIT_SIZE;
  //cout<<STACK_INIT_SIZE;
  return OK;
}
Status stackEmpty(SqStack &S)
{
	if (S.top==S.base) return TRUE;
	else	return FALSE;
}

Status Push(SqStack &S,BiTNode *e)
{
  if (S.top-S.base>=S.stacksize)
  {
    S.base=(BiTNode **)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
    if(!S.base) exit(OVERFLOW);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACKINCREMENT;
  }
  *S.top++=e;
  
  return OK;
}//push
Status Push(SqStack &S,BiTNode *e,char d)
{
  if (S.top-S.base>=S.stacksize)
  {
    S.base=(BiTNode **)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
    if(!S.base) exit(OVERFLOW);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACKINCREMENT;
  }
  *S.d++=d;
  *S.top++=e;
  
  return OK;
}//push
Status Pop(SqStack &S,BiTree &e)
{
  if(S.top==S.base) return ERROR;
   e=*--S.top;
  
  return OK;
}//pop
Status Pop(SqStack &S,BiTree &e,char &d)
{
  if(S.top==S.base) return ERROR;
  
  d=*--S.d;
  e=*--S.top;
  
  return OK;
}//pop

/*
void main()
{
 SqStack s;
 InitStack(s);
 cout<<"@#$%%FJH%^&T*H&*(IU*(IU&*(#$%&^%&^#%&$^%#$$%&^^&$%%^%&(*^&*)()"<<endl;
 BiTree p1,p2;

		
  p1=(BiTree )malloc(sizeof(BiTNode));
  p1->data='A';
  p1->lchild=NULL;p1->rchild=NULL;
  cout<<stackEmpty(s)<<endl;
  cout<<"p1:"<<p1<<','<<p1->data<<endl;
  Push(s,p1);//cout<<"p1:"<<p1<<','<<p1->data<<endl;
  cout<<stackEmpty(s)<<endl;
  Pop(s,p1);cout<<"p1:"<<p1<<','<<p1->data<<','<<p1->lchild<<','<<
	p1->rchild<<endl;
  cout<<stackEmpty(s)<<endl;

  char ch='l';
  p2=(BiTree )malloc(sizeof(BiTNode));
  p2->data='B';
  
  Push(s,p1,ch);
  Push(s,p2,'r');
  
  Pop(s,p2,ch);
  cout<<"p2:"<<p2<<','<<p2->data<<','<<ch<<endl;
  
  Pop(s,p1,ch);
  cout<<"p1:"<<p1<<','<<p1->data<<','<<ch<<endl;


}*/