前一篇讲解了如何编写二叉树结构的递归程序。尽管递归求解二叉树的方法和策略非常有效，但递归程序可能会产生不可接受的系统开销；因此，理解递归程序的机制，将递归程序转换为非递归程序的技能是非常重要的。 递归机制并不神秘。递归实际上就是特殊形式的普
前一篇讲解了如何编写二叉树结构的递归程序。尽管递归求解二叉树的方法和策略非常有效，但递归程序可能会产生不可接受的系统开销；因此，理解递归程序的机制，将递归程序转换为非递归程序的技能是非常重要的。
递归机制并不神秘。递归实际上就是特殊形式的普通函数调用，只是被调用函数与调用函数是完全相同的，这一点对初学者来说有些不太习惯。对于递归程序来说，最重要的就是保存调用函数中的局部变量状态(localvariable set)以及返回地址(returnaddress)，确定将要调用的函数参数(calledparameters)。在从被调用的函数中返回时，能够根据这些恢复到调用前的状态。
示例一： 阶乘函数
先用阶乘函数热热身。
fac(int n) : [1]
if (n == 0) { return 1; } [2]
else { int local = n; [3]
inttmp = fac(n-1); [4]
returnlocal * tmp; [5]
}
该递归函数比较简单。函数中含有需要保存的局部变量local ;调用参数是递减的整数n；只有一个返回出口，返回地址是[4]。用户栈包含局部变量和返回地址。虽然程序有点“罗嗦”，但有利于递归分析。
以 n= 2为例， 递归过程如下：
代码行 | 栈(返回地址,局部变量) | 将要调用的函数或行为 | 返回值 |
1 | fac (2) | ||
3-4 | (4,2) | fac (1) | |
3-4 | (4,2), (4,1) | fac (0) | |
2 | (4,2), (4,1) | 1 | |
4-5 | (4,2) | 返回至4，1出栈 | 1*1 |
4-5 | 返回至4，2出栈 | 2*1*1 |
经过分析，可以得到： A.若n> 0， 则将 n入栈， 将n-1传入fac()中，直到传入的参数为0为止；B.当n = 0时，返回1；C.从栈中取出返回地址及局部变量，并与返回值相乘得到结果。
int fac(int n)
{
if (n
while (n >0) { stack.push(n); n--;}
int result= 1; // n = 0时的返回值
while(!stack.isEmpty()) {
result*= stack.pop();
}
returnresult;
}
示例二：后序递归遍历
PostTravel(root){ [1]
if(root != null) { [2]
PostTravel(root->left); [3]
pause(); [4]
PostTravel(root->right); [5]
pause(); [6]
visit(root); [7]
pause(); [8]
} [9]
}
后序递归遍历的难度在于：有两个可能的返回出口。隐藏的局部变量为root。以基本的树结构：A（B，C）即根结点为A，左孩子为B，右孩子为C;递归过程如下：
代码行 | 栈（返回地址，局部变量） | 将要调用的函数或行为 |
1 | PostTravel (A) ； | |
2满足 | A入栈； | |
2-3 | (4,A) | PostTravel (B) ； |
2满足 | B入栈； | |
2-3 | (4,A), (4,B) | PostTravel(NULL) (B的左子树) |
2不满足 | 从9返回；栈非空，B出栈；返回至4； | |
4 | (4,A) | Root = B; B入栈 |
5 | (4,A), (6,B) | PostTravel(NULL) (B的右子树) |
2不满足 | 从9返回；栈非空，B出栈；返回至6； | |
6-8 | (4,A) | visit(B)；从9返回； 栈非空，A出栈；返回至4； |
4 | Root = A；A入栈 | |
5 | (6,A) | PostTravel (C) |
2满足 | C入栈； | |
2-3 | (6,A), (4,C) | PostTravel(NULL) (C的左子树) |
2 不满足 | 从9返回；栈非空，C出栈；返回至4； | |
4 | (6,A) | Root = C ; C入栈 |
5 | (6,A), (6,C) | PostTravel(NULL) (C的右子树 |
2不满足 | 从9返回；栈非空，C出栈；返回至6； | |
6-8 | (6,A) | visit(C)；从9返回； 栈非空，A出栈；返回至6； |
6-8 | visit(A)；从9返回。栈空；退出。 | |
虽然上述所示的数据流和控制流跟踪非常繁琐，但仍然能够从中获得一些有益的线索：1.系统从某一层递归调用返回时，会先进行出栈，取出返回地址，以确定将要返回的地址并继续执行；2.系统从某一层递归调用返回时，如果栈为空，那么，表明递归调用已经完成；3.如果有多个返回地址，则必须采取某种手段，标识将要返回到何处；4.二叉树的后序遍历结点顺序为：A-B-LeftNull-B-RightNull-B(打印)-A-C-LeftNull-C-RightNull-C(打印)-A(打印)；5.当访问二叉树的某结点A后，总是立即访问其父结点的右子树：若父结点的右子树已经访问（该结点A正是其父结点的右子树），则立即出栈其父结点并访问；若还没有访问，则访问其父结点的右子树。
实现程序如下：
Java(类goto语句)，——发现偶尔做点“坏事”还是蛮有成就感的，HOHO~。
像是经历了一场战斗，看来，二叉树的非递归遍历还是有点艰难的。不要紧，凡事多多练习就好了。至此，总结一下将递归程序转换为非递归函数的一些方法和技巧：1.用一些小例子来跟踪递归程序的执行，理解其机制和过程；2.挖掘一些关键的线索，这些线索对求解问题和终止程序可能会很有帮助；3.尝试着编写非递归程序，模拟递归程序的执行；4.优化非递归程序，使之更自然，更有效率。