發(fā)送樹(shù)和二叉樹(shù)+1117三班

《發(fā)送樹(shù)和二叉樹(shù)+1117三班》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第6章樹(shù)與二叉樹(shù)6.1樹(shù)的基本概念和術(shù)語(yǔ)6.2二叉樹(shù)6.3遍歷二叉樹(shù)6.4二叉樹(shù)、樹(shù)和森林6.5樹(shù)的應(yīng)用6.1樹(shù)的基本概念和術(shù)語(yǔ)6.1.1樹(shù)的定義樹(shù)(tree)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T。其中：(1)一個(gè)特定的結(jié)點(diǎn)稱為該樹(shù)的根(root)結(jié)點(diǎn),而且有且僅有一個(gè)；(2)根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的有限集合T1，T2，…，Tm，且其中每一個(gè)集合本身又是一棵樹(shù)，稱之為根的子樹(shù)(subtree)。這是一個(gè)遞歸的定義，即在定義中又用到了樹(shù)這個(gè)術(shù)語(yǔ)。它反應(yīng)了樹(shù)的固有特性?？梢哉J(rèn)為僅有一個(gè)根結(jié)點(diǎn)的樹(shù)是最小樹(shù)，樹(shù)中結(jié)點(diǎn)較多時(shí)，每個(gè)結(jié)點(diǎn)都是某一棵子樹(shù)的根。

2、在圖6.1中是一棵由11個(gè)結(jié)點(diǎn)組成樹(shù)T。其中A是根結(jié)點(diǎn)，其余結(jié)點(diǎn)分為三個(gè)互不相交的子集：T1={B，E，F(xiàn)}，T2={C，G}，T3={D，H，I，J，K}。T1，T2，T3都是樹(shù)根A的子樹(shù)，這三棵子樹(shù)的根結(jié)點(diǎn)分別是B，C，D。每棵子樹(shù)本身也是一棵樹(shù)，可繼續(xù)劃分。例如子樹(shù)T3以D為根結(jié)點(diǎn)，它的其余結(jié)點(diǎn)又可分為三個(gè)互相交的子集T31={H}，T32={I，K}，T33={J}，而其中T31，T33可都認(rèn)為是僅有一個(gè)根結(jié)點(diǎn)的子樹(shù)。圖6.1樹(shù)T6.1.2樹(shù)的常用術(shù)語(yǔ)樹(shù)結(jié)構(gòu)常常用到一些術(shù)語(yǔ)，如度、雙親、孩子、樹(shù)深等。樹(shù)的結(jié)點(diǎn)代表樹(shù)中的一個(gè)數(shù)據(jù)元素，它帶有數(shù)據(jù)信息，同時(shí)還帶有若

3、干分支。結(jié)點(diǎn)的度是該結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)。例如結(jié)點(diǎn)B有兩棵子樹(shù)，它的度是2。樹(shù)的度是樹(shù)中結(jié)點(diǎn)度的最大值。例如度為零的結(jié)點(diǎn)稱為葉子或終結(jié)點(diǎn)，度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)。圖6.1中樹(shù)T的度為3。結(jié)點(diǎn)E，F(xiàn)，G，H，K，J度為零，它們是葉子結(jié)點(diǎn)。某結(jié)點(diǎn)的各子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，而該結(jié)點(diǎn)又稱為孩子們的雙親結(jié)點(diǎn)。具有相同雙親的結(jié)點(diǎn)互稱為兄弟。圖6.1中根結(jié)點(diǎn)A有三棵子樹(shù)，這三棵子樹(shù)的根結(jié)點(diǎn)分別是B，C，D，因此說(shuō)結(jié)點(diǎn)A是結(jié)點(diǎn)B，C，D的雙親，而結(jié)點(diǎn)B，C，D又都是結(jié)點(diǎn)A的孩子，B，C，D之間互為兄弟。一棵樹(shù)上除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn)稱為根結(jié)點(diǎn)的子孫。對(duì)于樹(shù)中某結(jié)點(diǎn)，從根結(jié)點(diǎn)

