非递归实现树的操作

#include "stdio.h"
#include
#include

#define OVERFLOW -2
#define OK 1
#define ERROR 0

typedef  int  status;

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
 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 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){ 
//若栈不空，则删除栈顶元素，用e返回其值，并返回OK，否则返回ERROR
 if(S.top==S.base)
  return ERROR;
 e=*--S.top;
 return OK;
}

status StackEmpty(SqStack S){
//判断栈S是否为空，为空则返回OK，否则返回ERROR
 if(S.top==S.base)
  return OK;
 else return ERROR;
}
status CreateBiTree(BiTree &T){
//按先序次序建立二叉树的递归算法
 char 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;
}
status PreOrderTraverse(BiTree T)
{//先序遍历二叉树的非递归算法
 SqStack S;
 InitStack(S);
 BiTNode *p=T;
 printf("先序遍历二叉树所得序列：");
 while(p!=NULL||!StackEmpty(S))
 {
  while(p!=NULL)
  {
   printf("%c",p->data);
   Push(S,p);
   p=p->lchild;
  }  
  Pop(S,p);  
  p=p->rchild;  
 } 
 printf("\n");
 return OK;
}
status InOrderTraverse(BiTree T)
{//中序遍历二叉树的非递归算法
 
//中序遍历二叉树非递归算法BiTNode *p,*s[100];
SqStack S;
 InitStack(S);
 BiTNode *p=T;
 printf("中序遍历二叉树所得序列：");
while((p!=NULL)||!StackEmpty(S))  //若树或栈非空：
{   while(p!=NULL)
    {  Push(S,p);  //把左子树入栈，
        p=p->lchild;  //直到最左下角；
     } 
     Pop(S,p);       //（子树）根指针出栈；
     printf("%c",p->data);//访问（子树）根结点；
     p=p->rchild;    //把右子树入栈
}
return OK;
}
int main()
{//根据主函数完成实验报告部分。
 BiTree T; 
 printf("输入字符创建一棵树，空格表示结束\n");
 if(CreateBiTree(T))
 {
  printf("\n先序遍历：");
PreOrderTraverse(T);  
printf("\n中序遍历：");
InOrderTraverse(T);
 }
 getchar();
 getchar();
 return 0;
}