二叉樹是一種非常重要的資料結構，很多其它資料結構都是基于二叉樹的基礎演變而來的。對于二叉樹，有前序、中序以及後序三種周遊方法。因為樹的定義本身就是遞歸定義，是以采用遞歸的方法去實作樹的三種周遊不僅容易了解而且代碼很簡潔。而對于樹的周遊若采用非遞歸的方法，就要采用棧去模拟實作。在三種周遊中，前序和中序周遊的非遞歸算法都很容易實作，非遞歸後序周遊實作起來相對來說要難一點
前序周遊按照“根結點-左孩子-右孩子”的順序進行通路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
根據前序周遊通路的順序，優先通路根結點，然後再分别通路左孩子和右孩子。
即對于任一結點，其可看做是根結點，是以可以直接通路，通路完之後，若其左孩子不為空，按相同規則通路它的左子樹；當通路其左子樹時，再通路它的右子樹。
從根節點開始，開始周遊，并輸出（先序周遊首先輸出根）
遞歸輸出直至最左（先序根後面輸出的是左孩子）
當到達最左節點的時候，通路右節點
是以其處理過程如下：
對于任一結點p：
通路結點p，并将結點p入棧;
判斷結點p的左孩子是否為空，若為空，則取棧頂結點并進行出棧操作，并将棧頂結點的右孩子置為目前的結點p，循環至1);若不為空，則将p的左孩子置為目前的結點p;
直到p為null并且棧為空，則周遊結束。
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
另外還有一種方法，如果我們把一顆樹當成一個圖，前序，中序和後序周遊都是深度優先周遊的特例。
而其前前序周遊與深度優先周遊最像，列印順序也一緻，是以前序周遊也可以用深度優先搜尋來實作
中序周遊按照“左孩子-根結點-右孩子”的順序進行通路。
根據中序周遊的順序，對于任一結點，優先通路其左孩子，而左孩子結點又可以看做一根結點，然後繼續通路其左孩子結點，直到遇到左孩子結點為空的結點才進行通路，然後按相同的規則通路其右子樹。
從根節點開始，開始周遊
遞歸輸出直至最左，然後輸出（中序先輸出左孩子，而中序周遊第一個輸出的是其最左葉子節點）
對于任一結點p，
若其左孩子不為空，則将p入棧并将p的左孩子置為目前的p，然後對目前結點p再進行相同的處理；
若其左孩子為空，則取棧頂元素并進行出棧操作，通路該棧頂結點，然後将目前的p置為棧頂結點的右孩子；
直到p為null并且棧為空則周遊結束
40
41
42
後序周遊按照“左孩子-右孩子-根結點”的順序進行通路。
後序周遊的非遞歸實作是三種周遊方式中最難的一種。因為在後序周遊中，要保證左孩子和右孩子都已被通路并且左孩子在右孩子前通路才能通路根結點，這就為流程的控制帶來了難題。下面介紹兩種思路。
43
44
45
46
47
48
49
50
51
52
第二種思路：要保證根結點在左孩子和右孩子通路之後才能通路，是以對于任一結點p，先将其入棧。如果p不存在左孩子和右孩子，則可以直接通路它；或者p存在左孩子或者右孩子，但是其左孩子和右孩子都已被通路過了，則同樣可以直接通路該結點。若非上述兩種情況，則将p的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被通路，左孩子和右孩子都在根結點前面被通路。
其實後序周遊中目前節點要是想被輸出, 要麼
其左右孩子均為null
其左孩子剛被輸出，而其右孩子為null
其右孩子剛被輸出
但是這裡有一個優化, 入棧時候, 先是根入棧， 然後是右孩子, 然後是左孩子,
是以當跟元素位于棧頂的時候, 其左右孩子必然已經彈出，即被通路并且輸出,
也就是說, 判斷目前節點是否需要輸出時，隻需要之前被輸出的節點pre是目前棧定節點cur的孩子就行
即後序周遊中目前棧頂元素要是想被輸出
其孩子（不論左右）剛被輸出即可
而且如果剛被輸出的節點是其左孩子，那麼我們可以确定其有孩子必為null，否則它後于父節點入棧，應該在父節點之前被彈出并且輸出
是以我們的輸出判斷可以改為
利用遞歸的方法，按層進行列印，我們把根節點當做第0層，之後層次依次增加
首先我們用遞歸的方式來列印某一層的資訊
如果我們要列印第n層，那麼就需要從根節點開始遞歸的周遊，當到達我們制定的層次時，就輸出。
列印第n層的遞歸函數如下
如果我們想要列印第2層，就直接調用如下的即可
當然我們也可以采用層次遞減的方式，level = n為希望遞歸的層次，而層次每深入一次，level遞減，當level=0時，則說明遞歸至第n層
能夠列印第n層的節點，那麼我們實作層次周遊就簡單了，循環調用遞歸每一層的節點即可
以上的方法可以很清楚的看出，存在重複通路的情況，就是第0層通路的次數最多，第1層次之。是以這個遞歸的方法不是很有效的方法，但是卻不需要消耗額外的空間
第一個嘗試，利用了兩個隊列，一個儲存本層的節點，另一個儲存下層的節點。周遊本層的節點，把其子代節點排入下層隊列。本層周遊完畢後，就可換行，并交換兩個隊列。
我們可以設定兩個隊列，想象一下隊列的特點，就是先進先出，首先把第0層儲存在一個隊列中，然後按節點通路，并把已經通路節點的左右孩子節點放在第二個隊列中，當第一個隊列中的所有節點都通路完成之後，交換兩個節點。這樣重複下去，知道所有層的節點都被通路，這樣做的代價就是空間複雜度有點高。
本實作使用deque而不是queue，因為deque才支援swap()操作。注意，swap()是o(1)的操作，實際上隻是交換指針。
這實作要用兩個循環(書上的實作也是)，并且用了兩個隊列。能夠隻用一個循環、一個隊列麼?
其實我們隻需要使用辨別能夠辨別出每層的結束即可，是以可以歸納為如下的方法
* 雙指針法，辨別每層的開始結點和結束節點
size方法，同雙指針法，辨別每層的節點數目
end辨別，在每層結束後，插入一個辨別（如null或者特殊節點）來表示結束
第三種方法就是設定雙指針，一個curr指向通路當層開始的節點，一個end指向通路當層結束節點的下一個位置
同樣類似的方式，這種方式就是用了兩個指針，分别表示每層的開始和結束。
相同的，我們也可以使用兩個size來表示目前隊列中父節點的個數和子節點的個數
轉載：http://blog.csdn.net/gatieme/article/details/51163010
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)