#include<stdio.h>
#include<stdlib.h>
#define stacksize 100
#define STACKINCREMENT 10
typedef struct BiTNode//树的定义
{
int date;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct{
BiTNode *base;
BiTNode *top;
int StackSize; //当前已经分配的存储空间,以元素为单位
}SqStack;
int InitStack(SqStack &S)//初始化
{
S.base=(BiTNode *)malloc(stacksize*sizeof(BiTNode));
if(!S.base){
return -2;
}
S.top = S.base;
S.StackSize=stacksize;
return 1;
}
int Push(SqStack &s,BiTNode &e)//入栈
{
BiTNode *p;
if(s.top-s.base == s.StackSize){
p = (BiTNode *)realloc(s.base,(stacksize+STACKINCREMENT)*sizeof(BiTNode));
if(!p){
return -2;
}
s.base=p;
s.top = s.base + s.StackSize;
s.StackSize+=STACKINCREMENT;
}
*(s.top)=e;
s.top++;
return 1;
}
BiTNode Pop(SqStack s,BiTNode *e)//出栈
{
if(s.top != s.base){
s.top--; //先将栈顶指针减 1
*e=*(s.top);
}
return *e;
}
int creatBiTNode(BiTree &bt)//先序创建二叉树
{
int ch;
scanf("%d",&ch);
if(ch==0)
bt=NULL;
else{
bt=(BiTNode*)malloc(sizeof(BiTNode));
bt->date=ch;
creatBiTNode(bt->lchild);
creatBiTNode(bt->rchild);
}
return 0;
}
int preorder(BiTree bt)//顺序非递归访问二叉树
{
BiTNode *p;
SqStack *st;
InitStack(*st);
p=bt;
while(st->top!=st->base||p)
{
while(p)
{
printf("%d ",p->date);
Push(*st,*p);
p=p->lchild;
}
if(st->top!=st->base)
{
Pop(*st,p);
p=p->rchild;
}
}
return 0;
}
int main()
{
BiTNode *bt;
creatBiTNode(bt);
printf("先序序列为\n");
preorder(bt);
return 0;
}