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

2019-11-17 05:04:24

字體：大中小

來源：轉載

供稿：網友

　　遞歸遍歷與非遞歸遍歷

　　前面寫過一些關于遞歸的文章，因為那時還沒有寫到樹，因此也舉不出更有說服力的例子，只是闡述了“遞歸是一種思想”，正像網友評價的，“一篇入門的文章”。但只要能能讓你建立“遞歸是一種思想”這個觀念，我的努力就沒有白費。

現在，講完了二叉搜索樹，終于有了能說明問題的例子了。按照前面提供的代碼，應該能調試通過下面的程序。

　　#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.　　
　　return0;
　　
　　}
　　

　　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
　

不知從哪聽來的觀點“遞歸的速度慢，為了提高速度，應該用棧消解遞歸”，證據就是斐波那契數列的計算，遺憾的是斐波那契數列的非遞歸算法是循環迭代，不是棧消解；假如他真的拿棧來模擬，他就會發現，其實用棧的更慢。
　　
　　我們來看看為什么。遞歸的實現是將參數壓棧，然后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++技術專題數據結構數據結構教程專題，或　　
　　這只能說明堆棧溢出了。你可以看到層次遍歷還能工作（由此類推，棧模擬的也能工作），但是遞歸的不能工作了。這是因為和總的內存空間比起來，堆棧空間是很少的，假如遞歸的層次過深，堆棧就溢出了。所以，假如你預先感到遞歸的層次可能過深，你就要考慮用棧來消解了。

　　
　　然而，假如你必須用遞歸，而遞歸的層次深到連堆棧都溢出了，那肯定是你的算法有問題，或者是那個程序根本不適合在PC上運行——運行起來就象死機了，這樣的程序誰敢用？所以說用棧模擬遞歸是有意義的，但是不大，因為很少用到。
　　
　　對于樹結構來說，假如沒有雙親指針，那么遍歷時的遞歸是必須的，與其搞什么棧消解不如添加一個雙親指針，這實際上也是用堆空間換取堆棧空間的一個方法，只是比ADT棧來得直接、高效罷了。
　　
　　綜上，遞歸的棧消解，實際上只能節省堆棧空間，不僅不會提高速度，相反卻會降低——天下哪有白吃的午餐，既省了堆棧空間還能提高速度。那些“棧消解遞歸能提高速度”的謠傳只是對“消除尾遞歸能提高速度”的不負責任的引申，然而一群人以訛傳訛，真就像是那么回事了，這就叫三人成虎。等我這時候再回過頭看教科書，竟然沒看見一本書上寫著“棧消解遞歸能提高速度”。真的，以前一直被誤導了，還不知道是被誰誤導的——書上根本就沒有寫。
　　
　　另外的結論

　　對比上面兩組結果，可以看到插入15000個節點比200000個節點消耗的時間還多，其原因就是插入數據的順序不同，從而導致了find的效率不同。隨機的順序大致能保證樹的左右子樹分布均勻，而有序的序列將使樹退化成單支的鏈表，從而使得O(logN)的時間復雜度變成了O(N)。同時，這也是為什么200000個節點的樹遞歸遍歷還能工作，而遞歸遍歷15000個節點的樹堆棧就溢出了——遞歸的每一層對應的節點太少了。
　　
　　為了提高find的效率，同時也是使樹的遞歸遍歷方法的使用更為寬泛，有必要研究如何能使樹的高度降低，這就是下面將要講到的平衡樹的來由。

更多內容請看C/C++技術專題數據結構數據結構教程專題，或

上一篇：開發精彩實例：窗體自動隱藏

下一篇：C語言中的三大定律