1. 樹(Tree)
(1) 基礎(chǔ)概念
1> 節(jié)點(diǎn)
- 節(jié)點(diǎn)善已、根節(jié)點(diǎn)、父節(jié)點(diǎn)离例、子節(jié)點(diǎn)换团、兄弟節(jié)點(diǎn)
2> 樹、子樹
- 一棵樹可以沒有任何節(jié)點(diǎn)宫蛆，稱為 空樹
- 一棵樹可以只有1個(gè)節(jié)點(diǎn)艘包，也就是只有根節(jié)點(diǎn)
- 子樹、左子樹耀盗、右子樹
3> 度(degree)
- 節(jié)點(diǎn)的度：子樹的個(gè)數(shù)
- 樹的度：所有節(jié)點(diǎn)度中的最大值
4> 葉子節(jié)點(diǎn)(leaf)
- 葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)
- 非葉子節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)
5> 層數(shù)(level)
- 層數(shù)：根節(jié)點(diǎn)在第1層想虎，根節(jié)點(diǎn)的子節(jié)點(diǎn)在第2層，以此類推
6> 深度(depth)叛拷、高度(height)
- 節(jié)點(diǎn)的深度：從 根節(jié)點(diǎn) 到 當(dāng)前節(jié)點(diǎn) 的唯一路徑上的 節(jié)點(diǎn)總數(shù)
- 節(jié)點(diǎn)的高度：從 當(dāng)前節(jié)點(diǎn) 到 最遠(yuǎn)葉子節(jié)點(diǎn) 的路徑上的 節(jié)點(diǎn)總數(shù)
- 樹的深度：所有節(jié)點(diǎn)深度中的 最大值
- 樹的高度：所有節(jié)點(diǎn)高度中的 最大值
- 樹的深度 等于 樹的高度
二叉樹
(2) 樹的種類
- 有序樹：樹中任意節(jié)點(diǎn)的 子節(jié)點(diǎn)之間 有順序關(guān)系
- 無序樹(自由樹)：樹中任意節(jié)點(diǎn)的 子節(jié)點(diǎn)之間 沒有順序關(guān)系
- 森林：由m(m≥0)棵 互不相交 的樹組成的集合
2. 二叉樹(Binary Tree)
(1) 基礎(chǔ)概念
1> 二叉樹的特點(diǎn)
- 每個(gè)節(jié)點(diǎn)的度 最大為2 (最多擁有2棵子樹)
- 左子樹 和 右子樹 是有順序的
- 即使某節(jié)點(diǎn)只有一棵子樹磷醋，也要區(qū)分左右子樹
2> 二叉樹的性質(zhì)
- 非空二叉樹的 第i層，最多有
個(gè)節(jié)點(diǎn)(i≥1)
- 在高度為h的二叉樹上 最多有
- 1個(gè)節(jié)點(diǎn)(h≥1)
- 對(duì)于任何一棵非空二叉樹胡诗，如果葉子節(jié)點(diǎn)個(gè)數(shù)為
邓线，度為1的節(jié)點(diǎn)個(gè)數(shù)為
，度為2的節(jié)點(diǎn)個(gè)數(shù)為
- 則有:
- 二叉樹的節(jié)點(diǎn)總數(shù)n =
- 二叉樹的邊數(shù)T =
(2) 真二叉樹(Proper Binary Tree)
- 真二叉樹：所有節(jié)點(diǎn)的 度 要么為0煌恢，要么為2
真二叉樹骇陈、滿二叉樹
(3) 滿二叉樹(Full Binary Tree)
- 滿二叉樹：最后一層節(jié)點(diǎn)的度 都為0，其他節(jié)點(diǎn)的度 都為2
- 在同樣高度的二叉樹中瑰抵，滿二叉樹的葉子節(jié)點(diǎn) 數(shù)量最多你雌、總節(jié)點(diǎn) 數(shù)量最多
- 滿二叉樹 一定是 真二叉樹，真二叉樹 不一定是 滿二叉樹
- 假設(shè)滿二叉樹的高度為h(h≥1)二汛，那么
- 第i層的節(jié)點(diǎn)數(shù)量：
- 1
- 葉子節(jié)點(diǎn)數(shù)量：
- 總節(jié)點(diǎn)數(shù)量n
- n=
+
+
+ ... +
%7D)
- h =
(4) 完全二叉樹(Complete Binary Tree)
1> 概念
- 完全二叉樹：對(duì)節(jié)點(diǎn)從上至下婿崭、左至右開始編號(hào)，其所有編號(hào)都能與相同高度的滿二叉樹中的編號(hào)對(duì)應(yīng)
- 葉子節(jié)點(diǎn) 只會(huì)出現(xiàn) 最后2層肴颊，最后1層的 葉子結(jié)點(diǎn) 都靠左對(duì)齊
- 完全二叉樹從 根結(jié)點(diǎn) 至 倒數(shù)第2層 是一棵 滿二叉樹
- 滿二叉樹 一定是 完全二叉樹氓栈，完全二叉樹 不一定是 滿二叉樹
完全二叉樹
2> 性質(zhì)
- 度為1的節(jié)點(diǎn)只有 左子樹
- 度為1的節(jié)點(diǎn)要么 是1個(gè)，要么 是0個(gè)
- 同樣節(jié)點(diǎn)數(shù)量的二叉樹婿着，完全二叉樹的 高度最小
- 假設(shè)完全二叉樹的 高度為h (h≥1)授瘦，那么
- 至少有
+ 1 )
- 最多有
- 總節(jié)點(diǎn)數(shù)量為n
- h - 1 ≤
< h
- h = floor(
- 【floor是向下取整，ceiling是向上取整】
- 一棵有 n個(gè)節(jié)點(diǎn)的完全二叉樹(n>0)提完，從上到下形纺、從左到右對(duì)節(jié)點(diǎn)從1開始進(jìn)行編號(hào)，對(duì)任意第i個(gè)節(jié)點(diǎn)
- 如果 i = 1徒欣，它是根節(jié)點(diǎn)
- 如果 i > 1逐样，它的父節(jié)點(diǎn)編號(hào)為 floor( i / 2 )
- 如果 2i ≤ n，它的左子節(jié)點(diǎn)編號(hào)為 2i
- 如果 2i > n打肝，它無左子節(jié)點(diǎn)
- 如果 2i + 1 ≤ n官研，它的右子節(jié)點(diǎn)編號(hào)為 2i + 1
- 如果 2i + 1 > n，它無右子節(jié)點(diǎn)
3. 面試題
Q: 如果一棵完全二叉樹有768個(gè)節(jié)點(diǎn)闯睹，求葉子節(jié)點(diǎn)的個(gè)數(shù)戏羽？
解題步驟一：
- 假設(shè)葉子節(jié)點(diǎn)個(gè)數(shù)為
- 總結(jié)點(diǎn)個(gè)數(shù)n =
- n = 2
解題步驟二：
- 完全二叉樹的
-
- 葉子節(jié)點(diǎn)個(gè)數(shù)
-
- 葉子節(jié)點(diǎn)個(gè)數(shù)
解題步驟三：
- 葉子節(jié)點(diǎn)個(gè)數(shù)
- 非葉子節(jié)點(diǎn)個(gè)數(shù)
- floor((n + 1) / 2) 即 (n + 1) / 2 或 (n + 1) >> 1
得出答案：
- 因此葉子節(jié)點(diǎn)個(gè)數(shù)為 768 / 2 = 384
