文档介绍：L
A
B
D
I
H
E
K
J
C
F
G
M
N
二叉树的非递归遍历
1
L
A
B
D
I
H
E
K
J
C
F
G
M
N
非递归中序遍历二叉树：
先访问左子树，再访问根节点，最后访问右子树。
设置一个栈，出栈即为访问节点。先将根节点的左节点全部进栈，然后出栈一个节点，访问。将该节点的右孩子节点进栈，再将右孩子节点的所有左节点全部进栈...如此这般直到栈空为止。
2
void InOrderTraverse(BiTree T, Status (* visit)(ElemType e))
{
BiTree pStack[100], p;
int top = -1;
if(T != NULL)
{
p = T;
while(top > -1 || p != NULL)
{
while(p != NULL)
{
pStack[++top] = p;
p = p->lchild;
}
if(top > -1)
{
p = pStack[top--];
visit(p->data);
p = p->rchild;
}
}
}
}
3
L
A
B
D
I
H
E
K
J
C
F
G
M
N
设置一个栈，出栈即为访问该结点。
4
L
A
B
D
I
H
E
K
J
C
F
G
M
N
先将根节点及其左孩子全部进栈。
p->
5
L
A
B
D
I
H
E
K
J
C
F
G
M
N
将根结点A进栈。
此时，p指向A的左孩子B。
A
p->
6
L
A
B
D
I
H
E
K
J
C
F
G
M
N
将根结点A的左孩子B进栈。
此时，p指向B的左孩子D。
A
B
p->
7
L
A
B
D
I
H
E
K
J
C
F
G
M
N
将B的左孩子D进栈。
此时，p指向D的左孩子H。
A
B
D
p->
8
L
A
B
D
I
H
E
K
J
C
F
G
M
N
将D的左孩子H进栈。
此时，p指向H的左孩子，为NULL。
A
B
D
H
9
L
A
B
D
I
H
E
K
J
C
F
G
M
N
H出栈，访问。
此时，p指向H的右孩子，为NULL。
A
B
D
遍历结果：
H
10