本文介绍了三种实现二叉树非递归先序遍历的方法，旨在提供对栈结构应用的理解及优化遍历算法的思路。
1. 先序遍历非递归算法
```c
#define maxsize 100
typedef struct {
Bitree Elem[maxsize];
int top;
} SqStack;
void PreOrderUnrec(Bitree t) {
SqStack s;
StackInit(s);
p = t;
while (p != NULL || !StackEmpty(s)) {
// 遍历左子树
while (p != NULL) {
visite(p->data);
push(s, p);
p = p->lchild;
}
if (!StackEmpty(s)) {
p = pop(s);
p = p->rchild;
}
}
}
```
2. 中序遍历非递归算法
```c
#define maxsize 100
typedef struct {
Bitree Elem[maxsize];
int top;
} SqStack;
void InOrderUnrec(Bitree t) {
SqStack s;
StackInit(s);
p = t;
while (p != NULL || !StackEmpty(s)) {
// 遍历左子树
while (p != NULL) {
push(s, p);
p = p->lchild;
}
if (!StackEmpty(s)) {
p = pop(s);
visite(p->data); // 访问根结点
p = p->rchild; // 实现右子树遍历
}
}
}
```
3. 后序遍历非递归算法
```c
#define maxsize 100
typedef enum {
L, R
} tagtype;
typedef struct {
Bitree ptr;
tagtype tag;
} stacknode;
typedef struct {
stacknode Elem[maxsize];
int top;
} SqStack;
void PostOrderUnrec(Bitree t) {
SqStack s;
StackInit(s);
p = t;
do {
// 遍历左子树
while (p != NULL) {
stacknode x;
x.ptr = p;
x.tag = L; // 标记为左子树
push(s, x);
p = p->lchild;
}
while (!StackEmpty(s) && s.Elem[s.top].tag == R) {
stacknode x = pop(s);
p = x.ptr;
visite(p->data); // tag为R，表示右子树访问完毕
}
if (!StackEmpty(s)) {
s.Elem[s.top].tag = R; // 遍历右子树
p = s.Elem[s.top].ptr->rchild;
}
} while (!StackEmpty(s));
}
```
5星
