遞歸遍歷與非遞歸遍歷
前面寫過一些關(guān)于遞歸的文章，因?yàn)槟菚r(shí)還沒有寫到樹，因此也舉不出更有說服力的例子，只是闡述了“遞歸是一種思想”，正像網(wǎng)友評(píng)價(jià)的，“一篇入門的文章”。但只要能能讓你建立“遞歸是一種思想”這個(gè)觀念，我的努力就沒有白費(fèi)。現(xiàn)在，講完了二叉搜索樹，終于有了能說明問題的例子了。按照前面提供的代碼，應(yīng)該能調(diào)試通過下面的程序。

#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的內(nèi)容

#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

上面的程序中，層次遍歷用到的是隊(duì)列，這應(yīng)該可以代表用棧消解遞歸的情況，在我的機(jī)器C500上運(yùn)行的結(jié)果是：

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版的結(jié)果，時(shí)間單位是ms，不說明會(huì)有人認(rèn)為是死機(jī)了，^_^?？梢钥闯?，遞歸遍歷實(shí)際上并不慢，相反，更快一些，而debug版的結(jié)果是這樣的：

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

遞歸遍歷的速度是最快的
這恐怕是上面結(jié)果得出的最直接的結(jié)論。不知從哪聽來的觀點(diǎn)“遞歸的速度慢，為了提高速度，應(yīng)該用棧消解遞歸”，證據(jù)就是斐波那契數(shù)列的計(jì)算，遺憾的是斐波那契數(shù)列的非遞歸算法是循環(huán)迭代，不是棧消解；如果他真的拿棧來模擬，他就會(huì)發(fā)現(xiàn)，其實(shí)用棧的更慢。

我們來看看為什么。遞歸的實(shí)現(xiàn)是將參數(shù)壓棧，然后call自身，最后按層返回，一系列的動(dòng)作是在堆棧上操作的，用的是push、pop、call、ret之類的指令。而用ADT棧來模擬遞歸調(diào)用，實(shí)現(xiàn)的還是上述指令的功能，不同的是那些指令對(duì)照的ADT實(shí)現(xiàn)可就不只是一條指令了。誰都明白模擬的執(zhí)行效率肯定比真實(shí)的差，怎么會(huì)在這個(gè)問題上就犯糊涂了呢？

當(dāng)然，你非要在visit函數(shù)中加入類似這樣的istream file1(“input.txt”)，然后在用棧模擬的把這個(gè)放在循環(huán)的外面，最后你說，棧模擬的比遞歸的快，我也無話可說——曾經(jīng)就見過一個(gè)人，http://www.csdn.net/Develop/Read_Article.asp?Id=18342將數(shù)據(jù)庫連接放在visit函數(shù)里面，然后說遞歸的速度慢。

如果一個(gè)遞歸過程用非遞歸的方法實(shí)現(xiàn)后，速度提高了，那只是因?yàn)檫f歸做了一些無用功。比如用循環(huán)消解的尾遞歸，是多了無用的壓棧和出棧才使速度受損的；斐波那契數(shù)列計(jì)算的遞歸改循環(huán)迭代所帶來的速度大幅提升，是因?yàn)楦牡袅酥貜?fù)計(jì)算的毛病。假使一個(gè)遞歸過程必須要用棧才能消解，那么，完全模擬后的結(jié)果根本就不會(huì)對(duì)速度有任何提升，只會(huì)減慢；如果你改完后速度提升了，那只證明你的遞歸函數(shù)寫的有問題，例如多了許多重復(fù)操作——打開關(guān)閉文件、連接斷開數(shù)據(jù)庫，而這些完全可以放到遞歸外面。遞歸方法本身是簡(jiǎn)潔高效的，只是使用的人不注意使用方法。

這么看來，研究遞歸的棧消解好像是無用的，其實(shí)不然，用棧模擬遞歸還是有點(diǎn)意義的，只是并不大，下面將給出示例來說明。

棧模擬遞歸的好處是節(jié)省了堆棧
將上面的程序//node number那行的數(shù)值改為15000——不改沒反應(yīng)了別找我，將//random swap那行注釋掉，運(yùn)行debug版，耐心的等30秒，就會(huì)拋異常了，最后的輸出結(jié)果是這樣的：

Insert time: 27555.5    Node number: 15000

Non-Stack time: 16.858

LevlOrder time: 251.036

這只能說明堆棧溢出了。你可以看到層次遍歷還能工作（由此類推，棧模擬的也能工作），但是遞歸的不能工作了。這是因?yàn)楹涂偟膬?nèi)存空間比起來，堆?？臻g是很少的，如果遞歸的層次過深，堆棧就溢出了。所以，如果你預(yù)先感到遞歸的層次可能過深，你就要考慮用棧來消解了。

然而，如果你必須用遞歸，而遞歸的層次深到連堆棧都溢出了，那肯定是你的算法有問題，或者是那個(gè)程序根本不適合在PC上運(yùn)行——運(yùn)行起來就象死機(jī)了，這樣的程序誰敢用？所以說用棧模擬遞歸是有意義的，但是不大，因?yàn)楹苌儆玫健?br>
對(duì)于樹結(jié)構(gòu)來說，如果沒有雙親指針，那么遍歷時(shí)的遞歸是必須的，與其搞什么棧消解不如添加一個(gè)雙親指針，這實(shí)際上也是用堆空間換取堆棧空間的一個(gè)方法，只是比ADT棧來得直接、高效罷了。

綜上，遞歸的棧消解，實(shí)際上只能節(jié)省堆?？臻g，不僅不會(huì)提高速度，相反卻會(huì)降低——天下哪有白吃的午餐，既省了堆?？臻g還能提高速度。那些“棧消解遞歸能提高速度”的謠傳只是對(duì)“消除尾遞歸能提高速度”的不負(fù)責(zé)任的引申，然而一群人以訛傳訛，真就像是那么回事了，這就叫三人成虎。等我這時(shí)候再回過頭看教科書，竟然沒看見一本書上寫著“棧消解遞歸能提高速度”。真的，以前一直被誤導(dǎo)了，還不知道是被誰誤導(dǎo)的——書上根本就沒有寫。

另外的結(jié)論
對(duì)比上面兩組結(jié)果，可以看到插入15000個(gè)節(jié)點(diǎn)比200000個(gè)節(jié)點(diǎn)消耗的時(shí)間還多，其原因就是插入數(shù)據(jù)的順序不同，從而導(dǎo)致了find的效率不同。隨機(jī)的順序大致能保證樹的左右子樹分布均勻，而有序的序列將使樹退化成單支的鏈表，從而使得O(logN)的時(shí)間復(fù)雜度變成了O(N)。同時(shí)，這也是為什么200000個(gè)節(jié)點(diǎn)的樹遞歸遍歷還能工作，而遞歸遍歷15000個(gè)節(jié)點(diǎn)的樹堆棧就溢出了——遞歸的每一層對(duì)應(yīng)的節(jié)點(diǎn)太少了。

為了提高find的效率，同時(shí)也是使樹的遞歸遍歷方法的使用更為寬泛，有必要研究如何能使樹的高度降低，這就是下面將要講到的平衡樹的來由。