### 定義 二叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2i-1個結點；深度為k的二叉樹至多有2k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。 ### 圖示 :-:  ### 性質 1. 在非空二叉樹中，第i層的結點總數不超過2i-1, i>=1。 2. 深度為h的二叉樹最多有2h-1個結點(h>=1)，最少有h個結點。 3. 對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1。 4. 具有n個結點的完全二叉樹的深度為log2(n+1)。 5. 有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系： * [ ] 若I為結點編號則 如果I>1，則其父結點的編號為I/2； * [ ] 如果2I<=N，則其左兒子（即左子樹的根結點）的編號為2I；若2I>N，則無左兒子； * [ ] 如果2I+1<=N，則其右兒子的結點編號為2I+1；若2I+1>N，則無右兒子。 6. 給定N個節點，能構成h(N)種不同的二叉樹，其中h(N)為卡特蘭數的第N項，h(n)=C(2*n, n)/(n+1)。 7. 設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i。 ### 特殊的二叉樹 * 斜樹：所有的結點都只有左子樹或右子樹，特點是結點的個數與二叉樹的深度相同 * 滿二叉樹：所有的分支結點(非葉子)都存在左子樹和右子樹，并且所有的葉子都在同一層(完全對稱，非葉子結點的度一定是2，結點數是2^n - 1) * 完全二叉樹：允許在滿二叉樹中去掉若干個最后的結點，但是存在的結點序號一定與滿二叉樹位置一致(比滿二叉樹要求低一點，所以滿二叉樹一定是完全二叉樹，反之則不成立。如果某結點的度為1，則該結點只有左孩子) ### 二叉樹的存儲結構 1) 順序存儲：根據二叉樹概念第8點，可以知道完全二叉樹的父結點和孩子結點是有算術關系的，所以用一維數組存儲很方便。但是對于一般的二叉樹則會耗費很多存儲空間(如有5層的斜樹，只有1，2，4，8，16這幾個索引值是存了值的，其他空間都沒有作用) 2) 二叉鏈表：一個結點用(左孩子指針, 右孩子指針, 數據域)來表示，如果沒有孩子結點，則指針域指向空即可，可以節省很多空間(當然如果有必要指向父結點，也可以構造三叉鏈表，略)