1、前序遍历
void preorder_dev(bintree t){
seqstack s;
s.top = -1; //因为top在这里表示了数组中的位置，所以空为-1
if(!t){
printf("the tree is emptyn");
}else{
while(t || s.stop != -1){
while(t){ //只要结点不为空就应该入栈保存，与其左右结点无关
printf("%c ",t->data);
push(&s,t);
t= t->lchild;
}
t=pop(&s);
t=t->rchild;
}
}
}
2、中序遍历
void midorder(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!n");
}else{
while(t ||s.top != -1){
while(t){
push(&s,t);
t= t->lchild;
}
t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}
3、后序遍历
因为后序遍历最后还要要访问根结点一次，所以要访问根结点两次。采取夹标志位的方法解决这个问题。
这段代码非常纠结，对自己有信心的朋友可以尝试独立写一下。反正我是写了很长时间。逻辑不难，我画了一张逻辑图：
代码：
void postorder_dev(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!n");
}else{
while(t || s.top != -1){ //栈空了的同时t也为空。
while(t){
push(&s,t);
s.tag[s.top] = 0; //设置访问标记，0为第一次访问，1为第二次访问
t= t->lchild;
}
if(s.tag[s.top] == 0){ //第一次访问时，转向同层右结点
t= s.data[s.top]; //左走到底时t是为空的，必须有这步！
s.tag[s.top]=1;
t=t->rchild;
}else {
while (s.tag[s.top] == 1){ //找到栈中下一个第一次访问的结点，退出循环时并没有pop所以为其左子结点
t = pop(&s);
printf("%c ",t->data);
}
t = NULL; //必须将t置空。跳过向左走，直接向右走
}
}
}
}
4、层次遍历：即每一层从左向右输出
元素需要储存有先进先出的特性，所以选用队列存储。
队列的定义：
#define MAX 1000
typedef struct seqqueue{
bintree data[MAX];
int front;
int rear;
}seqqueue;
void enter(seqqueue *q,bintree t){
if(q->rear == MAX){
printf("the queue is full!n");
}else{
q->data[q->rear] = t;
q->rear++;
}
}
bintree del(seqqueue *q){
if(q->front == q->rear){
return NULL;
}else{
q->front++;
return q->data[q->front-1];
}
}
