二叉樹基礎(chǔ)（上）：什么樣的二叉樹適合用數(shù)組存儲奸焙？
前面學(xué)習(xí)到的都是線性表結(jié)構(gòu)，棧徒溪，隊列等等忿偷。今天學(xué)習(xí)一種非線性表結(jié)構(gòu)：樹金顿。樹這種數(shù)據(jù)結(jié)構(gòu)比線性表的數(shù)據(jù)結(jié)構(gòu)要復(fù)雜的多臊泌，內(nèi)容也比較多，所以作者 @王爭 分四節(jié)來講解揍拆。
帶著問題學(xué)習(xí)渠概，是最有效的學(xué)習(xí)方式：二叉樹有哪幾種存儲方式？什么樣的二叉樹適合用數(shù)組來存儲嫂拴？
樹（Tree）
什么是 樹 呢播揪？看下圖中的樹，觀察這些 樹 都有什么特征筒狠？
上圖中的 樹 猪狈，與我們現(xiàn)實生活中的樹很相似，上圖中橙色的圓辩恼，就是 樹 中存放的元素雇庙，樹 中的每個元素谓形，我們叫作 節(jié)點；用來連線相鄰節(jié)點之間的關(guān)系疆前，我們叫做 父子關(guān)系寒跳。
除此之外，樹還有三個比較相似的概念：高度(Height)竹椒、深度(Depth)童太、層(Level)。
他們的定義是這樣的：
- 節(jié)點的高度 = 節(jié)點到葉子節(jié)點的
最長路徑（有幾條邊連接的） - 節(jié)點的深度 = 根節(jié)點到這個節(jié)點所經(jīng)歷的邊的個數(shù)
- 節(jié)點的層數(shù) = 節(jié)點的深度 + 1
- 樹的高度 = 根節(jié)點的高度
note：記憶方式胸完，高度是從下往上算（葉子節(jié)點到該節(jié)點）书释，深度是從上往下算（根節(jié)點到該節(jié)點）、高度和深度都是從 0 計數(shù)赊窥。層數(shù)是從 1 計數(shù)征冷，跟深度計算類似。
二叉樹（Binary Tree）
我們最常用的就是二叉樹誓琼。
二叉樹检激，每個節(jié)點最多只有兩個 叉，也就是兩個子節(jié)點腹侣，分別是左子節(jié)點和右子節(jié)點叔收。不過，二叉樹并不要求每個節(jié)點都有兩個子節(jié)點傲隶，有的結(jié)點只有左子節(jié)點饺律，有的節(jié)點只有右子節(jié)點。下圖均為二叉樹跺株，所以也可以猜想下四叉樹复濒、八叉樹長什么樣子。
上圖中乒省，編號 2 和編號 3 這兩個二叉樹是比較特殊的巧颈。
編號 2 的二叉樹，葉子節(jié)點全在最底層袖扛，除了葉子節(jié)點之外砸泛，每個節(jié)點都有左右兩個子節(jié)點，這種二叉樹就叫作滿二叉樹蛆封。
編號 3 的二叉樹中唇礁，葉子節(jié)點都在最底下兩層，最后一層的葉子節(jié)點都靠左排列（最后一層的節(jié)點之間不能有空隙惨篱，從左到右不能有空隙）盏筐，并且除了最后一層，其他層的節(jié)點個數(shù)都要達到最大砸讳，這種二叉樹叫作完全二叉樹琢融。
滿二叉樹的特征非常明顯楷拳，但是完全二叉樹的特征不怎么明顯啊，單從長相來看吏奸，完全二叉樹并沒有特別特殊的地方欢揖，那么完全二叉樹到底是如何定義的呢？
我們需要線了解奋蔚，如何表示（或者存儲）一個二叉樹她混？
想要存儲一棵二叉樹，我們有兩種方法泊碑，一種是基于指針或者引用的二叉鏈式存儲法坤按，一種是基于數(shù)組的順序存儲法。
鏈式存儲法
使用鏈表結(jié)構(gòu)馒过，每個節(jié)點有三個字段臭脓，數(shù)據(jù)、左節(jié)點指針腹忽、右節(jié)點指針来累。我們只要拎住根節(jié)點，就可以通過左右節(jié)點的指針窘奏，把整棵樹都穿起來嘹锁。這種存儲方式比較常用，大部分二叉樹代碼都是通過這種結(jié)構(gòu)來實現(xiàn)的着裹。
基于數(shù)組的循序存儲法
把根節(jié)點存儲在下標 i = 1 的位置领猾，把左子節(jié)點存儲在下標 2 * i = 2 的位置，右子節(jié)點存儲在 2 * i + 1 = 3 的位置骇扇。以此類推摔竿，B節(jié)點的左子節(jié)點存儲在 2 * i = 2 * 2 = 4 的位置，右子節(jié)點存儲在 2 * i + 1 = 2 * 2 + 1 = 5 的位置少孝。
所以继低，求一個節(jié)點的父節(jié)點：i/2 即可（一般情況下，為了方便計算子節(jié)點韭山，根節(jié)點都會存儲在下標為 1 的位置）郁季。
剛剛示例，其實就是一個完全二叉樹钱磅，我們可以發(fā)現(xiàn)，完全二叉樹會浪費下標為 0 的存儲位置似枕，如果是非完全二叉樹的話盖淡，其實會浪費更多的數(shù)組存儲空間。
所以凿歼，完全二叉樹無疑是最節(jié)省內(nèi)存的一種方式褪迟。因為數(shù)組的存儲方式并不需要像鏈式存儲法那樣冗恨，要存儲額外的左右子節(jié)點的指針。這也是為什么完全二叉樹會單獨拎出來的原因味赃，也是為什么完全二叉樹要求最后一層的子節(jié)點要從左到右排列的原因掀抹。
堆其實是一種完全二叉樹，最常用的存儲方式就是數(shù)組心俗。
二叉樹的遍歷
前面學(xué)習(xí)到二叉樹的基本定義與存儲方法傲武，現(xiàn)在來學(xué)習(xí)一下二叉樹非常重要的操作，二叉樹的遍歷城榛。（比較常見的面試題）
如何將所有節(jié)點都遍歷出來呢揪利？三種經(jīng)典方法：(前、中狠持、后序疟位，表示的是節(jié)點與它的左右子樹節(jié)點遍歷打印的先后順序)
- 前序遍歷
- 對于樹中任意節(jié)點來說，先打印這個節(jié)點喘垂，然后再打印它的左子樹甜刻，最后打印它的右子樹
- 中序遍歷
- 對于樹中任意節(jié)點來說，先打印它的左子樹正勒，然后再打印它本身罢吃，最后打印它的右子樹
- 后序遍歷
- 對于樹中任意節(jié)點來說，先打印它的左子樹昭齐，然后再打印它的右子樹尿招，最后打印這個節(jié)點本身
實際上，二叉樹的前阱驾、中就谜、后序遍歷就是一個遞歸的過程。
比如前序遍歷里覆，其實就是先打印根節(jié)點丧荐，然后再遞歸地打印左子樹，最后遞歸的打印右子樹喧枷。
前面學(xué)習(xí)遞歸的時候了解到虹统，遞歸代碼難不難寫主要是看能不能寫出遞推公式，而寫遞推公式的關(guān)鍵就是隧甚，如果要解決問題 A 车荔，就假設(shè)子問題 B、C 已經(jīng)解決戚扳，然后再來看如何利用 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
通過遞推公式來書寫遞歸代碼就簡單很多了蒂教，以下是代碼：
void preOrder(Node* root) {
if (root == null) return;
print root // 此處為偽代碼巍举，表示打印 root 節(jié)點
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此處為偽代碼，表示打印 root 節(jié)點
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此處為偽代碼凝垛，表示打印 root 節(jié)點
}
二叉樹的前懊悯、中、后序遍歷的遞歸實現(xiàn)是不是很簡單苔严？那么 二叉樹遍歷的時間復(fù)雜度是多少呢定枷？
從前面前、中届氢、后序遍歷的順序圖可以看到欠窒，每個節(jié)點最多會被訪問兩次，所以遍歷操作的時間復(fù)雜度退子，跟節(jié)點的個數(shù) n 成正比岖妄，也就是說二叉樹遍歷的時間復(fù)雜度是 ○(n)。
解答開篇 & 內(nèi)容小結(jié)
今天學(xué)習(xí)到一種非線性表數(shù)據(jù)結(jié)構(gòu)寂祥，樹荐虐。關(guān)于樹，需要掌握的概念：
- 節(jié)點名稱：根節(jié)點丸凭、葉子節(jié)點福扬、父節(jié)點、子節(jié)點惜犀、兄弟節(jié)點
- 概念：高度（從下往上數(shù)）铛碑、深度（從上往下數(shù)）、層數(shù)（深度加1）
我們平時最常用的樹就是二叉樹虽界。二叉樹的每個節(jié)點最多有兩個子節(jié)點汽烦，分別是左子節(jié)點和右子節(jié)點。
二叉樹中莉御，有兩種比較特殊的樹撇吞，分別是滿二叉樹和完全二叉樹。滿二叉樹又是完全二叉樹的一種特殊情況礁叔。
二叉樹既可以用鏈式存儲牍颈，也可以用數(shù)組順序存儲。
數(shù)組循序存儲的方式比較適合完全二叉樹晴圾，其他類型的二叉樹存儲會比較浪費存儲空間颂砸。
二叉樹里非常重要的操作就是前、中死姚、后序遍歷操作人乓，遍歷的時間復(fù)雜度是 ○(n)。
使用遞歸代碼來實現(xiàn)二叉樹的遍歷操作都毒。
課后思考
- 給定一組數(shù)據(jù)色罚，比如 1，3账劲，5戳护，6，9瀑焦，10腌且。求出可以構(gòu)建出多少種不同的二叉樹？
- 今天學(xué)習(xí)了三種二叉樹的遍歷方式榛瓮，前铺董、中、后序禀晓。還有一種遍歷方式叫做按層遍歷精续，如何實現(xiàn)呢？
