【思路】
假设递归算法流程图：T是要遍历树的根指针，若T
!=
NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
void
PreOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
基于方法一，流程图如右，当型循环
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)){
while
(
T
!=
NULL
){
Visit(T->data)
;
Push(S,T);
T
=
T->lchild;
}
if(
!StackEmpty(S)
){
Pop(S,T);
T
=
T->rchild;
}
}
}
【算法2】
void
PreOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
基于方法二，流程图如右，当型循环
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)
){
while
(
T
!=
NULL
){
Visit(T->data);
Push(S,
T->rchild);
T
=
T->lchild;
}
if
(
!StackEmpty(S)
){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
【算法】
void
InOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
流程图如右，当型循环
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)
){
while
(
T
!=
NULL
){
Push(S,T);
T
=
T->lchild;
}
if(
!StackEmpty(S)
){
Pop(S,
T);
Visit(T->data);
T
=
T->rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
typedef
struct
stackElement{
Bitree
data;
char
tag;
}stackElemType;
【算法】
void
PostOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
流程图如右，当型循环
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)
){
while
(
T
!=
NULL
){
Push(S,T,0);
T
=
T->lchild;
}
while
(
!StackEmpty(S)
&&
GetTopTag(S)==1){
Pop(S,
T);
Visit(T->data);
}
if
(
!StackEmpty(S)
){
SetTopTag(S,
1);
//
设置栈顶标记
T
=
GetTopPointer(S);
//
取栈顶保存的指针
T
=
T->rchild;
}else
break;
}
}
