前文傳送門：
「一本正經的聊資料結構（1）：時間複雜度」
「一本正經的聊資料結構（2）：數組與向量」
「一本正經的聊資料結構（3）：棧和隊列」
「一本正經的聊資料結構（4）：樹」
存儲結構
前面的内容我們介紹了樹和二叉樹的一些基礎概念，樹是資料結構中的重中之重，而二叉樹又是樹結構中的重點。
一直以來，包括我上學的年代，對樹和二叉樹的掌握都是模棱兩可，希望能通過這篇文章可以給各位講清楚這些疑難點。
二叉樹的存儲結構分為兩種，一種是順序存儲結構，另一種是鍊式存儲結構。
順序存儲結構
順序存儲結構就是使用一維數組存儲二叉樹中的節點，并且節點的存儲位置，就是數組的下标索引。
存儲在一維數組中的樣子如下：
這個示例是一個 完全二叉樹 的示例， 完全二叉樹 所對應的順序存儲剛好填滿整個數組，但是如果二叉樹不是 完全二叉樹 的時候，采用順序存儲又是怎樣的呢？
下圖中淺色結點表示結點不存在：
其中，
∧
表示數組中此位置沒有存儲結點。可以看到，使用順序存儲已經造成了空間浪費的情況。
如果是極端的右斜二叉樹，順序存儲情況會如何呢？
如下：
可以看到，在順序存儲結構下，極端的右斜二叉樹存儲造成了存儲空間的極大的浪費。
是以順序存儲方式一般适合完全二叉樹。
鍊式存儲結構
順序存儲結構有些無法滿足二叉樹的存儲，那麼我們考慮使用鍊式存儲結構。
二叉樹每個節點最多會有兩個孩子，是以，可以将結點資料結構定義為一個資料和兩個指針域。如下：
那麼剛才我們的那個完全二叉樹的存儲結構就可以這麼展現：
周遊
二叉樹的 周遊 是指從二叉樹的根結點出發，按照某種次序依次通路二叉樹中的所有結點，使得每個結點被通路一次，且僅被通路一次。
二叉樹的周遊依據通路次序可以分為四種方式：
- 前序周遊
- 中序周遊
- 後序周遊
- 層次周遊
簡單來講， 前序周遊 就是由根節點開始，當第一次到達結點時就輸出結點資料，按照先向左在向右的方向通路。
還是用這個完全二叉樹舉例子：
當他進行前序周遊的時候，通路順序如下：
從根結點出發，則第一次到達結點 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 。
後序周遊 就是從二叉樹的根結點出發，當第三次到達結點時就輸出結點資料，按照先向左在向右的方向通路。
後序周遊 的通路順序如下：
到達 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 。
小結
本文介紹了二叉樹的存儲結構以及四種周遊方式，各位看完了應該對二叉樹有一個初步的認知，如果不涉及一些變種的二叉樹，僅二叉樹的基礎内容而言，還是比較簡單的，希望各位同學能夠自己思考下，在大腦中能建立出一個二叉樹的模型，友善後面的學習。
參考
https://www.jianshu.com/p/bf73c8d50dc2
掃描二維碼關注「極客挖掘機」公衆号！作者：極客挖掘機
定期發表作者的思考：技術、産品、營運、自我提升等。
本文版權歸作者極客挖掘機和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果您覺得作者的文章對您有幫助，就來作者個人小站逛逛吧：
極客挖掘機