## 非递归遍历二叉树的四种策略-先序、中序、后序和层序

先序遍历二叉树算法1

```// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status PreOrderTraverse(BiTree T, Status (Visit *)(TElemType e))
{
InitStack(S);
Push(S, T);
p = T;//或 GetTop(S, p);
while(!StackEmpty(S) && p)
{
while(p)
{
if(!Visit(p->data))
return ERROR;
Push(p->rchild);
p = p->lchild;
}
Pop(S, p);
}
DestroyStack(S);
return OK;
}```

```// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status PreOrderTraverse(BiTree T, Status (Visit *)(TelemType))
{
InitStack(S);
Push(S, T);
p = T;
while(!StackEmpty(S) && p)
{
while(p)
{
if(!Visit(p->data))
return ERROR;
Push(S, p);
p = p->lchild;
}
if(!StackEmpty(S))
{
Pop(S, p);
p = p->rchild;
}
}
DestroyStack(S);
return OK;
}
```

```// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status InOrderTraverse(BiTree T, Status (Visit *)(TelemType e))
{
InitStack(S);
Push(S, T)'
p = T;
while(!StackEmpty(S) && p)
{
while(p)
{
Push(S, p);
p = p ->lchild;
}
Pop(S, p);
if(!Visit(p->data))
return ERROR;
p = p->rchild;
}
DestroyStack(S);
return OK;
}```

```// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status PostOrderTraverse(BiTree T, Status (Visit *)(TelemType e))
{
InitStack(S);
Push(S, T);
p = T;
while(!StackEmpty(S) && p)
{
if(p)
{／／一直走到最左下的结点
Push(S, p);
p = p->lchild;
}
else
{//p为NULL时
GetTop(S, p);
if(p->rchild && p->rchild != r)
{//p有右孩子或p的右孩子不是刚刚被访问的
p = p->rchild;
Push(S, p);
p = p->lchild;
}
else
{//p无右孩子或p右孩子刚刚被访问过时
Pop(S, p);
Visit(p->data);
r = p;
p = NULL;
}
}
}
DestroyStack(S);
return OK;
}```

```// Copyright (c) 2009, ALex ZhonG. All rights reserved.

Status LevelOrderTraverse(BiTree T, Status (Visit *)(TelemType e))
{
InitQueue(Q);
p = T;
if(p)
{
if(!Visit(p->data)
return ERROR;
EnQueue(Q, p->lchild);
EnQueue(Q, p->rchild);
while(Q)
{
DeQueue(Q, p);
if(!Visit(p->data))
return ERROR;
if(p->lchild)
EnQueue(Q, p->lchild);
if(p->rchild)
EnQueue(Q, p->rchild);
}
}
return OK;
}```

ALex ZhonG