4、開(kāi)始到該結(jié)點(diǎn)的雙親是該結(jié)點(diǎn)的祖先。結(jié)點(diǎn)的層次值從根算起，根的層次值為1，其余結(jié)點(diǎn)的層次值為雙親結(jié)點(diǎn)層次值加1。一棵樹(shù)的深度是該樹(shù)中結(jié)點(diǎn)最大層次值，例如圖6.1中的樹(shù)T的深度為4。結(jié)點(diǎn)A，B，E，K的層次值分別為1，2，3，4。6.1.3樹(shù)的表示形式樹(shù)的表示形式有多種，常見(jiàn)的三種形式是：(1)倒懸樹(shù)法，如圖6.1所示；(2)集合包含關(guān)系文氏圖法，如圖6.2(a)所示；(3)凹入法，如圖6.2(b)所示。圖6.2樹(shù)結(jié)構(gòu)的不同表示方法(a)文氏圖法；(b)凹入法6.2二叉樹(shù)6.2.1二叉樹(shù)的定義二叉樹(shù)(binarytree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諛?shù)(n=0

5、)，或?yàn)榉强諛?shù)。對(duì)于非空樹(shù)有：(1)有一個(gè)特定的稱之為根的結(jié)點(diǎn)。(2)除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)分為兩個(gè)互不相交的稱之為左子樹(shù)和右子樹(shù)的二叉樹(shù)。這個(gè)定義是遞歸的。由于左、右子樹(shù)也是二叉樹(shù)，因此子樹(shù)也可為空樹(shù)。圖6.3中展現(xiàn)了五種不同基本形態(tài)的二叉樹(shù)。圖6.3二叉樹(shù)的五種基本形態(tài)其中(a)為空樹(shù)，(b)為僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)，(c)是僅有左子樹(shù)而右子樹(shù)為空的二叉樹(shù)，(d)是僅有右子樹(shù)而左子樹(shù)為空的二叉樹(shù)，(e)是左、右子樹(shù)均非空的二叉樹(shù)。這里應(yīng)特別注意的是，二叉樹(shù)的左子樹(shù)和右子樹(shù)是嚴(yán)格區(qū)分并且不能隨意顛倒的，圖6.3(c)與圖6.3(d)就是兩棵不同的二叉樹(shù)。6.2.2二叉

6、樹(shù)的重要性質(zhì)性質(zhì)1二叉樹(shù)第i(i≥1)層上至多有2i-1個(gè)結(jié)點(diǎn)。證明：根據(jù)圖6.4(a)可知，根結(jié)點(diǎn)在二叉樹(shù)的第一層上，這層結(jié)點(diǎn)數(shù)最多為1個(gè)，即20個(gè)；顯然第二層上最多有2個(gè)結(jié)點(diǎn)，即21個(gè)；…假設(shè)第i-1層的結(jié)點(diǎn)最多有2i-2個(gè)，且每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，那么第i層上結(jié)點(diǎn)最多有2*2i-2=2i-1個(gè)。性質(zhì)1證明完畢。性質(zhì)2深度為k(k≥1)的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。證明：由性質(zhì)(1)可知各層結(jié)點(diǎn)最多數(shù)目之和為：20+21+22+…..+2k-1；由二進(jìn)制換算關(guān)系可知：20+21+22+…+2k-1=2k–1，因此二叉樹(shù)樹(shù)中結(jié)點(diǎn)的最大數(shù)目為2k-1。性質(zhì)2證明完畢

7、。性質(zhì)3在任意二叉樹(shù)中，若葉子結(jié)點(diǎn)(即度為零的結(jié)點(diǎn))個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，那么n0=n2+1。證明：設(shè)n代表二叉樹(shù)結(jié)點(diǎn)的總數(shù)，那么n=n0+n1+n2(6.1)由于有n個(gè)結(jié)點(diǎn)的二叉樹(shù)總邊數(shù)為n-1條，于是得n-1=0*n0+1*n1+2*n2(6.2)將(6.1)式代入(6.2)式得n0=n2+1性質(zhì)3證明完畢。現(xiàn)在介紹兩種特殊形態(tài)的二叉樹(shù)，它們是滿二叉樹(shù)和完全二叉樹(shù)。深度為k并且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)，如圖6.4(a)所示。對(duì)滿二叉樹(shù)的結(jié)點(diǎn)可以從根結(jié)點(diǎn)開(kāi)始自上向下，自左至右順序編號(hào)，圖6.4(a