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

成都創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括廣元網(wǎng)站建設(shè)、廣元網(wǎng)站制作、廣元網(wǎng)頁制作以及廣元網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，廣元網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到廣元省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

那么還有另一種樹結(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 的滿二叉樹中編號(hào)為 1 -- n 的結(jié)點(diǎn)一一對(duì)應(yīng)。則稱這顆二叉樹為完全二叉樹（從上到下從左到右編號(hào)）。

完全二叉樹的相關(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)；

第二層對(duì)多有 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、對(duì)任何一顆二叉樹，如果其葉結(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；

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

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

?????5、一顆有 n 個(gè)結(jié)點(diǎn)的完全二叉樹（高度為[log₂n] + 1），按層次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)（從上到下，從左到右），對(duì)任意結(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 無右孩子；

通過對(duì)二叉樹的學(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)換（三十五）-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://www.rwnh.cn/article30/ceipso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、域名注冊(cè)、響應(yīng)式網(wǎng)站、移動(dòng)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、品牌網(wǎng)站制作

廣告

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