程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++數據結構學習:二叉樹(3)

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

編輯:C++入門知識
  遞歸遍歷與非遞歸遍歷
  
     前面寫過一些關於遞歸的文章,因為那時還沒有寫到樹,因此也舉不出更有說服力的例子,只是闡述了“遞歸是一種思想”,正像網友評價的,“一篇入門的文章”。但只要能能讓你建立“遞歸是一種思想”這個觀念,我的努力就沒有白費。 <!-- 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++技術專題  數據結構  數據結構教程專題,或
 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved