二叉树非递归遍历算法详解
巧若拙（欢迎转载，但请注明出处：http://blog.）

二叉树是一种很常见的非线性数据结构，它的应用非常广泛，有必要熟练掌握。二叉树的二叉链表存储表示如下：
typedef char ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode;

typedef struct BiTNode *BiTree;

二叉树的递归算法很容易实现，而且简明易懂，但非递归算法就不是那么好理解了。本文将结合代码详细解释遍历二叉树的三种不同方式。
采用非递归方式遍历二叉树，必须构造一个栈，利用栈后进先出的特点，按照一定顺序把各结点存入到栈中。由于访问二叉树总是要从根结点开始的，所以根结点总是要第一个入栈，但根结点的出栈时机要根据遍历的方式来定。
    先来看前序遍历方式。前序遍历是先输出根结点，再输出左子树，最后输出右子树，故要在访问其孩子结点前，先将根结点出栈，并输出其数据域，然后根据栈后进先出的特点，先将其右孩子入栈（如果有），再将其左孩子入栈（如果有）。代码如下：
void PreOrderTraverse_S_1(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点，栈stack[]用来存储结点
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        stack[++top] = BT; //根结点入栈
        while (top >= 0)
        {
            p = stack[top--]; //栈顶元素出栈
            printf("%c", p->data);//输出该结点
            if (p->rchild != NULL) //如果该结点有右孩子，将右孩子入栈
            {
                 stack[++top] = p->rchild;
            }
            if (p->lchild != NULL) //如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈
            {
                 stack[++top] = p->lchild;
            }
        }
    }   
}

    函数PreOrderTraverse_S_1()充分利用了栈后进先出的特点，思路清晰，代码简洁。其实，我们还可以通过分析前序遍历二叉树的特征，先输出当前根结点数据，并将其入栈，再遍历左孩子，然后栈顶元素出栈，访问其右孩子。依此反复循环，直到输出所有结点（即栈空）为止。代码如下：
void PreOrderTraverse_S_2(BiTree BT) //采用非递归方式前序遍历二叉树BT
{
    BiTree p, stack[MAXSIZE];//p表示当前结点，栈stack[]用来存储结点
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        p = BT;
        while (p || top >= 0)
        {
            if (p != NULL) //先输出结点数据，再遍历左孩子
            {
                printf("%c", p->data);//输出该结点
                stack[++top] = p;
                p = p->lchild;
            }
            else
            {
                p = stack[top--]; //栈顶元素出栈
                p = p->rchild; //访问右孩子
            }
        }
    }
}

如果能充分理解函数PreOrderTraverse_S_2()，中序遍历二叉树是不难实现的，它与前序遍历的区别在于：它需要先遍历左子树，再输出根结点。所以代码只需要更改一下语句printf("%c", p->data);的位置即可。代码如下：

void InOrderTraverse_S(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点，栈stack[]用来存储结点
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        p = BT;
        while (p || top >= 0)
        {
            if (p != NULL) //不急着输出结点数据，先遍历左孩子
            {
                stack[++top] = p;
                p = p->lchild;
            }
            else
            {
                p = stack[top--]; //栈顶元素出栈
                printf("%c", p->data);//输出该结点
                p = p->rchild; //访问右孩子
            }
        }
    }
}

后序遍历二叉树算法的基本思路和前序遍历基本一样，也是利用栈后进先出的特点，先将右孩子入栈，再将左孩子入栈。但实现起来稍微复杂点，主要原因是要在访问了左，右子树之后才能输出根结点，需要访问根结点两次，而且必须在第二次访问根结点时才能将根结点退栈，所以需要一个辅助标记，记录根结点是否已经被访问过。代码如下：
void PostOrderTraverse_S_1(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点，栈stack[]用来存储结点
    int tag[MAXSIZE] = {0}; //用来标志栈顶元素是否初次被访问
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        stack[++top] = BT; //根结点入栈
        tag[top] = 0; //初次访问该结点
        
        while (top >= 0)
        {
            p = stack[top]; //取栈顶元素，但先不出栈
            if ((p->rchild == NULL && p->lchild == NULL) || tag[top] == 1)//是叶子结点或者该结点已经被访问过，直接退栈，并输出其数据
            {
                printf("%c", p->data);//输出该结点
                top--;    //退栈
            }
            else //先访问其子孙
            {
                tag[top] = 1; //表明该结点已经被访问过了，下次回来的时候直接退栈即可
                if (p->rchild != NULL) //如果该结点有右孩子，将右孩子入栈
                {
                     stack[++top] = p->rchild;
                     tag[top] = 0; //初次访问该结点
                }
                if (p->lchild != NULL) //如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈
                {
                     stack[++top] = p->lchild;
                     tag[top] = 0; //初次访问该结点
                }
            }
        }
    }   
}

类比函数PreOrderTraverse_S_1()和函数PreOrderTraverse_S_2()，我们也可以通过分析后序遍历二叉树的特征，得到新的算法实现。这里也需要借助一个辅助标记，用来记录栈顶元素的右孩子是否被访问过。我们先访问左孩子，然后取出栈顶元素赋值给p，但先不出栈，若栈顶元素右子树尚未访问，访问其右孩子；若已经访问过，则输出该结点，退栈，并让p指向NULL，以避免重复访问左孩子。代码如下：
void PostOrderTraverse_S_2(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点，栈stack[]用来存储结点
    int tag[MAXSIZE] = {0}; //用来标志栈顶元素的右孩子是否被访问过，0表示未访问，1表示已访问
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        p = BT;
        while (p || top >= 0)
        {
            if (p != NULL) //不急着输出结点数据，先访问左孩子
            {
                stack[++top] = p;
                tag[top] = 0; //表明该结点的右子树尚未访问
                p = p->lchild;
            }
            else
            {
                p = stack[top]; //取栈顶元素，但先不出栈
                if (tag[top] == 0) //若右子树尚未访问，访问其右孩子
                {
                    tag[top] = 1; //表明该结点的右子树已接受访问
                    p = p->rchild;
                }
                else
                {
                    printf("%c", p->data);//输出该结点
                    top--;    //退栈，并让p指向NULL，以避免重复访问左孩子
                    p = NULL;
                }
            }
        }
    }
}

代码总是很多，讲解总是很短。一段小小学习总结，占用您不少宝贵时间，如果有什么疑问，就请留言吧，我一定知无不言，言无不尽。

[ 本帖最后由 巧若拙 于 2014-10-3 21:10 编辑 ]