前言：本篇文章只是記錄王爭的數(shù)據(jù)結(jié)構(gòu)與算法之美的學(xué)習(xí)筆記，寫下來能強(qiáng)迫自己系統(tǒng)的再過一遍颜骤，加深理解样悟。這門課
以實(shí)際開發(fā)中遇到的問題為例，引入解決問題涉及到的的數(shù)據(jù)結(jié)構(gòu)和算法，但不會講的太細(xì)遏匆，最好結(jié)合一本實(shí)體書進(jìn)行學(xué)習(xí)法挨。
1. 樹
1.1 樹的定義
樹有一個(gè)根節(jié)點(diǎn)，很多個(gè)子節(jié)點(diǎn)幅聘，如下圖所示：
1.2 樹中節(jié)點(diǎn)間的關(guān)系
節(jié)點(diǎn)之間有著不同的關(guān)系凡纳，比如下面圖中，A 是 B 的父節(jié)點(diǎn)帝蒿，B 是 A 的子節(jié)點(diǎn)荐糜，B C D 都是 A 的子節(jié)點(diǎn)，互稱為兄弟結(jié)點(diǎn)葛超。沒有父節(jié)點(diǎn)的節(jié)點(diǎn)就是根節(jié)點(diǎn)（E 節(jié)點(diǎn)）暴氏，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)叫做葉子節(jié)點(diǎn)或者葉節(jié)點(diǎn)，比如 G H I J K L绣张。
1.3 高度&深度&層
- 節(jié)點(diǎn)的高度 = 節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑（邊數(shù)）
- 節(jié)點(diǎn)的深度 = 根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)所經(jīng)歷的邊的個(gè)數(shù)
- 節(jié)點(diǎn)的層數(shù) = 節(jié)點(diǎn)的深度 + 1
- 樹的高度 = 根節(jié)點(diǎn)的高度
2. 二叉樹
2.1 二叉樹的分類
二叉樹使我們最常用的答渔，什么是二叉樹？就是一個(gè)節(jié)點(diǎn)下面侥涵，最多有兩個(gè)子節(jié)點(diǎn)沼撕，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，如下圖所示：
滿二叉樹（上圖 2 號樹）：
- 葉子結(jié)點(diǎn)全都在最底層
- 除了葉子節(jié)點(diǎn)外芜飘，每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)
- 滿二叉樹總的節(jié)點(diǎn)個(gè)數(shù) = 2^n - 1 (n 為樹的層數(shù))
完全二叉樹（上圖 3 號樹）：
- 葉子節(jié)點(diǎn)在最底下兩層
- 最后一層葉子節(jié)點(diǎn)從左到右中間無間隔
- 除了最后一層务豺，其他層節(jié)點(diǎn)數(shù)要達(dá)到最大
滿二叉樹屬于完全二叉樹，完全二叉樹并不一定是滿二叉樹燃箭。
2.2 二叉樹的存儲
有了二叉樹這種數(shù)據(jù)結(jié)構(gòu)冲呢，我們肯定需要考慮如何存儲。有兩種方法：
- 基于指針或者引用的二叉鏈?zhǔn)酱鎯Ψ?/li>
- 基于數(shù)組的順序存儲法
2.2.1 鏈?zhǔn)酱鎯?/h6>
其實(shí)跟鏈表的結(jié)點(diǎn)大同小異招狸，每個(gè)節(jié)點(diǎn)有三個(gè)字段：data存儲數(shù)據(jù)敬拓，left right 分別指向左右兩個(gè)子節(jié)點(diǎn)，這種方式比較常用裙戏，如下圖所示：
2.2.2 順序存儲
就是把根節(jié)點(diǎn)存儲在下標(biāo) i = 1 的位置乘凸，左子節(jié)點(diǎn)存儲在下標(biāo) 2 * i = 2 的位置，右子節(jié)點(diǎn)存儲在 2 * i + 1 = 3的位置累榜，以此類推营勤，如下圖所示，存儲的是完全二叉樹：
節(jié)點(diǎn)存儲在數(shù)組中下標(biāo)為 i 的位置壹罚，則其左子節(jié)點(diǎn)的下標(biāo)為 2 * i葛作，右子節(jié)點(diǎn)的下標(biāo)為 2 * i + 1，父節(jié)點(diǎn)下標(biāo)為 i / 2猖凛。
如果是非完全二叉樹赂蠢，如果用順序存儲的話會浪費(fèi)一些空間，還是用鏈?zhǔn)酱鎯Ρ容^合適辨泳，如下圖所示：
3. 二叉樹的遍歷
經(jīng)典的方法有三種：
- 前序遍歷：先打印這個(gè)節(jié)點(diǎn)虱岂，然后打印它的左子樹玖院，最后打印它的右子樹
- 中序遍歷：先打印節(jié)點(diǎn)的左子樹，然后打印這個(gè)節(jié)點(diǎn)第岖，最后打印它的右子樹
- 后序遍歷：先打印它的左子樹难菌，然后打印它的右子樹，最后打印這個(gè)節(jié)點(diǎn)
如下圖所示：
這三種遍歷其實(shí)就是一個(gè)遞歸的過程蔑滓，遞推公式如下：
前序遍歷的遞推公式：
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é)點(diǎn)
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此處為偽代碼，表示打印root節(jié)點(diǎn)
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此處為偽代碼烫饼，表示打印root節(jié)點(diǎn)
}
從前面的前猎塞、中、后序遍歷的順序圖杠纵，可以看出來荠耽，每個(gè)節(jié)點(diǎn)最多會被訪問兩次，所以遍歷操作的時(shí)間復(fù)雜度比藻，跟節(jié)點(diǎn)的個(gè)數(shù) n 成正比铝量，也就是說二叉樹遍歷的時(shí)間復(fù)雜度是 O(n)。
4. 練習(xí)
- 二叉樹的前序银亲、中序慢叨、后序遞歸遍歷方法
- 二叉樹的前序、中序务蝠、后序非遞歸遍歷方法
- 二叉樹的層序遍歷
- 獲取樹的總得節(jié)點(diǎn)數(shù)
- 獲取樹的葉子節(jié)點(diǎn)數(shù)
- 求樹的深度
- 求二叉樹第k層的結(jié)點(diǎn)個(gè)數(shù)
- 判斷兩棵二叉樹是否結(jié)構(gòu)相同
- 求二叉樹的鏡像
- 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)
