1、先序遍历的非递归实现
Staus PreOrderTraverse(BiTree T, (* Visit)(TElemType e))
{
InitStack(S);
p = T;
while(p || !StackEmpty( S ) )
{
/* if(p)
{
if ( !Visist(p->data) )
return ERROR;
Push(S, p); //只要存储根节点就行
p = p->lchild;
}
else //当左子树访问完了,退到子树根,开始访问右子树
{
Pop(S, p);
p = p->rchild;
}
*/
while( p != NULL)
{
Push(S, p);
visit(p->data);
p = p->lchild;
}
Pop(S, p);
p = p->rchild;
}
}
2、中序遍历的非递归实现
Status InOrderTraverse(BiTree T, (* Visit)(TElemType e)
{
InitStack(S); p = T;
while( p || !StackEmpty( S )
{
while(p)
{
Push(S, p);
p = p->lchild;
}
Pop(S, p);
if ( !Visit( p->data) )
return ERROR;
p = p->rchild;
}
return OK;
}
3、后序遍历的非递归实现
Status PostOrderTraverse(BiTree T, Status (* Vistit)*(TElemType e)
{
InitStack(S); p = T;
while (p || !StackEmpty( S ))
{
while (p) ////沿着左孩子方向走到最左下
{
Push(S, p);
p = p->child;
}
// Pop(S, p);
GetTop(S, p);
if (p->rchild == NULL || p->rchild == pre) //如果p没有右孩子或者其右孩子刚刚被访问过
{
if ( !Visit(p->data) )
return ERROR;
pre = p;
Pop(S, p);
p = NULL; //这时,不用对p的左子树再进行遍历了。
}
else
{
p = p->rchild;
}
}
return OK;
}
(jingxshi) |