编写的方法:根据树中结点的遍历规律及顺序直接写出其非递归算法。
先序非递归算法
【思路】
假设: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);
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
while
( T
!=
NULL
||
!
StackEmpty(S))
{
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
}