演算法中遞歸樹

Ⅰ 演算法導論 4-3 遞歸式 T(n)=2T(n/2)+n/lgn的復雜度求解

     在閱讀演算法導論第四章的時候，求解一些遞歸式的復雜度時，遇到了一些問題，因此將思路分享一下。

     首先對於可以用主方法求解的形式，這里不再說明，符合主方法的三種情況只要套用公式即可得到正確答案。關於主方法使用遞歸樹法進行證明，演算法導論上已經解釋的很詳細，感興趣可以參考一下散汪咐。

    在練習題 4.6-2 中提到了    ， 其中   ，要求證明主遞歸式的的解為  

    以   為例，很明顯不符合主方法的條件，因為第三章講到過  ，那麼可以考慮使用遞歸樹法，進行求解，然後再使用代入法進行數學歸納法的證明。

    首先遞歸樹高度為  （書中  以2為底，而不是10），葉節點數量為  ，即數量為n，每個葉節點復雜度為  ，因此葉節點總的復雜度為 

    然後計算中間節點包括根陵雹節點的復雜度，每一層有   個子節點

    

    接下來計算等差數列之和即可

              

        

即   

總的復雜度 

     因此可以很清楚的看到，由於遞歸樹的每層代價類似，最後結果多出來的   可以認為樹的總層數進行累加的結果。

    下面使用代入法驗證該結論，由於證明漸近上界與證明漸近下界的過程類似，因此只證明上界。

    設 

    則，

得證，其中 

    在思考題 4-3中 有類似   形式的遞歸式存在，其解為  ，有些解答認為是   實際上並不準確。

    同樣這種形式也不符合主方法的條件，同樣使用遞歸樹法進行近似的求解，然後再使用代入法證明答案的正確性。

    在計算這個遞歸式需要使用一些調和級數的知識，在算沖純法導論的附錄A中有公式 A.7，調和級數求和的證明需要使用到積分的定理，這里就不贅述了。

    同樣，首先計算葉節點的復雜度，同上 葉節點數量為  ，即每個葉節點復雜度為  ，總的復雜度為 

    接下來計算中間節點包括根節點的復雜度，同上，一共有  層，各層之和為

        

這里的累加項不再是一個等比數列，而是一個調和級數，即為

所以可以看出進行多出一次對數運算的原因在於分數的累加，因此總的復雜度 

同樣，下面使用代入法證明結果的正確性，因為證明步驟類似，這里也只證明漸近上界為  , 設 ，所以有

下面證明  ，為了證明的簡便，我們假設n為2的冪次，即  ，則

對於極限  ，那麼有

於是，得證  

Ⅱ 先序遍歷二叉樹的遞歸演算法怎樣理解

二叉樹的結點結構是:
1、根結點（存放結點數據）
2、左子樹指針
3、右子樹指計
對二叉樹的遍歷就是訪問各個結點中根結點里存放的數據。例如：
如果結點A有左結點B，右結點C，記作A(B,C)，不同結點我用"\"隔開。那麼有這樣一個(BitTree)二叉樹表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己畫出來，不然我後面白講了。
要想把所有的數據都訪問到則必需按照一定的原則，即當前結點的下一個結點是哪個結點。
無論是先、中還是後序演算法都是先將左結點視為下一個結點，當左結點不存在（即為空時）才將右結點視作下一個結點，如果右結點也不存在就返回當前結點的上層結點再向右訪問，如此類推。
於是對二叉樹的遍歷問題就被抽象成三個基本步驟:
1、訪問根結點。
2、訪問該點的所有左子樹。
3、訪問該點的所有右子樹。
先序遍歷的策略是按123的步驟執行，中序是按213來，後序則是231,它們之間的不同只是「訪問根結點」在這三個步驟中的位置。
看著你剛畫好的那個BitTree跟著我的思路走。在先序遍歷演算法PriorOrder中,先將BitTree的頭結點A傳進來，按步驟123的處理。123是抽象實現，記住所表達的思想，下面是具體實現。為了避免混亂用中文數字記錄步驟。
一、即是讀取結點A的數據內容A（此時A為當前函數處理結點)，將A的右結點C放入棧S中，S中的內容為S（C）[注意這一步是演算法的一個輔助，並不是先向右訪問,下同]，將左結點B傳給PriorOrder處理。此時讀取了A
二、讀取B的內容B（此時B為當前結點），將B的右結點E放入S中，S中的內容為S(C,E),將B的左結點D傳給PriorOrder處理。此時讀取了AB
三、D為當前結點，D的右為空沒有東西放入S，S中的內容仍為S(C,E)，D的左也為空，沒有訪問可訪問的。此時就從S中取出E(因為棧是先進後出的所以取的就是E，此時S中的內容為S(C),正好是上一層沒訪問過的右子樹)，將E傳給PriorOrder處理。此時讀取了AB D
四、E為當前結點，對於結點E類似的有S(C,G),讀取了ABDE,將F傳入PriorOrder
五、F為當前結點，右為空，左也為空，讀取了ABDEF,從棧中取出G傳給PriorOrder處理,S的內容為S(C);
六、類似的讀取了ABDEFG,從S中取出了C，傳給PriorOrder處理。此時S（）。
七、當前結點為C，從將C的右結點放入S，S中內容為S(H),C的左為空，從S取出H，將H傳給PriorOrder處理。此時S為S().於是就讀取了ABDEFGC
八，類似的讀取了ABDEFGCH
九，最後ABDEFGCHF
你再對照的書上的演算法想想，畫畫就應該能明白點。特別要理角的一點是為什麼用遞歸演算法時計算機能按這樣的方式是因為函數調用是「先調用，後執行完」，或者說「後調用，先執行完」。注意我加一個「完」字