递归遍历与非递归遍历
前面写过一些关于递归的文章，因为那时还没有写到树，因此也举不出更有说服力的例子，只是阐述了“递归是一种思想”，正像网友评价的，“一篇入门的文章”。但只要能能让你建立“递归是一种思想”这个观念，我的努力就没有白费。现在，讲完了二叉搜索树，终于有了能说明问题的例子了。按照前面提供的代码，应该能调试通过下面的程序。
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <time.h>
#include "BSTree.h"
#include "Timer.h"
#define random(num) (rand() % (num))
#define randomize() srand((unsigned)time(NULL))
#define NODENUM 200000//node number
int data[NODENUM];
void zero(int &t) { t = 0; }
int main()
{
BSTree<int> a; Timer t; randomize(); int i;
for (i = 0; i < NODENUM; i++) data[i] = i;
for (i = 0; i < NODENUM; i++) swap(data[i], data[random(NODENUM)]);//random swap
t.start(); for (i = 0; i < NODENUM; i++) a.insert(data[i]);
cout << "Insert time: " << t.GetTime() << "\tNode number: " << NODENUM << endl;
t.start(); for (a.first(); a.get() != NULL; a.next()) a.get()->data = 0;
cout << "Non-Stack time: " << t.GetTime() << endl;
t.start(); a.LevelOrder(zero); cout << "LevlOrder time: " << t.GetTime() << endl;
t.start(); a.PreOrder(zero); cout << " PreOrder time: " << t.GetTime() << endl;
t.start(); a.InOrder(zero); cout << " InOrder time: " << t.GetTime() << endl;
t.start(); a.PostOrder(zero); cout << "PostOrder time: " << t.GetTime() << endl;
return 0;
}
以下是timer.h的内容
#ifndef Timer_H
#define Timer_H
#include <windows.h>
class Timer
{
public:
Timer() { QueryPerformanceFrequency(&Frequency); }
inline void start() { QueryPerformanceCounter(&timerB); }
inline double GetTime()
{
QueryPerformanceCounter(&timerE);
return (double)(timerE.QuadPart - timerB.QuadPart) / (double)Frequency.QuadPart * 1000.0;
}
private:
LARGE_INTEGER timerB, timerE, Frequency;
};
#endif
上面的程序中，层次遍历用到的是队列，这应该可以代表用栈消解递归的情况，在我的机器C500上运行的结果是：
Insert time: 868.818 Node number: 200000
Non-Stack time: 130.811
LevlOrder time: 148.438
PreOrder time: 125.47
InOrder time: 129.125
PostOrder time: 130.914
以上是VC6的release版的结果，时间单位是ms，不说明会有人认为是死机了，^_^。可以看出，递归遍历实际上并不慢，相反，更快一些，而debug版的结果是这样的：
Insert time: 1355.69 Node number: 200000
Non-Stack time: 207.086
LevlOrder time: 766.023
PreOrder time: 183.287
InOrder time: 179.835
PostOrder time: 190.674
递归遍历的速度是最快的
这恐怕是上面结果得出的最直接的结论。不知从哪听来的观点“递归的速度慢，为了提高速度，应该用栈消解递归”，证据就是斐波那契数列的计算，遗憾的是斐波那契数列的非递归算法是循环迭代，不是栈消解；如果他真的拿栈来模拟，他就会发现，其实用栈的更慢。
我们来看看为什么。递归的实现是将参数压栈，然后call自身，最后按层返回，一系列的动作是在堆栈上操作的，用的是push、pop、call、ret之类的指令。而用ADT栈来模拟递归调用，实现的还是上述指令的功能，不同的是那些指令对照的ADT实现可就不只是一条指令了。谁都明白模拟的执行效率肯定比真实的差，怎么会在这个问题上就犯糊涂了呢？
当然，你非要在visit函数中加入类似这样的istream file1(“input.txt”)，然后在用栈模拟的把这个放在循环的外面，最后你说，栈模拟的比递归的快，我也无话可说——曾经就见过一个人，http://www.csdn.net/Develop/Read_Article.asp?Id=18342将数据库连接放在visit函数里面，然后说递归的速度慢。
如果一个递归过程用非递归的方法实现后，速度提高了，那只是因为递归做了一些无用功。比如用循环消解的尾递归，是多了无用的压栈和出栈才使速度受损的；斐波那契数列计算的递归改循环迭代所带来的速度大幅提升，是因为改掉了重复计算的毛病。假使一个递归过程必须要用栈才能消解，那么，完全模拟后的结果根本就不会对速度有任何提升，只会减慢；如果你改完后速度提升了，那只证明你的递归函数写的有问题，例如多了许多重复操作——打开关闭文件、连接断开数据库，而这些完全可以放到递归外面。递归方法本身是简洁高效的，只是使用的人不注意使用方法。
这么看来，研究递归的栈消解好像是无用的，其实不然，用栈模拟递归还是有点意义的，只是并不大，下面将给出示例来说明。
栈模拟递归的好处是节省了堆栈
将上面的程序//node number那行的数值改为15000——不改没反应了别找我，将//random swap那行注释掉，运行debug版，耐心的等30秒，就会抛异常了，最后的输出结果是这样的：
Insert time: 27555.5 Node number: 15000
Non-Stack time: 16.858
LevlOrder time: 251.036
这只能说明堆栈溢出了。你可以看到层次遍历还能工作（由此类推，栈模拟的也能工作），但是递归的不能工作了。这是因为和总的内存空间比起来，堆栈空间是很少的，如果递归的层次过深，堆栈就溢出了。所以，如果你预先感到递归的层次可能过深，你就要考虑用栈来消解了。
然而，如果你必须用递归，而递归的层次深到连堆栈都溢出了，那肯定是你的算法有问题，或者是那个程序根本不适合在PC上运行——运行起来就象死机了，这样的程序谁敢用？所以说用栈模拟递归是有意义的，但是不大，因为很少用到。
对于树结构来说，如果没有双亲指针，那么遍历时的递归是必须的，与其搞什么栈消解不如添加一个双亲指针，这实际上也是用堆空间换取堆栈空间的一个方法，只是比ADT栈来得直接、高效罢了。
综上，递归的栈消解，实际上只能节省堆栈空间，不仅不会提高速度，相反却会降低——天下哪有白吃的午餐，既省了堆栈空间还能提高速度。那些“栈消解递归能提高速度”的谣传只是对“消除尾递归能提高速度”的不负责任的引申，然而一群人以讹传讹，真就像是那么回事了，这就叫三人成虎。等我这时候再回过头看教科书，竟然没看见一本书上写着“栈消解递归能提高速度”。真的，以前一直被误导了，还不知道是被谁误导的——书上根本就没有写。
另外的结论
对比上面两组结果，可以看到插入15000个节点比200000个节点消耗的时间还多，其原因就是插入数据的顺序不同，从而导致了find的效率不同。随机的顺序大致能保证树的左右子树分布均匀，而有序的序列将使树退化成单支的链表，从而使得O(logN)的时间复杂度变成了O(N)。同时，这也是为什么200000个节点的树递归遍历还能工作，而递归遍历15000个节点的树堆栈就溢出了——递归的每一层对应的节点太少了。
为了提高find的效率，同时也是使树的递归遍历方法的使用更为宽泛，有必要研究如何能使树的高度降低，这就是下面将要讲到的平衡树的来由。
