非递归实现树的操作

时间：2010-09-06 来源：chengbin_liu

#include "stdio.h"
#include <malloc.h>
#include <stdlib.h> #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;
}