文档介绍：二叉树的非递归遍历
E G
①0(①
非递归后序遍历二叉树:
先访问左子树,再访问右子树,最后访问根节点。
设置一个栈。先将根节点的左节点全部进栈。出栈
个节点,将该节点的右孩子进栈,再将右孩子的
左节点全部进栈当一个节点的左、右孩子都被访
问过后再访问该节点,如此这般直到栈空为止。(判
断某节点的右孩子是否被访问,需要单独设置一个
指针跟踪刚刚访问的节点。在后序遍历中,某节点一
的右孩子节点一定刚好在该节点之前被访问)
DEFG
(
void PostorderTraverse(BiTree T, Status(* visit)(ElemType e)
BiTree pstack [10
int t
-1,si
BiTree root T
if(root NULL)
hile(root ! NULL)[
pStack [++topI
root
root->lchild
★害
NULL
t= pstack [top]
if(root->rchild== p)
visit(root->data)
七
root= root->rchild
S工
/**
)while(top
B
E G
①0(①
00
个栈,
可访问访问结点
的情况后出栈
A
B
E G
①0(①
将A根结点进栈。
此时p指向A的左
孩子B。
A
B
E G
A
将B进栈
此时p指向B的左
孩子D。
A
B
DO⑥
D
A
将D进栈
此时p指向D的左
孩子H。
A
B
D
BHOO O
A
将H进栈
此时p指向H的左
孩子,为NULL。
pTmp也为NUL。
A
B
D⑥
A
while(top=-1 & sign )
获取栈顶H,p指向H,由于H右孩子不存在,访问H,
H出栈。
遍历结果:此时,pmp指向已被访问的H结点。sgn置为已访问
A
B
D⑥
A
while(top =1&& sign)
获取栈顶D,p指向D,由于D右孩子存在,不访问D。
此时,把p指向D的右孩子1,pTmp仍指向已被访问
遍历结果:的H结点。sign置为0