??????? 我們在之前學(xué)習(xí)了通用樹的相關(guān)知識，那么通用樹的結(jié)構(gòu)實(shí)現(xiàn)相對來說比較復(fù)雜，有沒有一種比較簡單的樹呢？我們在之前的通用樹結(jié)構(gòu)中使用的是雙親孩子表示法，每個(gè)結(jié)點(diǎn)都有一個(gè)指向其雙親的指針，每個(gè)結(jié)點(diǎn)都有若干個(gè)指向其孩子的指針。結(jié)構(gòu)如下圖所示

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)桃江,10年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18982081108

????????那么還有另一種樹結(jié)構(gòu)模型 -- 孩子兄弟表示法。每個(gè)結(jié)點(diǎn)都有一個(gè)指向其第一個(gè)孩子的指針，每個(gè)結(jié)點(diǎn)都有一個(gè)指向其第一個(gè)右兄弟的指針。結(jié)構(gòu)如下圖所示

????????孩子兄弟表示法的特點(diǎn)：1、能夠表示任意的樹形結(jié)構(gòu)；2、每個(gè)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)成員和兩個(gè)指針成員；3、孩子結(jié)點(diǎn)指針和兄弟結(jié)點(diǎn)指針構(gòu)成了“樹杈”。

????????下來我們來看看二叉樹的定義：二叉樹是由 n ( n >= 0 ) 個(gè)結(jié)點(diǎn)組成的有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩顆分別稱為左子樹和右子樹的、互不相交的二叉樹組成。二叉樹有以下 5 種形態(tài)

????????下來我們來看看兩種特殊的二叉樹：滿二叉樹（Full Binary Tree）和完全二叉樹（Complete Binary Tree）。

????????1、滿二叉樹：如果二叉樹中所有分支結(jié)點(diǎn)的度數(shù)都為 2，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。

????????2、完全二叉樹：如果一顆具有 n 個(gè)結(jié)點(diǎn)的高度為 K 的二叉樹，它的每一個(gè)結(jié)點(diǎn)都與高度 K 的滿二叉樹中編號為 1 -- n 的結(jié)點(diǎn)一一對應(yīng)。則稱這顆二叉樹為完全二叉樹（從上到下從左到右編號）。

????????完全二叉樹的相關(guān)特性：a> 同樣結(jié)點(diǎn)數(shù)的二叉樹，完全二叉樹的高度最小；b> 完全二叉樹的葉結(jié)點(diǎn)僅出現(xiàn)在最下面兩層：最底層的葉結(jié)點(diǎn)一定出現(xiàn)在左邊，倒數(shù)第二層的葉結(jié)點(diǎn)一定出現(xiàn)在右邊，完全二叉樹中度為 1 的結(jié)點(diǎn)只有左孩子。如下圖所示

????????下來我們來看看二叉樹的幾個(gè)性質(zhì)：

????????1、在二叉樹的第 i 層最多有 2^i-1 個(gè)結(jié)點(diǎn)（i >= 1）。

????????????第一層最多有 2^1-1 = 1個(gè)結(jié)點(diǎn)；

??????????? 第二層對多有 2^2-1 = 2個(gè)結(jié)點(diǎn)；

?????????? ?第三層最多有 2^3-1 = 4 個(gè)結(jié)點(diǎn)；

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

??????? 2、高度為 k 的二叉樹最多有 2^k-1個(gè)結(jié)點(diǎn)（k >= 0）。

????????????如果有一層，最多有 1 = 2^1-1 = 1 個(gè)結(jié)點(diǎn)；

????????????如果有二層，最多有 1 = 2^2-1 = 3 個(gè)結(jié)點(diǎn)；

????????????如果有三層，最多有 1 = 2^3-1 = 7 個(gè)結(jié)點(diǎn)；

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

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

????????????證明：假設(shè)二叉樹中度 1 的結(jié)點(diǎn)有 n₁個(gè)且總結(jié)點(diǎn)為 n 個(gè)，則： n = n₀ + n₁ + n₂；

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

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

????????4、具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的高度為[log₂n] + 1。（[X] 表示不大于 X 的最大整數(shù)）。

????????????證明：假設(shè)這 n 個(gè)結(jié)點(diǎn)組成的完全二叉樹高度為 k，則：?2^k-1-1 < n <= 2^k-1；

????????????????因?yàn)?n 為整數(shù)，所以：?2^k-1 <= n < 2^k；

????????????????取對數(shù)：k-1 <= log₂n < k；

????????????????因?yàn)?k 為整數(shù)，所以：k = [log₂n] + 1

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

????????????如果 i = 1，則結(jié)點(diǎn) i 是二叉樹根；如果 i > 1，則其雙親結(jié)點(diǎn)為 [i/2]；

????????????如果 2i <= n，則結(jié)點(diǎn) i 的左孩子為 2i；如果 2i > n，則結(jié)點(diǎn) i 無左孩子；

????????????如果 2i+1 <= n，則結(jié)點(diǎn) i 的右孩子為 2i+1；如果 2i+1 > n，則結(jié)點(diǎn) i 無右孩子；

????????通過對二叉樹的學(xué)習(xí)總結(jié)如下：1、通用樹結(jié)構(gòu)采用了雙親結(jié)點(diǎn)表示法進(jìn)行描述；2、孩子兄弟表示法有能力描述任意類型的樹結(jié)構(gòu)；3、孩子兄弟表示法能夠?qū)⑼ㄓ脴滢D(zhuǎn)化為二叉樹；4、二叉樹是最多只有兩個(gè)孩子的樹。

新聞名稱：樹到二叉樹的轉(zhuǎn)換（三十五）
URL標(biāo)題：http://m.newbst.com/article2/jhsioc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、響應(yīng)式網(wǎng)站、網(wǎng)站內(nèi)鏈、小程序開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)