1
二叉樹
的性質
（1）非空二叉樹葉子節點樹等於雙分支節點樹加1。
證明：設二叉樹上葉子節點樹為n0，單分支節點樹為n1，雙分支節點樹為n2（如果沒有特別指出，後面均採用這種設定），則有：
a 總節點數 n=n0+n1+n2；
b 總分支數=n1+2*n2；
c 總分支數=總節點數-1。
根據以上三式有：n1 + 2*n2 = n0 + n1 + n2 - 1
即 n0 = n2 + 1。
（2）非空二叉樹上第i層上至多有2∧（i - 1）個節點（i≥1）。
（3）高度為h的二叉樹至多有2∧h - 1個節點（h≥1）。
（4）對完全二叉樹中編號為i的節點（1≤i≤n，n≥1，n為節點數）有：
① 若2i≤n，則編號為i的節點為分支節點，否則為葉子節點。
② 若n為奇數，則每個分支節點都既有左孩子節點，又有右孩子節點；若n為偶數，則編號最大的分支節點（編號為n/2）只有左孩子節點，其餘分支節點都有左、右孩子節點。
③ 若編號為i的節點有左孩子節點，則左孩子節點的編號為2i；若編號為i的節點有右孩子節點，則右孩子節點的編號為2i + 1。
④ 除根節點外，當i為偶數時，其雙親節點的編號為i/2，它是雙親節點的左孩子節點；當i為奇數時，其雙親節點的編號為（i-1）/2，它是雙親節點的右孩子節點。
（5）具有n個（n＞0）節點的完全二叉樹的高度為 log 2 （n+1） 或 log 2 n + 1。（取對數的最大整數）
