第6章+樹和二叉樹

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

1、第六章樹和二叉樹6.1樹的定義和基本概念6.2二叉樹6.2.1樹的定義和基本術(shù)語6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)6.3遍歷二叉樹6.3.1遍歷二叉樹6.3.2線索二叉樹6.4樹和森林6.4.1樹的存儲(chǔ)結(jié)構(gòu)6.4.2森林與二叉樹的轉(zhuǎn)換6.4.3樹和森林的遍歷6.6赫夫曼樹及其應(yīng)用6.6.1最優(yōu)二叉樹（赫夫曼樹）6.6.2赫夫曼編碼樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象

2、地表示。樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時(shí)，可用樹來描述其執(zhí)行過程。等等。6.1樹的定義和基本術(shù)語定義：樹(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：（1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；(2)其余的結(jié)點(diǎn)可分為m(m>=0)個(gè)互不相交的子集T1,T2,T3…TmT1,T2,T3…Tm，其中每個(gè)子集又是一棵樹，并稱其為子樹(Subtree)。如圖6.1樹還有其他的

3、表示形式，如圖6.2的三種表示法：（1）嵌套集合（2）廣義表的形式（3）凹入表示法下面是樹結(jié)構(gòu)的一些基本術(shù)語：度：結(jié)點(diǎn)擁有的子樹稱為結(jié)點(diǎn)的度。葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)。其余結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。孩子：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子。相應(yīng)地，該結(jié)點(diǎn)稱為雙親。同一個(gè)雙親的孩子稱為兄弟。依此可以遞歸定義祖先和子孫的概念。結(jié)點(diǎn)的層次：從根開始定義，根為第一層，根的孩子為第二層。若某個(gè)結(jié)點(diǎn)在第l層，則其子樹的根就在第l+1層。雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為

4、樹的深度或高度。有序樹：如果該樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的，則該樹稱為有序樹。否則稱為無序樹。森林：是m（m>=0）棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。由此，可以森林和樹相互遞歸的定義來描述樹。Tree=(root,F)，其中F是m棵樹的森林。F=(T1,T2,T3…Tm)，其中Ti稱做根root的第i棵子樹。6.2二叉樹二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉樹的許多操作算法簡(jiǎn)單，而任何樹都可以與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。6

5、.2.1二叉樹的定義定義：二叉樹是由n(n>=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹，且次序不能任意顛倒。這也是一個(gè)遞歸定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況，它們是兩個(gè)概念。二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。圖6.8列出二差樹的5種基本形態(tài)，圖6.8(C)和圖6.8（d）是不同的兩棵二叉樹。(a)空二叉樹A

6、ABABACB(b)根和空的左右子樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹圖6.8二叉樹的5種形式6.2.2二叉樹的性質(zhì)二叉樹具有下列重要性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1)。采用歸納法證明此性質(zhì)。當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1=20=1,命題成立?，F(xiàn)在假定對(duì)于所有的j，1<=j

7、1層上最大結(jié)點(diǎn)數(shù)的二倍，即2×2i-2＝2i-1。命題得到證明。性質(zhì)2：深度為k的二叉樹至多有2k－1個(gè)結(jié)點(diǎn)（k>=1).深度為k的二叉樹的最大的結(jié)點(diǎn)數(shù)`為二叉樹中每層上的最大結(jié)點(diǎn)數(shù)之和，由性質(zhì)1得到每層上的最大結(jié)點(diǎn)數(shù)：EkI=1（第i層上的最大結(jié)點(diǎn)數(shù)）=EkI=12i-1=2k–1性質(zhì)3：對(duì)任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為n1，二叉樹中總結(jié)點(diǎn)數(shù)為N，因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)均小于或等于2，所以有：N＝n0＋n1＋n2(6-1)再看二叉樹中的分

8、支數(shù)，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)進(jìn)入分支，設(shè)B為二叉樹中的分支總數(shù)，則有：N＝B＋1。由于這些分支都是由度為1和2的結(jié)點(diǎn)射出的，所有有：B＝n1+2*n2N＝B＋1＝n1＋2×n2＋1（6－2)由式（6－1）和（6－2）得到：n0+n1+n2=n1+2*n2+1n0＝n2＋1下面介紹兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