PreOrder(BiTree T) //先序非递归遍历二叉树
{
InitStack(S); //创建工作栈
Push(S,T);
while(!StackEmpty(S))
{
Pop(S,p); //出栈
Visit(p); //访问
if(p->rchild)
Push(S,p->rchild); //右子树入栈
if(p->lchild)
Push(S,p->lchild); //左子树入栈
}
}
InOrder(BiTree T) //中序非递归遍历二叉树
{
InitStack(S); //创建工作栈
Push(S,<T,0>); //根入栈，且置0标志此时不能访问
while(!StackEmpty(S))
{
Pop(S,<p,flag>); //出栈
if(flag==1)
Visit(p); //访问标志为1可以访问
else
{
if(p->rchild)
Push(S,<p->rchild,0>); //右子树入栈且置访问标志0
Push(S,<p,1>); //根入栈且置访问标志1
if(p->lchild)
Push(S,<p->lchild,0>); //左子树入栈且置访问标志0
}
}
}
PostOrder(BiTree T) //后序非递归遍历二叉树
{
InitStack(S); //创建工作栈
Push(S,<T,0>); //根入栈，且置i0标志此时不能访问
while(!StackEmpty(S))
{
Pop(S,<p,flag>); //出栈
if(flag==1)
Visit(p); //访问标志为1可以访问
else
{
Push(S,<p,1>); //根入栈且置访问标志1
if(p->rchild)
Push(S,<p->rchild,0>); //右子树入栈且置访问标志0
if(p->lchild)
Push(S,<p->lchild,0>); //左子树入栈且置访问标志0
}
}
}
LayerOrder(BiTree T) //层次遍历二叉树
{
InitQueue(Q); //创建工作队列
EnQueue(Q,T); //根入队
while(!QueueEmpty(Q))
{
DeQueue(Q,p); //出队
Visit(p); //访问
if(p->lchild)
EnQueue(Q,p->lchild); //左子树入队
if(p->rchild)
EnQueue(Q,p->rchild); //右子树入队
}
}
评论