加關注可以第一時間接收數據結構系列文章，覺得不錯可以轉發和點贊，謝謝支持
前面我們講的都是線性表結構，棧、隊列等等。今天我們講一種非線性表結構，樹。樹這種數據結構比線性表的數據結構要複雜得多，內容也比較多，所以我會分四節來講解。
我反覆強調過，帶著問題學習，是最有效的學習方式之一，所以在正式的內容開始之前，我還是給你出一道思考題：二叉樹有哪幾種存儲方式？什麼樣的二叉樹適合用數組來存儲？
帶著這些問題，我們就來學習今天的內容，樹！
樹（Tree）
我們首先來看，什麼是“樹”？再完備的定義，都沒有圖直觀。所以我在圖中畫了幾棵“樹”。你來看看，這些“樹”都有什麼特徵？
你有沒有發現，“樹”這種數據結構真的很像我們現實生活中的“樹”，這裡面每個元素我們叫作“節點”；用來連線相鄰節點之間的關係，我們叫作“父子關係”。
比如下面這幅圖，A 節點就是 B 節點的父節點，B 節點是 A 節點的子節點。B、C、D 這三個節點的父節點是同一個節點，所以它們之間互稱為兄弟節點。我們把沒有父節點的節點叫作根節點，也就是圖中的節點 E。我們把沒有子節點的節點叫作葉子節點或者葉節點，比如圖中的 G、H、I、J、K、L 都是葉子節點。
除此之外，關於“樹”，還有三個比較相似的概念：高度（Height）、深度（Depth）、層（Level）。它們的定義是這樣的：
這三個概念的定義比較容易混淆，描述起來也比較空洞。我舉個例子說明一下，你一看應該就能明白。
記這幾個概念，我還有一個小竅門，就是類比“高度”“深度”“層”這幾個名詞在生活中的含義。
在我們的生活中，“高度”這個概念，其實就是從下往上度量，比如我們要度量第 10 層樓的高度、第 13 層樓的高度，起點都是地面。所以，樹這種數據結構的高度也是一樣，從最底層開始計數，並且計數的起點是 0。
“深度”這個概念在生活中是從上往下度量的，比如水中魚的深度，是從水平面開始度量的。所以，樹這種數據結構的深度也是類似的，從根結點開始度量，並且計數起點也是 0。
“層數”跟深度的計算類似，不過，計數起點是 1，也就是說根節點的位於第 1 層。
二叉樹（Binary Tree）
樹結構多種多樣，不過我們最常用還是二叉樹。
二叉樹，顧名思義，每個節點最多有兩個“叉”，也就是兩個子節點，分別是左子節點和右子節點。不過，二叉樹並不要求每個節點都有兩個子節點，有的節點只有左子節點，有的節點只有右子節點。我畫的這幾個都是二叉樹。以此類推，你可以想象一下四叉樹、八叉樹長什麼樣子。
這個圖裡面，有兩個比較特殊的二叉樹，分別是編號 2 和編號 3 這兩個。
其中，編號 2 的二叉樹中，葉子節點全都在最底層，除了葉子節點之外，每個節點都有左右兩個子節點，這種二叉樹就叫作滿二叉樹。
編號 3 的二叉樹中，葉子節點都在最底下兩層，最後一層的葉子節點都靠左排列，並且除了最後一層，其他層的節點個數都要達到最大，這種二叉樹叫作完全二叉樹。
滿二叉樹很好理解，也很好識別，但是完全二叉樹，有的人可能就分不清了。我畫了幾個完全二叉樹和非完全二叉樹的例子，你可以對比著看看。
你可能會說，滿二叉樹的特徵非常明顯，我們把它單獨拎出來講，這個可以理解。但是完全二叉樹的特徵不怎麼明顯啊，單從長相上來看，完全二叉樹並沒有特別特殊的地方啊，更像是“芸芸眾樹”中的一種。
那我們為什麼還要特意把它拎出來講呢？為什麼偏偏把最後一層的葉子節點靠左排列的叫完全二叉樹？如果靠右排列就不能叫完全二叉樹了嗎？這個定義的由來或者說目的在哪裡？
要理解完全二叉樹定義的由來，我們需要先了解，如何表示（或者存儲）一棵二叉樹？
想要存儲一棵二叉樹，我們有兩種方法，一種是基於指針或者引用的二叉鏈式存儲法，一種是基於數組的順序存儲法。
我們先來看比較簡單、直觀的鏈式存儲法。從圖中你應該可以很清楚地看到，每個節點有三個字段，其中一個存儲數據，另外兩個是指向左右子節點的指針。我們只要拎住根節點，就可以通過左右子節點的指針，把整棵樹都串起來。這種存儲方式我們比較常用。大部分二叉樹代碼都是通過這種結構來實現的。
我們再來看，基於數組的順序存儲法。我們把根節點存儲在下標 i = 1 的位置，那左子節點存儲在下標 2 * i = 2 的位置，右子節點存儲在 2 * i + 1 = 3 的位置。以此類推，B 節點的左子節點存儲在 2 * i = 2 * 2 = 4 的位置，右子節點存儲在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。
我來總結一下，如果節點 X 存儲在數組中下標為 i 的位置，下標為 2 * i 的位置存儲的就是左子節點，下標為 2 * i + 1 的位置存儲的就是右子節點。反過來，下標為 i/2 的位置存儲就是它的父節點。通過這種方式，我們只要知道根節點存儲的位置（一般情況下，為了方便計算子節點，根節點會存儲在下標為 1 的位置），這樣就可以通過下標計算，把整棵樹都串起來。
不過，我剛剛舉的例子是一棵完全二叉樹，所以僅僅“浪費”了一個下標為 0 的存儲位置。如果是非完全二叉樹，其實會浪費比較多的數組存儲空間。你可以看我舉的下面這個例子。
所以，如果某棵二叉樹是一棵完全二叉樹，那用數組存儲無疑是最節省內存的一種方式。因為數組的存儲方式並不需要像鏈式存儲法那樣，要存儲額外的左右子節點的指針。這也是為什麼完全二叉樹會單獨拎出來的原因，也是為什麼完全二叉樹要求最後一層的子節點都靠左的原因。
當我們講到堆和堆排序的時候，你會發現，堆其實就是一種完全二叉樹，最常用的存儲方式就是數組。
二叉樹的遍歷
前面我講了二叉樹的基本定義和存儲方法，現在我們來看二叉樹中非常重要的操作，二叉樹的遍歷。這也是非常常見的面試題。
如何將所有節點都遍歷打印出來呢？經典的方法有三種，前序遍歷、中序遍歷和後序遍歷。其中，前、中、後序，表示的是節點與它的左右子樹節點遍歷打印的先後順序。
- 前序遍歷是指，對於樹中的任意節點來說，先打印這個節點，然後再打印它的左子樹，最後打印它的右子樹。
- 中序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它本身，最後打印它的右子樹。
- 後序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它的右子樹，最後打印這個節點本身。
實際上，二叉樹的前、中、後序遍歷就是一個遞歸的過程 。比如，前序遍歷，其實就是先打印根節點，然後再遞歸地打印左子樹，最後遞歸地打印右子樹。
寫遞歸代碼的關鍵，就是看能不能寫出遞推公式，而寫遞推公式的關鍵就是，如果要解決問題 A，就假設子問題 B、C 已經解決，然後再來看如何利用 B、C 來解決 A。所以，我們可以把前、中、後序遍歷的遞推公式都寫出來。
前序遍歷的遞推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍歷的遞推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
後序遍歷的遞推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
有了遞推公式，代碼寫起來就簡單多了。這三種遍歷方式的代碼，我都寫出來了，你可以看看。
1
void preOrder(Node* root) {
2
if (root == null) return;
3
print root // 此處為偽代碼，表示打印 root 節點
4
preOrder(root->left);
5
preOrder(root->right);
6
}
7
8
void inOrder(Node* root) {
9
if (root == null) return;
10
inOrder(root->left);
11
print root // 此處為偽代碼，表示打印 root 節點
12
inOrder(root->right);
13
}
14
15
void postOrder(Node* root) {
16
if (root == null) return;
17
postOrder(root->left);
18
postOrder(root->right);
19
print root // 此處為偽代碼，表示打印 root 節點
20
}
二叉樹的前、中、後序遍歷的遞歸實現是不是很簡單？你知道二叉樹遍歷的時間複雜度是多少嗎？我們一起來看看。
從我前面畫的前、中、後序遍歷的順序圖，可以看出來，每個節點最多會被訪問兩次，所以遍歷操作的時間複雜度，跟節點的個數 n 成正比，也就是說二叉樹遍歷的時間複雜度是 O(n)。
解答開篇 & 內容小結
今天，我講了一種非線性表數據結構，樹。關於樹，有幾個比較常用的概念你需要掌握，那就是：根節點、葉子節點、父節點、子節點、兄弟節點，還有節點的高度、深度、層數，以及樹的高度。
我們平時最常用的樹就是二叉樹。二叉樹的每個節點最多有兩個子節點，分別是左子節點和右子節點。二叉樹中，有兩種比較特殊的樹，分別是滿二叉樹和完全二叉樹。滿二叉樹又是完全二叉樹的一種特殊情況。
二叉樹既可以用鏈式存儲，也可以用數組順序存儲。數組順序存儲的方式比較適合完全二叉樹，其他類型的二叉樹用數組存儲會比較浪費存儲空間。除此之外，二叉樹裡非常重要的操作就是前、中、後序遍歷操作，遍歷的時間複雜度是 O(n)，你需要理解並能用遞歸代碼來實現。
閱讀更多 xiuxiuing 的文章
