二叉树遍历的一些非递归算法
时间: 2023-11-26 19:47:59 浏览: 41
以下是二叉树遍历的三种非递归算法:
1. 前序遍历(PreOrder):
```c
void PreOrder(BiNode *bt) {
Stack s;
InitStack(&s);
BiNode *p = bt;
while (p || !IsEmpty(s)) {
if (p) {
printf("%c ", p->data);
Push(&s, p);
p = p->lchild;
} else {
Pop(&s, &p);
p = p->rchild;
}
}
}
```
2. 中序遍历(MidOrder):
```c
void MidOrder(BiNode *bt) {
Stack s;
InitStack(&s);
BiNode *p = bt;
while (p || !IsEmpty(s)) {
if (p) {
Push(&s, p);
p = p->lchild;
} else {
Pop(&s, &p);
printf("%c ", p->data);
p = p->rchild;
}
}
}
```
3. 后序遍历(PostOrder):
```c
void PostOrder(BiNode *bt) {
Stack s;
InitStack(&s);
BiNode *p = bt;
BiNode *r = NULL;
while (p || !IsEmpty(s)) {
if (p) {
Push(&s, p);
p = p->lchild;
} else {
GetTop(s, &p);
if (p->rchild && p->rchild != r) {
p = p->rchild;
Push(&s, p);
p = p->lchild;
} else {
Pop(&s, &p);
printf("%c ", p->data);
r = p;
p = NULL;
}
}
}
}
```