（一） 樹

層次 ： 根為第一層 ， 最大層為樹的高度 ， 深度為根到該節(jié)點(diǎn)的路徑長(zhǎng)度 ； 高度為葉節(jié)點(diǎn)到該節(jié)點(diǎn)最大路徑

二叉樹性質(zhì)：

1 ，二叉樹第 i 層上的結(jié)點(diǎn)數(shù)目最多為 2i-1(i ≥ 1) 。

2 ，深度為 k 的二叉樹至多有 2^k-1 個(gè)結(jié)點(diǎn) (k ≥ 1)

3 ， 在任意 - 棵二叉樹中 ， 若終端結(jié)點(diǎn)的個(gè)數(shù)為 n0 ， 度為 2 的結(jié)點(diǎn)數(shù)為 n2 ， 則 no=n2 1

4 ，具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為： log2[n]( 向下） 1 或 log2[n 1]( 向上）

二叉樹存儲(chǔ)形式：

1 ，順序存儲(chǔ)：第 i 個(gè)結(jié)點(diǎn)的孩子是 2i,2i 1 ( 完全二叉樹適用，如果該樹不是完全二叉 樹，需要添加空節(jié)點(diǎn)構(gòu)成完全二叉樹）

2 ，二叉鏈表結(jié)構(gòu)：左右指針，中間數(shù)據(jù) |left|data|right| 二叉樹遍歷： 遍歷是樹進(jìn)行其他運(yùn)算的基礎(chǔ) ， 前 中 ， 中 后 ， 層次 中 （ 因?yàn)榍昂罂梢酝瞥龈Y(jié)點(diǎn) ， 而中可以推左右） 使用遞歸思想來推樹的結(jié)構(gòu)能夠快些 如：前 中 前： GDAFEMHZ 中： ADEFGHMZ 步驟：根據(jù)前知道 root 是 G ，根據(jù)中知道左子樹是 ADEF, 右子樹是 HMZ 分析 leftTree, 由前知道 root 是 D ， so leftTree is:A,and rightTree is :EF