史上最简明易懂非递归遍历二叉树算法

巧若拙

遍历二叉树的递归函数是体现了算法之美的高妙算法，思路清晰，代码简洁，读之赏心悦目。代码如下：

[mw_shl_code=c,true]void PreOrderTraverse_R(BiTree BT)//采用递归方式先序遍历二叉树BT
{
       if(BT != NULL)
       {
              printf("%c", BT->data);//输出该结点（根结点）
              PreOrderTraverse_R(BT->lchild);  //遍历左子树
              PreOrderTraverse_R(BT->rchild);//遍历右子树
       }
}

void InOrderTraverse_R(BiTree BT)//采用递归方式中序遍历二叉树BT
{
       if(BT != NULL)
       {
              InOrderTraverse_R(BT->lchild);  //遍历左子树
              printf("%c", BT->data);//输出该结点（根结点）
              InOrderTraverse_R(BT->rchild);//遍历右子树
       }
}

void PostOrderTraverse_R(BiTree BT)//采用递归方式后序遍历二叉树BT
{
       if(BT != NULL)
       {
              PostOrderTraverse_R(BT->lchild);  //遍历左子树
              PostOrderTraverse_R(BT->rchild);//遍历右子树
              printf("%c", BT->data);//输出该结点（根结点）
       }
}
[/mw_shl_code]

相较之下，大部分流传的非递归遍历二叉树算法语言晦涩，面目可憎，虽然利用了栈数据结构来模拟递归遍历过程，但思路和表达形式上未能与递归算法对应起来，造成初学者理解上的困惑。如果能够将非递归算法和递归算法相互对应，则可大大方便初学者理解二者间的等效性。

我们知道，编译器在调用函数时会分配一个栈空间，以存储必要信息，如果该函数调用了别的函数，其栈空间会一直保留，直到该函数最后一条语句执行完毕，才会释放其栈空间。在模拟非递归算法的时候，我们需要手工分配和释放栈空间。

三种不同的遍历方式区别在于栈空间的释放时机和输出结点信息时机的不同：先序和中序遍历是在访问栈顶元素的右孩子（右子树）之前退栈，而后序遍历在访问右子树之后退栈；先序遍历是在某结点入栈时输出其信息，而中序和后序遍历是在该结点退栈时输出其信息。

       无论是递归算法还是非递归算法，都遵循上述规则，二者可以一一对应。图示如下：

SeanYuan

高深莫测啊！！！{:soso_e110:}