二叉樹的性質(zhì)：
- 二叉樹中，第 i 層最多有 2i-1 個(gè)結(jié)點(diǎn)
- 如果二叉樹的深度為 K，那么此二叉樹最多有 2K-1 個(gè)結(jié)點(diǎn)
- 二叉樹中，終端結(jié)點(diǎn)數(shù)（葉子結(jié)點(diǎn)數(shù)）為 n0，度為 2 的結(jié)點(diǎn)數(shù)為 n2，則 n0=n2+1
- 具有 n 個(gè)節(jié)點(diǎn)的滿二叉樹的深度為 log2(n+1)
完全二叉樹：
- 如果二叉樹中除去最后一層節(jié)點(diǎn)后為滿二叉樹，且最后一層的結(jié)點(diǎn)依次從左到右分布，則此二叉樹被稱為完全二叉樹
- n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 [log2n]+1，[log2n] 表示取小于 log2n 的最大整數(shù)
- 對(duì)于任意一個(gè)結(jié)點(diǎn) i，當(dāng) i>1 時(shí)，父親結(jié)點(diǎn)為結(jié)點(diǎn) [i/2]，
深度優(yōu)先搜索：
廣度優(yōu)先搜索：
紅黑樹：
- 本身是一棵二叉查找樹，在其基礎(chǔ)上附加了兩個(gè)要求：
（1）樹中的每個(gè)結(jié)點(diǎn)增加了一個(gè)用于存儲(chǔ)顏色的標(biāo)志域；
（2）樹中沒有一條路徑比其他任何路徑長(zhǎng)出兩倍，整棵樹要接近于“平衡”的狀態(tài) - 滿足以下性質(zhì)的二叉查找樹才是紅黑樹：
（1）樹中所有節(jié)點(diǎn)不是紅的就是黑的
（2） 根結(jié)點(diǎn)的顏色是黑的
（3）所有為 null 的葉子結(jié)點(diǎn)的顏色是黑的
（4）如果此結(jié)點(diǎn)是紅的，那么它的兩個(gè)孩子結(jié)點(diǎn)全部都是黑的
