我們在之前學習了通用樹的相關知識，那麼通用樹的結構實作相對來說比較複雜，有沒有一種比較簡單的樹呢？我們在之前的通用樹結構中使用的是雙親孩子表示法，每個結點都有一個指向其雙親的指針，每個結點都有若幹個指向其孩子的指針。結構如下圖所示
那麼還有另一種樹結構模型 -- 孩子兄弟表示法。每個結點都有一個指向其第一個孩子的指針，每個結點都有一個指向其第一個右兄弟的指針。結構如下圖所示
孩子兄弟表示法的特點：1、能夠表示任意的樹形結構；2、每個結點包含一個資料成員和兩個指針成員；3、孩子結點指針和兄弟結點指針構成了“樹杈”。
下來我們來看看二叉樹的定義：二叉樹是由 n ( n >= 0 ) 個結點組成的有限集合，該集合或者為空，或者是由一個根結點加上兩顆分别稱為左子樹和右子樹的、互不相交的二叉樹組成。二叉樹有以下 5 種形态
下來我們來看看兩種特殊的二叉樹：滿二叉樹（Full Binary Tree）和完全二叉樹（Complete Binary Tree）。
1、滿二叉樹：如果二叉樹中所有分支結點的度數都為 2，且葉子結點都在同一層次上，則稱這類二叉樹為滿二叉樹。
2、完全二叉樹：如果一顆具有 n 個結點的高度為 K 的二叉樹，它的每一個結點都與高度 K 的滿二叉樹中編号為 1 -- n 的結點一一對應。則稱這顆二叉樹為完全二叉樹（從上到下從左到右編号）。
完全二叉樹的相關特性：a> 同樣結點數的二叉樹，完全二叉樹的高度最小；b> 完全二叉樹的葉結點僅出現在最下面兩層：最底層的葉結點一定出現在左邊，倒數第二層的葉結點一定出現在右邊，完全二叉樹中度為 1 的結點隻有左孩子。如下圖所示
下來我們來看看二叉樹的幾個性質：
1、在二叉樹的第 i 層最多有 2i-1 個結點（i >= 1）。
第一層最多有 21-1 = 1 個結點；
第二層對多有 22-1 = 2 個結點；
第三層最多有 23-1 = 4 個結點；
......
2、高度為 k 的二叉樹最多有 2k-1個結點（k >= 0）。
如果有一層，最多有 1 = 21-1 = 1 個結點；
如果有二層，最多有 1 = 22-1 = 3 個結點；
如果有三層，最多有 1 = 23-1 = 7 個結點；
3、對任何一顆二叉樹，如果其葉結點有 n0 個，度為 2 的非葉結點有 n2 個，則有 n0 = n2 + 1。
證明：假設二叉樹中度 1 的結點有 n1個且總結點為 n 個，則： n = n0 + n1 + n2；
假設二叉樹中連接配接父結點與子結點間的邊為 e 條，則： e = n1 + 2n2 = n -1 ；
是以：n0 = n2 + 1
4、具有 n 個結點的完全二叉樹的高度為[log2n] + 1。（[X] 表示不大于 X 的最大整數）。
證明：假設這 n 個結點組成的完全二叉樹高度為 k，則： 2k-1-1 < n <= 2k-1；
因為 n 為整數，是以： 2k-1 <= n < 2k；
取對數：k-1 <= log2n < k；
因為 k 為整數，是以：k = [log2n] + 1
5、一顆有 n 個結點的完全二叉樹（高度為[log2n] + 1），按層次對結點進行編号（從上到下，從左到右），對任意結點 i 有：
如果 i = 1，則結點 i 是二叉樹根；如果 i > 1，則其雙親結點為 [i/2]；
如果 2i <= n，則結點 i 的左孩子為 2i；如果 2i > n，則結點 i 無左孩子；