ght == Curr) //若Prev为NULL或是Curr的父节点
? ? ? ? {
? ? ? ? ? ? if(Curr->Left != NULL)
? ? ? ? ? ? ? ? Push(S, Curr->Left);
? ? ? ? ? ? else if(Curr->Right != NULL)
? ? ? ? ? ? ? ? Push(S, Curr->Right);
? ? ? ? }
? ? ? ? else if(Curr->Left == Prev)? ? //若Prev是Curr的左儿子
? ? ? ? {
? ? ? ? ? ? if(Curr->Right != NULL)
? ? ? ? ? ? ? ? Push(S, Curr->Right);
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? printf("%d\n", Curr->Data);? ? //访问当前节点
? ? ? ? ? ? Pop(S);? ? //访问后弹出
? ? ? ? }
? ? ? ? Prev = Curr;? ? //处理完当前节点后将Curr节点变为Prev节点
? ? }
}
4. 层序遍历
二叉树遍历的核心问题是二维结构的线性化。我们通过节点访问其左右儿子时，存在的问题是访问左儿子后，右儿子怎么访问。因此我们需要一个存储结构保存暂时不访问的节点。前面三种遍历方式的非递归实现，我们是通过堆栈来保存。事实上也可以通过队列来保存。
队列实现的基本思路：遍历从根节点开始，首先将根节点入队，然后执行循环：节点出队，访问（访问）根节点，将左儿子入队，将右儿子入队，直到队列为空停止。
这种遍历方式的结果是将二叉树从上到下，从左至右一层一层的遍历，即层序遍历，代码实现如下:
void LevelOrderTraversal(BinTree BT)
{
? ? BinTree T;
? ? Queue Q;? ? //声明一个队列
? ? if (BT == NULL)
? ? ? ? return;? ? ? ? ? ? ? ? //如果树为空，直接返回
? ? Q = CreatQueue(MAX_SIZE);? //创建并初始化队列
? ? AddQ(Q, BT);? ? ? ? ? ? ? ? //将根节点入队
? ? while (!IsEmpty(Q))
? ? {
? ? ? ? T = DeleteQ(Q);? ? //节点出队
? ? ? ? printf("%d\n", T->Data);? ? //访问出队的节点
? ? ? ? if (T->Left)? ? AddQ(Q, T->Left);? //若左儿子不为空，将其入队
? ? ? ? if (T->Right)? ? AddQ(Q, T->Right)? //若右儿子不为空，将其入队
? ? }
}