---

在数据结构相关的书里，大家都学习了树的先序，中序，后序的递归遍历算法。实际上每种遍历方法都有其对应的非递归算法。下面就给出树的非递归算法。在非递归算法里，都用到了栈来保存中间结果。大家一定要注意在这些算法里面栈的使用方法。

 

#define  MAX  100

//二叉树前序遍历 递归 实现：

void preorder(btree *t)

{

 if(t)

 {

  printf(“%d”, t->data);

  preorder(t->left);

  preorder(t->right);

 }

}

//二叉树前序遍历 非递归 实现：

void preorder(btree *b)

{

     btree    *stack[MAX];

     int  top;

 

     if (b != NULL)

    {

     //栈初始化

         top = 1;

         stack[top] = b;

         while (top > 0)

        {

             //出栈

              p = stack[top];

              top--;

              //遍历根结点

              printf("%d", p->data);

              //右子树进栈

              if (p->right != NULL)

            {

                   top++;

                  stack[top] = p->right;

              }

              /左子树进栈

              if (p->left != NULL)

            {

                   top++;

                   stack[top] = p->left;

              }

         }

     }

}

//二叉树中序遍历 递归 实现：

void inorder(btree *t)

{

 if(t)

 {

  inorder(t->left);

  printf(“%d”, t->data);

  inorder(t->right);

 }

}

//二叉树中序遍历 非递归 实现：

void inorder(btree *b)

{

     btree    *stack[MAX], *p;

     int  top = 0;

 

     p = b;

     do

    {

     //遍历左子树

         while (p != NULL)

        {

              top++;

              stack[top] = p;

              p = p->left;

         }

         if (top > 0)

        {

             //遍历根结点

              p = stack[top];

              top--;

              printf("%d", p->data);

              //遍历右子树

              p = p->right;

         }

     } while (p != NULL && top != 0)

}

//二叉树后序遍历 递归 实现：

void postorder(btree *t)

{

 if(t)

 {

  postorder(t->left);

  postorder(t->right);

  printf(“%d”, t->data);

 }

}

//二叉树后序遍历 非递归 实现：

void postorder(btree *b)

{

     btree    *stack[MAX], *p;

     int tag[MAX], top = 0;

 

     p = b;

     do

    {

     //遍历左子树

         while (p != NULL)

        {

              top++;

              stack[top] = p;

              tag[top] = 0;

              p = p->left;

         }

         if (top > 0)

        {

              p = stack[top];

              //右子树遍历完成，所以遍历根结点

              if (tag[top] == 1)

              {

                   top--;

                   printf("%d", p->data);

              }

              //遍历右子树

              if (top > 0)

             {

                   p = p->right;

                   tag[top] = 1;

              }

         }

     } while (p != NULL && top != 0)

}

    在后序非递归遍历时，用了一个额外的tag标签数组，当tag为0时，表示为左子树。当tag为1时，表示右子树遍历完毕。