#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct BiTNode//树的定义
{
char date;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct//栈的定义
{
int *base;
int *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S)//初始化栈
{
S.base=(int *)malloc(100*sizeof(char));
S.top=S.base;
S.stacksize=100;
}
bool StackEmpty(SqStack S)//判断栈空
{
if(S.top==S.base)
return 1;
else
return 0;
}
bool Push(SqStack &S,char e)//入栈
{
if(S.top-S.base==S.stacksize)
return 0;
*S.top++=e;
return 1;
}
bool Pop(SqStack &S,char &e)//出栈
{
if(S.top==S.base);
return 0;
e=*--S.top;
return 1;
}
int creatBiTNode(BiTree &bt)//顺序创建二叉树
{
char ch;
scanf("%c",&ch);
if(ch=='#')
bt=0;
else{
bt=(BiTNode*)malloc(sizeof(BiTNode));
bt->date=ch;
creatBiTNode(bt->lchild);
creatBiTNode(bt->rchild);
}
}
int preorder(BiTree &bt)//顺序非递归访问二叉树
{
BiTNode *p;
SqStack *st;
InitStack(*st);
p=bt;
while(!StackEmpty(*st)||p!=0)
{
while(p!=0)
{
printf("%c ",p->date);
Push(*st,p->date);
p=p->lchild;
}
if(!StackEmpty(*st))
{
Pop(*st,p->date);
p=p->rchild;
}
}
}
int main()//测试
{
BiTree bt;
printf("先序输入二叉树的节点,'#'表示空");
creatBiTNode(bt);
printf("这棵树的先序节点为");
preorder(bt);
return 0;
}