前面兩篇博客介紹了線性表的順序存儲與鏈式存儲以及對應的操作，并且還聊了棧與隊列的相關內容。本篇博客我們就繼續(xù)聊數(shù)據(jù)結構的相關東西，并且所涉及的相關Demo依然使用面向對象語言Swift來表示。本篇博客我們就來介紹樹結構的一種：二叉樹。在之前的博客中我們簡單的聊了一點樹的東西，樹結構的特點是除頭節(jié)點以外的節(jié)點只有一個前驅，但是可以有一個或者多個后繼。而二叉樹的特點是除頭結點外的其他節(jié)點只有一個前驅，節(jié)點的后繼不能超過2個。
本篇博客，我們只對二叉樹進行討論。在本篇博客中，我們對二叉樹進行創(chuàng)建，然后進行各種遍歷，最后將二叉樹進行線索化。在Demo實現(xiàn)之前，我們先對二叉樹的概念及其特性進行介紹，然后在給出具體的代碼實現(xiàn)。
一、二叉樹的特性
上面我們已經提到過，一個除頭結點外，每個節(jié)點只有一個前驅，有零到兩個后繼的樹即為二叉樹。在二叉樹中，一個節(jié)點可以有左節(jié)點或者左子樹，也可以有右節(jié)點或者右子樹。一些特殊的二叉樹，比如斜二叉樹、滿二叉樹、完全二叉樹等等就不做過多贅述了。說這么多，不如看一張圖來的直觀。下方就是一個典型的二叉樹。
了解二叉樹，理解其特性還是比較重要的?；诙鏄浔旧淼倪壿嫿Y構，下方是二叉樹這種數(shù)據(jù)結構所具備的特性。
-
特性1：在二叉樹的第i層上至多有2^(i-1)（i >= 1）個節(jié)點。
- 這一特性比較好理解，如果層數(shù)是從零開始數(shù)的話，那么低i層上的節(jié)點數(shù)就是2^i，因為二叉樹層與層之間的節(jié)點數(shù)是以2的指數(shù)冪進行增長的。如果根節(jié)點算是第0層的話，那么第n層的節(jié)點數(shù)就是2^n次冪。
-
特性2：深度為k的二叉樹至多有2^k-1（k>=1）個節(jié)點。
- 這一特性也是比較好理解的, 由數(shù)學上的遞加公式就可以很容易的推出來。由特性1易知每層最多有多少個節(jié)點，那么深度為k的話，說明一共有k層，那么共有節(jié)點數(shù)為：2^0 + 2^1 + 2^2 + 2^(k-1) = 2^k - 1。
- 特性3：
