樹到二叉樹的轉換（三十五）

??????? 我們在之前學習了通用樹的相關知識，那么通用樹的結構實現相對來說比較復雜，有沒有一種比較簡單的樹呢？我們在之前的通用樹結構中使用的是雙親孩子表示法，每個結點都有一個指向其雙親的指針，每個結點都有若干個指向其孩子的指針。結構如下圖所示

????????那么還有另一種樹結構模型 -- 孩子兄弟表示法。每個結點都有一個指向其第一個孩子的指針，每個結點都有一個指向其第一個右兄弟的指針。結構如下圖所示

????????孩子兄弟表示法的特點：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 層最多有 2^i-1 個結點（i >= 1）。

????????????第一層最多有 2^1-1 = 1 個結點；

??????????? 第二層對多有 2^2-1 = 2 個結點；

?????????? ? 第三層最多有 2^3-1 = 4 個結點；

????????????......

??????? 2、高度為 k 的二叉樹最多有 2^k-1個結點（k >= 0）。

????????????如果有一層，最多有 1 = 2^1-1 = 1 個結點；

????????????如果有二層，最多有 1 = 2^2-1 = 3 個結點；

????????????如果有三層，最多有 1 = 2^3-1 = 7 個結點；

????????????......

????????3、對任何一顆二叉樹，如果其葉結點有 n₀ 個，度為 2 的非葉結點有?n₂ 個，則有 n₀ = n₂ + 1。

????????????證明：假設二叉樹中度 1 的結點有 n₁個且總結點為 n 個，則： n = n₀ + n₁ + n₂；

????????????????假設二叉樹中連接父結點與子結點間的邊為 e 條，則： ?e = n₁ + 2n₂ = n -1 ；

????????????????所以：n₀ = n₂ + 1

????????4、具有 n 個結點的完全二叉樹的高度為[log₂n] + 1。（[X] 表示不大于 X 的最大整數）。

????????????證明：假設這 n 個結點組成的完全二叉樹高度為 k，則：?2^k-1-1 < n <= 2^k-1；

????????????????因為 n 為整數，所以：?2^k-1 <= n < 2^k；

????????????????取對數：k-1 <= log₂n < k；

????????????????因為 k 為整數，所以：k = [log₂n] + 1

? ????? 5、一顆有 n 個結點的完全二叉樹（高度為[log₂n] + 1），按層次對結點進行編號（從上到下，從左到右），對任意結點 i 有：

????????????如果 i = 1，則結點 i 是二叉樹根；如果 i > 1，則其雙親結點為 [i/2]；

????????????如果 2i <= n，則結點 i 的左孩子為 2i；如果 2i > n，則結點 i 無左孩子；

????????????如果 2i+1 <= n，則結點 i 的右孩子為 2i+1；如果 2i+1 > n，則結點 i 無右孩子；

????????通過對二叉樹的學習總結如下：1、通用樹結構采用了雙親結點表示法進行描述；2、孩子兄弟表示法有能力描述任意類型的樹結構；3、孩子兄弟表示法能夠將通用樹轉化為二叉樹；4、二叉樹是最多只有兩個孩子的樹。