一本正經的聊數據結構（5）：二叉樹的存儲結構與遍歷
前文傳送門：
存儲結構
前面的內容我們介紹了樹和二叉樹的一些基礎概念，樹是數據結構中的重中之重，而二叉樹又是樹結構中的重點。
一直以來，包括我上學的年代，對樹和二叉樹的掌握都是模稜兩可，希望能通過這篇文章可以給各位講清楚這些疑難點。
二叉樹的存儲結構分為兩種，一種是順序存儲結構，另一種是鏈式存儲結構。
順序存儲結構
順序存儲結構就是使用一維數組存儲二叉樹中的節點，並且節點的存儲位置，就是數組的下標索引。
存儲在一維數組中的樣子如下：
這個示例是一個 完全二叉樹 的示例， 完全二叉樹 所對應的順序存儲剛好填滿整個數組，但是如果二叉樹不是 完全二叉樹 的時候，採用順序存儲又是怎樣的呢？
下圖中淺色結點表示結點不存在：
存儲在一維數組中的樣子如下：
其中， ∧ 表示數組中此位置沒有存儲結點。可以看到，使用順序存儲已經造成了空間浪費的情況。
如果是極端的右斜二叉樹，順序存儲情況會如何呢？
如下：
存儲在一維數組中的樣子如下：
可以看到，在順序存儲結構下，極端的右斜二叉樹存儲造成了存儲空間的極大的浪費。
所以順序存儲方式一般適合完全二叉樹。
鏈式存儲結構
順序存儲結構有些無法滿足二叉樹的存儲，那麼我們考慮使用鏈式存儲結構。
二叉樹每個節點最多會有兩個孩子，因此，可以將結點數據結構定義為一個數據和兩個指針域。如下：
那麼剛才我們的那個完全二叉樹的存儲結構就可以這麼展現：
遍歷
二叉樹的 遍歷 是指從二叉樹的根結點出發，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點被訪問一次，且僅被訪問一次。
二叉樹的遍歷依據訪問次序可以分為四種方式：
- 前序遍歷
- 中序遍歷
- 後序遍歷
- 層次遍歷
前序遍歷
簡單來講， 前序遍歷 就是由根節點開始，當第一次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。
還是用這個完全二叉樹舉例子：
當他進行前序遍歷的時候，訪問順序如下：
從根結點出發，則第一次到達結點 A ，故輸出 A ;
繼續向左訪問，第一次訪問結點 B ，故輸出 B ；
按照同樣規則，輸出 D ，輸出 H ；
當到達葉子結點H，返回到 D ，此時已經是第二次到達 D ，故不在輸出 D ，進而向 D 右子樹訪問， D 右子樹不為空，則訪問至 I ，第一次到達 I ，則輸出 I ；
I 為葉子結點，則返回到 D ， D 左右子樹已經訪問完畢，則返回到 B ，進而到 B 右子樹，第一次到達 E ，故輸出 E ；
向E左子樹，故輸出 J ；
按照同樣的訪問規則，繼續輸出 C 、 F 、 G 。
所以，這個完全二叉樹的前序遍歷結果為： ABDHIEJCFG 。
中序遍歷
中序遍歷 就是從二叉樹的根結點出發，當第二次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。
還是上面的完全二叉樹，訪問順序如下：
從根結點出發，則第一次到達結點 A ，不輸出 A ，繼續向左訪問，第一次訪問結點 B ，不輸出 B ；繼續到達 D ， H ；
到達 H ， H 左子樹為空，則返回到 H ，此時第二次訪問 H ，故輸出 H ；
H 右子樹為空，則返回至 D ，此時第二次到達 D ，故輸出 D ；
由 D 返回至 B ，第二次到達 B ，故輸出 B ；
按照同樣規則繼續訪問，輸出 J 、 E 、 A 、 F 、 C 、 G ；
所以，中序遍歷的結果為： HDIBJEAFCG 。
後序遍歷
後序遍歷 就是從二叉樹的根結點出發，當第三次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。
後序遍歷 的訪問順序如下：
從根結點出發，則第一次到達結點 A ，不輸出 A ，繼續向左訪問，第一次訪問結點 B ，不輸出 B ；繼續到達 D ， H ；
到達 H ， H 左子樹為空，則返回到 H ，此時第二次訪問 H ，不輸出 H ；
H 右子樹為空，則返回至 H ，此時第三次到達 H ，故輸出 H ；
由 H 返回至 D ，第二次到達 D ，不輸出 D ；
繼續訪問至 I ， I 左右子樹均為空，故第三次訪問 I 時，輸出 I ；
返回至 D ，此時第三次到達 D ，故輸出 D ；
按照同樣規則繼續訪問，輸出 J 、 E 、 B 、 F 、 G 、 C ， A ；
所以，後序遍歷的結果為： HIDJEBFGCA 。
層次遍歷
層次遍歷 就是按照樹的層次自上而下的遍歷二叉樹。
層次遍歷的訪問順序如下：
從根節點出發，第一個到達節點 A ，直接輸出 A ；
繼續向左訪問，到達節點 B ，輸出節點 B ，繼續訪問節點的右節點 C ，輸出節點 C ，此時，第二層訪問結束，繼續訪問第三層；
訪問節點 B 的左節點 D ，輸出 D ，繼續訪問節點 B 的右節點 E ，輸出節點 E ；
剩下依次訪問節點 F 、 G 、 H 、 I 、 J 。
所以層次遍歷的結果為： ABCDEFGHIJ 。
小結
本文介紹了二叉樹的存儲結構以及四種遍歷方式，各位看完了應該對二叉樹有一個初步的認知，如果不涉及一些變種的二叉樹，僅二叉樹的基礎內容而言，還是比較簡單的，希望各位同學能夠自己思考下，在大腦中能建立出一個二叉樹的模型，方便後面的學習。
參考
//www.jianshu.com/p/bf73c8d50dc2
