转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098283597120/
对于通常的尾递归很容易转换成循环。通过手工模拟我们基本上就可以确定如何进行转换。实际上尾递归的转换也可以看成是下面这种模式的特殊情况，在这种模式下，尾递归只是一个这样的递归树。
递归向非递归的转化，最简单的方法就是利用栈。但是对于比较复杂的递归转换起来即使利用栈也比较困难，所以试图寻找一种容易理解的递归向非递归转换的一般模式，通过这种模式可以很容易的写出非递归形式。以前的算法书籍，比如<<算法引论>>对这个问题有专门的介绍。因为一方面栈的空间是比较小的，这样递归有可能导致栈溢出；另一方面有些老的程序语言，并不支持递归。这样就有非递归化的需求。但是之前看到的一些非递归化的方法有些形式化，也不容易记忆和理解。所以这里试图建立一种更近直白容易理解的非递归化方法。
实际上在<<算法导论>>里，关于递归复杂度的分析方法中，有一个是通过递归调用树来进行计算的。也就是说递归调用的整个过程是可以用一棵树表示出来的，这样一课树画出来之后，只要再确定一个遍历顺序就可以了。可以看到，递归的顺序实际上就是dfs的遍历顺序，所以我们只要可以用迭代实现dfs，然后将它应用到递归调用树上，就可以将递归程序用迭代表达出来了。
二叉树的各种遍历是我们最经常见到的递归程序，当然很多题目也是要求实现后序，中序或者前序的非递归遍历。可以看到，递归程序就是在这样的一棵树中遍历，当然散落在递归调用间的处理程序，实际上也可以标在递归树的边上，也就是说，只要我们把递归画成一棵树，然后把递归程序里面的除了递归调用之外的代码加到相应的路径处，然后在用dfs遍历时，在经过相应的边时，加上相应的处理程序就可以了。这样就把递归程序，与递归树建立其了对应关系。
其中包含了两个步骤：
一.画出递归树
二.将额外的处理代码加入递归树中相对应的位置，从下图中可以看到递归程序中的1 2 3 4以及与递归树中对应的1 2 3 4的位置。(我们只画出来了根节点的对应部分，实际上所有节点都具有根节点的形式)
看下面的程序和二叉树
void preorder(node * root){
//1
if(root == NULL) return;
printf("%d ",root -> key);
preorder(root -> left);
//2
//3
preorder(root -> right);
//4
}
下面再来看dfs的非递归程序是如何实现的，实际上使用了一个隐式栈。这里我们定义三种节点：活结点，死结点，待扩展节点。
从图中来看，绿色的代表活结点，红色的代表死结点，剩下的代表未访问节点，待扩展节点则代表当前处理的节点即栈顶节点。在整个处理过程中，栈中保存的是所有的活结点，而活结点实际上就是当前位置到根节点的路径上的所有节点。如果当前节点还有扩展节点，就把它压入栈，然后再以当前节点为扩展节点，否则该节点就是死结点，将它pop出栈即可。dfs的迭代的一般模式如下：（引自王晓东 <<算法设计与分析>> 第5章回溯法）
void iterative_Backtrack(){
int t = 1;
while(t > 0){//如果栈未空
//则扩展当前栈顶节点
if(f(t) <= g(t)) //f[t],g[t]可以看成是栈里第t个元素代表的那个节点未搜索过的起始节点和终止节点编号
for(int i = f(t) ; i <= g(t) ; i++){ //->>>>实际上应该改为while(f(t) <= g(t))
x[t] = h(i);//将栈顶元素设为h[i],当然还有些需要做的工作没有写出来，需要修改f(t)和h(t)的内容
if(constraint(t) && bound(t)){//如果可行
if(solution(t)) output(t);//如果是解则直接输出
else t++; //否则继续扩展，
}
//虽然是个for循环，但是实际上当前节点只扩展了一个节点，之后该扩展节点又变成了当前扩展节点，
//t++正是带来了这样的影响，在下一个for循环中，当然实际上这段代码还有些问题。
}//end of for
else t–;//如果不存在扩展节点，则将当前元素出栈，称为死结点
}//end of while
}//end of func
分析上面的程序，实际上模式很简单：
初始我们可以把根节点压栈。
之后开始迭代。迭代中，我们把栈顶节点作为待扩展节点，然后我们看栈顶节点应该扩展那个节点了，这里需要一个数组来记录栈中节点已经扩展到哪个节点了，也就是里面的f数组。如果栈顶节点还有可扩展节点，那么我们就把这个可扩展节点放到栈里(很明显这个过程中需要更新f[t]的值)，然后进行下一次的迭代。如果栈顶节点已经没有可扩展的节点了，说明以该节点为根的子树已经处理完毕，这样该节点就应该出栈，变成死结点了，然后开始下一次的迭代。如果栈中还有节点，就说明需要继续进行迭代，否则就终止。
下面我们将它应用到二叉树遍历中：
实际上下面的程序里，并没有建立用来保存栈中第t个元素的起始和终止扩展节点的f[],g[]数组，因为对于儿叉树来说，每个节点最多只有两个扩展节点，所以这里是通过直接判断确定当前节点该如何扩展的，也就是说下面程序的那些条件判断就代替了上面的dfs迭代中的那个for循环。
下面是后序遍历的非递归版本，可以看到我们在这里把printf操作，加到了所有的pop操作之后，这也正是后序访问的时机。
/*postorder*/
void non_recursive_stack_postorder(struct node * root){
struct node * temp,*last;
push(root);
while(!isempty()) {
//查看当前栈顶节点，也就是待扩展节点
temp = stack[top];
//如果左右孩子皆为空
if((temp->left == NULL && temp -> right == NULL)){
last = pop();
printf("%d ",last -> key);
///printf("%d ",temp -> key);
continue;
}
//如果是从左子树回溯来的，则应该扩展右孩子了
if(last == temp -> left){
///printf("%d ",temp -> key);
//如果右子树不为空
if(temp -> right != NULL){push(temp->right);continue;}
//如果右子树为空
else {last = pop() ; printf("%d ",last -> key);continue ; }
}
//如果是右子树回溯过来的，说明当前节点已经没有可扩展节点了，应该出栈变成死结点
if(last == temp -> right ){
last = pop();
printf("%d ",last -> key);
continue;
}
//如果栈顶节点不是回溯到达的，而是刚加入的节点，则应该从左子树开始扩展
if(temp -> left != NULL){
push(temp -> left);
//printf("%d ",temp -> left -> key);
continue;
}
//如果栈顶节点不是回溯到达的，而是刚加入的节点，但是左子树为空
if(temp -> right != NULL){
///printf("%d ",temp -> key);
push(temp -> right);
//printf("%d ",temp -> right -> key);
continue;
}
}
}
如果要改成前序，也很简单，只要把所有的print操作写到push操作前面即可。也就是图中的红色两句printf。
如果要修改成中序，观察程序可以看到，有三个可能的时机，一种是左子树为空，另一种是左右子树皆为空，最后一种是从左子树回溯过来的时候。也就是上面代码中对应的绿色三句,它们打印的就是中序遍历的结果。
从上面这个程序可以看成，我们只要正确的安排打印的顺序，就可以正确的实现前中后序的非递归遍历了。实际上我们观察前中后序的递归版本也可以看出，它们遍历的递归调用结构其实是一样的，不同的就在于节点打印的时机。
另外实际上也可以不采用上面的这种用栈+dfs的迭代实现的方法，比如前序可以简单的这样实现：
void non_recursive_stack_preorder(struct node * root){
struct node * temp;
push(root);
while(!isempty()){
temp = pop();
printf("%d ",temp -> key);
if(temp -> right != NULL)
push(temp -> right);
if(temp -> left != NULL)
push(temp -> left);
}
}
ps：
有的题目也有这样的要求，就是不让使用栈来实现二叉树的非递归遍历。实际上这样的题目通常是因为，树节点还有一个特殊的变量：指向父节点的指针。利用这个指针实际上就可以实现类似于栈的功能了。再结合我们的程序中的方法：就是比较上一个pop出来的节点与当前节点的左右孩子是否相等，我们就可以确定当前节点处在什么样的扩展状态。