C++數據結構學習：二叉樹(3)

　　遞歸遍歷與非遞歸遍歷
　　
　　 　　前面寫過一些關於遞歸的文章，因為那時還沒有寫到樹，因此也舉不出更有說服力的例子，只是闡述了“遞歸是一種思想”，正像網友評價的，“一篇入門的文章”。但只要能能讓你建立“遞歸是一種思想”這個觀念，我的努力就沒有白費。 <!-- frame contents --> <!-- /frame contents --> 現在，講完了二叉搜索樹，終於有了能說明問題的例子了。按照前面提供的代碼，應該能調試通過下面的程序。
　　
　　 　　#include
　　
　　 　　usingnamespacestd;
　　
　　 　　#include
　　 　　
　　 　　#include
　　 　　
　　 　　#include"BSTree.h"
　　 　　
　　 　　#include"Timer.h"
　　 　　
　　 　　#definerandom(num)(rand()%(num))
　　 　　
　　 　　#definerandomize()srand((unsigned)time(NULL))
　　 　　
　　 　　#defineNODENUM200000//nodenumber
　　 　　
　　 　　intdata[NODENUM];
　　 　　
　　 　　voidzero(int&t){t=0;}
　　 　　
　　 　　intmain()
　　 　　
　　 　　{
　　 　　
　　 　　BSTreea;Timert;randomize();inti;
　　 　　
　　 　　for(i=0;i　　 　　
　　 　　for(i=0;i　　 　　
　　 　　t.start();for(i=0;i　　 　　
　　 　　cout<<"Inserttime:"<　　 　　
　　 　　t.start();for(a.first();a.get()!=NULL;a.next())a.get()->data=0;
　　 　　
　　 　　cout<<"Non-Stacktime:"<　　 　　
　　 　　t.start();a.LevelOrder(zero);cout<<"LevlOrdertime:"<　　 　　
　　 　　t.start();a.PreOrder(zero);cout<<"PreOrdertime:"<　　 　　
　　 　　t.start();a.InOrder(zero);cout<<"InOrdertime:"<　　 　　
　　 　　t.start();a.PostOrder(zero);cout<<"PostOrdertime:"<　　 　　
　　 　　return0;
　　 　　
　　 　　}
　　 　　
　　
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　以下是timer.h的內容
　　 　　
　　 　　#ifndefTimer_H
　　 　　
　　 　　#defineTimer_H
　　 　　
　　 　　#include
　　 　　
　　 　　classTimer
　　 　　
　　 　　{
　　 　　
　　 　　public:
　　 　　
　　 <!-- frame contents --> <!-- /frame contents --> 　　Timer(){QueryPerformanceFrequency(&Frequency);}
　　 　　
　　 　　inlinevoidstart(){QueryPerformanceCounter(&timerB);}
　　
　　 　　inlinedoubleGetTime()
　　 　　
　　 　　{
　　
　　 　　
　　 　　QueryPerformanceCounter(&timerE);
　　 　　
　　 　　return(double)(timerE.QuadPart-timerB.QuadPart)/(double)Frequency.QuadPart*1000.0;
　　
　　 　　}
　　 　　
　　 　　private:
　　 　　
　　 　　LARGE_INTEGERtimerB,timerE,Frequency;
　　
　　 　　};
　　 　　
　　 　　#endif
　　 　　
　　 　　上面的程序中，層次遍歷用到的是隊列，這應該可以代表用棧消解遞歸的情況，在我的機器C500上運行的結果是：
　　 　　
　　 　　Inserttime:868.818Nodenumber:200000
　　 　　
　　 　　Non-Stacktime:130.811
　　 　　
　　 　　LevlOrdertime:148.438
　　 　　
　　 　　PreOrdertime:125.47
　　 　　
　　 　　InOrdertime:129.125
　　 　　
　　 　　PostOrdertime:130.914
　　 　　
　　 　　以上是VC6的release版的結果，時間單位是ms，不說明會有人認為是死機了，^_^。可以看出，遞歸遍歷實際上並不慢，相反，更快一些，而debug版的結果是這樣的：
　　
　　 　　Inserttime:1355.69Nodenumber:200000
　　 　　
　　 　　Non-Stacktime:207.086
　　 　　
　　 　　LevlOrdertime:766.023
　　 　　
　　 　　PreOrdertime:183.287
　　 　　
　　 　　InOrdertime:179.835
　　 　　
　　 　　PostOrdertime:190.674
　　 　
　　
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　　遞歸遍歷的速度是最快的
　　
　　 　　這恐怕是上面結果得出的最直接的結論。 <!-- frame contents --> <!-- /frame contents --> 不知從哪聽來的觀點“遞歸的速度慢，為了提高速度，應該用棧消解遞歸”，證據就是斐波那契數列的計算，遺憾的是斐波那契數列的非遞歸算法是循環迭代，不是棧消解；假如他真的拿棧來模擬，他就會發現，其實用棧的更慢。
　　 　　
　　 　　我們來看看為什麼。遞歸的實現是將參數壓棧，然後call自身，最後按層返回，一系列的動作是在堆棧上操作的，用的是push、pop、call、ret之類的指令。而用ADT棧來模擬遞歸調用，實現的還是上述指令的功能，不同的是那些指令對照的ADT實現可就不只是一條指令了。誰都明白模擬的執行效率肯定比真實的差，怎麼會在這個問題上就犯糊塗了呢？
　　 　　
　　 　　當然，你非要在visit函數中加入類似這樣的istreamfile1(“input.txt”)，然後在用棧模擬的把這個放在循環的外面，最後你說，棧模擬的比遞歸的快，我也無話可說——曾經就見過一個人，http://www.csdn.net/Develop/Read_Article.ASP？Id=18342將數據庫連接放在visit函數裡面，然後說遞歸的速度慢。
　　 　　
　　 　　假如一個遞歸過程用非遞歸的方法實現後，速度提高了，那只是因為遞歸做了一些無用功。比如用循環消解的尾遞歸，是多了無用的壓棧和出棧才使速度受損的；斐波那契數列計算的遞歸改循環迭代所帶來的速度大幅提升，是因為改掉了重復計算的毛病。假使一個遞歸過程必須要用棧才能消解，那麼，完全模擬後的結果根本就不會對速度有任何提升，只會減慢；假如你改完後速度提升了，那只證實你的遞歸函數寫的有問題，例如多了許多重復操作——打開關閉文件、連接斷開數據庫，而這些完全可以放到遞歸外面。遞歸方法本身是簡潔高效的，只是使用的人不注重使用方法。
　　 　　
　　 　　這麼看來，研究遞歸的棧消解似乎是無用的，其實不然，用棧模擬遞歸還是有點意義的，只是並不大，下面將給出示例來說明。
　　 　　
　　 　　棧模擬遞歸的好處是節省了堆棧
　　
　　 　　將上面的程序//nodenumber那行的數值改為15000——不改沒反應了別找我，將//randomswap那行注釋掉，運行debug版，耐心的等30秒，就會拋異常了，最後的輸出結果是這樣的：
　　 　　
　　 　　Inserttime:27555.5Nodenumber:15000
　　 　　
　　 　　Non-Stacktime:16.858
　　 　　
　　 　　LevlOrdertime:251.036
　　
　　
　　
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或 　　
　　 　　這只能說明堆棧溢出了。你可以看到層次遍歷還能工作（由此類推，棧模擬的也能工作），但是遞歸的不能工作了。這是因為和總的內存空間比起來，堆棧空間是很少的，假如遞歸的層次過深，堆棧就溢出了。所以，假如你預先感到遞歸的層次可能過深，你就要考慮用棧來消解了。 <!-- frame contents --> <!-- /frame contents -->
　　
　　 　　
　　 　　然而，假如你必須用遞歸，而遞歸的層次深到連堆棧都溢出了，那肯定是你的算法有問題，或者是那個程序根本不適合在PC上運行——運行起來就象死機了，這樣的程序誰敢用？所以說用棧模擬遞歸是有意義的，但是不大，因為很少用到。
　　 　　
　　 　　對於樹結構來說，假如沒有雙親指針，那麼遍歷時的遞歸是必須的，與其搞什麼棧消解不如添加一個雙親指針，這實際上也是用堆空間換取堆棧空間的一個方法，只是比ADT棧來得直接、高效罷了。
　　 　　
　　 　　綜上，遞歸的棧消解，實際上只能節省堆棧空間，不僅不會提高速度，相反卻會降低——天下哪有白吃的午餐，既省了堆棧空間還能提高速度。那些“棧消解遞歸能提高速度”的謠傳只是對“消除尾遞歸能提高速度”的不負責任的引申，然而一群人以訛傳訛，真就像是那麼回事了，這就叫三人成虎。等我這時候再回過頭看教科書，竟然沒看見一本書上寫著“棧消解遞歸能提高速度”。真的，以前一直被誤導了，還不知道是被誰誤導的——書上根本就沒有寫。
　　 　　
　　 　　另外的結論
　　
　　 　　對比上面兩組結果，可以看到插入15000個節點比200000個節點消耗的時間還多，其原因就是插入數據的順序不同，從而導致了find的效率不同。隨機的順序大致能保證樹的左右子樹分布均勻，而有序的序列將使樹退化成單支的鏈表，從而使得O(logN)的時間復雜度變成了O(N)。同時，這也是為什麼200000個節點的樹遞歸遍歷還能工作，而遞歸遍歷15000個節點的樹堆棧就溢出了——遞歸的每一層對應的節點太少了。
　　 　　
　　 　　為了提高find的效率，同時也是使樹的遞歸遍歷方法的使用更為寬泛，有必要研究如何能使樹的高度降低，這就是下面將要講到的平衡樹的來由。
　　
　　
　　 更多內容請看C/C++技術專題  數據結構  數據結構教程專題，或