數(shù)據(jù)結(jié)構(gòu)A第5章(南郵)

第5章樹(shù)引言樹(shù)形結(jié)構(gòu)是元素之間具有分層關(guān)系的結(jié)構(gòu)，它類似于自然界中的樹(shù)，應(yīng)用廣泛，是一類很重要的非線性數(shù)據(jù)結(jié)構(gòu)。在計(jì)算機(jī)應(yīng)用中，常出現(xiàn)嵌套的數(shù)據(jù)，樹(shù)結(jié)構(gòu)提供了對(duì)該類數(shù)據(jù)的自然表示；利用樹(shù)結(jié)構(gòu)，可以有效地解決一些算法問(wèn)題。由于結(jié)構(gòu)特征，樹(shù)形結(jié)構(gòu)常采用遞歸方式定義。被稱為遞歸數(shù)據(jù)結(jié)構(gòu)。有關(guān)樹(shù)的許多算法是遞歸的。數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE南京郵電大學(xué)計(jì)算機(jī)學(xué)院內(nèi)容提要1、樹(shù)的基本概念；給出樹(shù)的定義，關(guān)于樹(shù)中的一些術(shù)語(yǔ)；2、二叉樹(shù)的定義、性質(zhì)及其規(guī)范；3、二叉樹(shù)的遍歷等算法的實(shí)現(xiàn)；4、樹(shù)和森林的表示、存儲(chǔ)和遍歷；5、二叉樹(shù)的應(yīng)用實(shí)例——哈夫曼樹(shù)和哈夫曼編碼。南京郵電大學(xué)計(jì)算機(jī)學(xué)院層次結(jié)構(gòu)的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。國(guó)家、省、市、縣和區(qū)。書的章節(jié)、回目。上級(jí)和下級(jí)。整體和部分。祖先和后裔。5.1樹(shù)的基本概念5.1.1樹(shù)的定義課堂提要第5章樹(shù)5.1樹(shù)的基本概念5.2二叉樹(shù)5.3二叉樹(shù)的遍歷5.5樹(shù)和森林5.7哈夫曼樹(shù)和哈夫曼編碼南京郵電大學(xué)計(jì)算機(jī)學(xué)院圖5-1西歐語(yǔ)言譜系圖原始印歐語(yǔ)古意大利語(yǔ)日耳曼語(yǔ)西日耳曼語(yǔ)拉丁語(yǔ)西班牙語(yǔ)法語(yǔ)意大利語(yǔ)希臘語(yǔ)北日耳曼語(yǔ)冰島語(yǔ)瑞典語(yǔ)挪威語(yǔ)英語(yǔ)荷蘭語(yǔ)德語(yǔ)古希臘語(yǔ)南京郵電大學(xué)計(jì)算機(jī)學(xué)院樹(shù)形結(jié)構(gòu)操作系統(tǒng)的目錄結(jié)構(gòu)南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.樹(shù)的定義定義5.1有根數(shù)或樹(shù)的定義

樹(shù)是包括n（n1）個(gè)元素的有限非空集合D，R是D中元素的序偶的集合，R滿足以下特性：（1）有且僅有一個(gè)結(jié)點(diǎn)r∈D，不存在任何結(jié)點(diǎn)v∈D，v≠r，使得<v,r>∈R，稱r為樹(shù)的根。（2）除根r以外的所有結(jié)點(diǎn)u∈D，都有且僅有一個(gè)結(jié)點(diǎn)v∈D，v≠u，使得<v,u>∈R。這樣定義的樹(shù)也稱有根樹(shù)，簡(jiǎn)稱樹(shù)。樹(shù)不為空集合，樹(shù)中至少有一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)，其余結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)。因此樹(shù)形成層次結(jié)構(gòu)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院2.樹(shù)的遞歸定義定義5.2

樹(shù)是包括n個(gè)結(jié)點(diǎn)的有限非空集合T，其中一個(gè)特定的結(jié)點(diǎn)r稱為根，其余結(jié)點(diǎn)（T-{r}）劃分成m（m≥0）個(gè)互不相交的子集T1，T2，...Tm，其中，每個(gè)子集都是樹(shù)，被稱為樹(shù)根r的子樹(shù)。定義5.2是遞歸的，用子樹(shù)來(lái)定義樹(shù)，也就是說(shuō)，在樹(shù)的定義中引用了樹(shù)概念本身，所以，樹(shù)被稱為遞歸數(shù)據(jù)結(jié)構(gòu)。EAFGBCDLJMN南京郵電大學(xué)計(jì)算機(jī)學(xué)院結(jié)點(diǎn)(node)：樹(shù)中的元素。

E、A、F、B、G、C、D、L、J、M、N均為結(jié)點(diǎn)。5.1.2基本術(shù)語(yǔ)EAFGBCDLJMN路徑(path)：從某個(gè)結(jié)點(diǎn)沿樹(shù)中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。E和N之間存在一條路徑。根結(jié)點(diǎn)和它的子樹(shù)根（如果存在）之間形成一條邊。路徑(path)：從某個(gè)結(jié)點(diǎn)沿樹(shù)中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。E和N之間存在一條路徑。EAFGBCDLJMN路徑(path)：從某個(gè)結(jié)點(diǎn)沿樹(shù)中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。E和N之間存在一條路徑。南京郵電大學(xué)計(jì)算機(jī)學(xué)院雙親(parent)：若一個(gè)結(jié)點(diǎn)有子樹(shù)，那么該結(jié)點(diǎn)稱為子樹(shù)根的雙親。A、F、B的雙親是E。C、D的雙親是F。孩子(child)：某結(jié)點(diǎn)子樹(shù)的根是該結(jié)點(diǎn)的孩子。E有三個(gè)孩子：A、F、B。D有一個(gè)孩子：J。兄弟(sibling)：有相同雙親的結(jié)點(diǎn)互為兄弟。A、F、B互為兄弟，C和D互為兄弟。結(jié)點(diǎn)G和C互為兄弟否？EAFGBCDLJMN南京郵電大學(xué)計(jì)算機(jī)學(xué)院后裔(decendent)：一個(gè)結(jié)點(diǎn)的所有子樹(shù)上的任何結(jié)點(diǎn)都是該結(jié)點(diǎn)的后裔。結(jié)點(diǎn)C的后裔為：L、M、N。EAFGBCDLJMN祖先(ancestor)：從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先。結(jié)點(diǎn)L的祖先為：E、F、C。南京郵電大學(xué)計(jì)算機(jī)學(xué)院結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。結(jié)點(diǎn)E的度為3，結(jié)點(diǎn)F的度為2，結(jié)點(diǎn)A的度為1，結(jié)點(diǎn)G的度為0。葉子(leaf)：度為零的結(jié)點(diǎn)。B、G、J、M、N均為葉子結(jié)點(diǎn)。EAFGBCDLJMN分支結(jié)點(diǎn)(branch)：度不為零的結(jié)點(diǎn)。E、A、F、C等為分支結(jié)點(diǎn)。樹(shù)的度：樹(shù)中結(jié)點(diǎn)的最大的度。該樹(shù)的度為3。南京郵電大學(xué)計(jì)算機(jī)學(xué)院結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1。結(jié)點(diǎn)E的層次為1。結(jié)點(diǎn)M的層次為5。樹(shù)的高度：樹(shù)中結(jié)點(diǎn)的最大層次?！邩?shù)中結(jié)點(diǎn)的最大層次為5?！鄻?shù)的高度為5。12345EAFGBCDLJMN南京郵電大學(xué)計(jì)算機(jī)學(xué)院AG無(wú)序樹(shù)：如果樹(shù)中結(jié)點(diǎn)的各子樹(shù)之間的次序是不重要的，可以交換位置。下列是同一棵無(wú)序樹(shù)：將左邊樹(shù)中所有結(jié)點(diǎn)的子樹(shù)互換次序就是右邊的樹(shù)。EAFGBCDLJMNEFBCDLJNM南京郵電大學(xué)計(jì)算機(jī)學(xué)院有序樹(shù)：如果樹(shù)中結(jié)點(diǎn)的各棵子樹(shù)看成是從左到右有次序的，則稱該樹(shù)為有序樹(shù)。有序樹(shù)的各子樹(shù)從左到右為第一棵子樹(shù)、第二棵，…如果下列是有序樹(shù)，則二者是二棵不同的樹(shù)AGEAFGBCDLJMNEFBCDLJNM南京郵電大學(xué)計(jì)算機(jī)學(xué)院森林：是樹(shù)的集合。0個(gè)或多個(gè)不相交的樹(shù)組成森林。果園或有序森林：有序樹(shù)的有序集合。森林與樹(shù)只有很小的差別，若將樹(shù)中的根去掉，則得到根的子樹(shù)組成的森林。BEAGFCDLJMNE若增加一個(gè)結(jié)點(diǎn)，將森林中各樹(shù)的根作為新增結(jié)點(diǎn)的孩子，則森林即成為樹(shù)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院遞歸1.遞歸的定義函數(shù)直接（間接）調(diào)用自已，稱為函數(shù)的遞歸調(diào)用。2.簡(jiǎn)單實(shí)例以下是一個(gè)最簡(jiǎn)單的遞歸函數(shù)。voidfunc(){func();}

修改為：voidfunc(intn){if(n<=0)return;func(n--);}南京郵電大學(xué)計(jì)算機(jī)學(xué)院3.遞推關(guān)系可以把要解決的問(wèn)題轉(zhuǎn)化為一個(gè)新問(wèn)題，而這個(gè)新的問(wèn)題的解決方法仍與原來(lái)的解決方法相同，只是所處理對(duì)象的規(guī)模有規(guī)律地遞增或遞減，即要找到對(duì)象之間的遞推關(guān)系。

方法相同，規(guī)模變化4.遞歸的結(jié)束條件要有一個(gè)明確的結(jié)束遞歸的條件，一定要能夠在適當(dāng)?shù)牡胤浇Y(jié)束遞歸調(diào)用，不然可能導(dǎo)致系統(tǒng)崩潰南京郵電大學(xué)計(jì)算機(jī)學(xué)院intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}例如：采用遞歸計(jì)算N！正整數(shù)N?。絅*(N-1)*(N-2)*…*2*1，

階乘序列可轉(zhuǎn)換為N?。絅*(N-1)!，而(N-1)!以可轉(zhuǎn)換為(N-1)!=(N-1)*(N-2)!(N-2)!=(N-2)*(N-3)!，……2!=2*1!1!=1遞推關(guān)系：N?。絅*(N-1)!結(jié)束條件：N等于1南京郵電大學(xué)計(jì)算機(jī)學(xué)院intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}n=3{if(n==1)…….func(n-1)*n}n=2{if(n==1)…….func(n-1)*n}n=1{if(n==1)return1}1func(n-1)func(n-1)n=2n=12執(zhí)行過(guò)程：南京郵電大學(xué)計(jì)算機(jī)學(xué)院設(shè)計(jì)遞歸算法，求有n個(gè)元素的整數(shù)數(shù)組A中的最大值。

a0a1…ai…

an-2an-101…i…n-2n-1a(n-1)Max(n)Max(n-1)

a0a1…ai…

an-3an-2an-101…i…n-2n-1a(n-2)Max(n-1)Max(n-2)南京郵電大學(xué)計(jì)算機(jī)學(xué)院設(shè)計(jì)遞歸算法，求整數(shù)數(shù)組A[n]中的最大值。

a0a1…ai…

an-3an-2an-101…i…n-2n-1a(1)Max(2)Max(1)遞推關(guān)系：max(n)等于max(n-1)與a[n-1]之間的大者結(jié)束條件：n等于1時(shí)，Max(1)的值即為a0，所以不再向下遞推南京郵電大學(xué)計(jì)算機(jī)學(xué)院intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(temp<a[n-1])returna[n-1];elsereturntemp;}}遞推關(guān)系：max(n)等于max(n-1)與a[n-1]之間的大者結(jié)束條件：n等于1時(shí)，Max(1)的值即為a0，所以不再向下遞推南京郵電大學(xué)計(jì)算機(jī)學(xué)院intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(temp<a[n-1])returna[n-1];elsereturntemp;}}

8

9

10012n=3{if(n==1)…….Max(a,2)<a[2]}n=2{if(n==1)…….Max(a,1)<a[1]}n=1{if(n==1)returna[0]}89南京郵電大學(xué)計(jì)算機(jī)學(xué)院二叉樹(shù)是非常重要的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。很多從實(shí)際問(wèn)題中抽象出來(lái)的數(shù)據(jù)是二叉樹(shù)形的；以后我們將看到任意樹(shù)或森林可方便地轉(zhuǎn)換成二叉樹(shù)，從而為一般樹(shù)和森林的存儲(chǔ)和處理提供了有效方法。5.2二叉樹(shù)課堂提要第5章樹(shù)5.1樹(shù)的基本概念5.2二叉樹(shù)5.3二叉樹(shù)的遍歷5.5樹(shù)和森林5.7哈夫曼樹(shù)和哈夫曼編碼南京郵電大學(xué)計(jì)算機(jī)學(xué)院方法二：改進(jìn)結(jié)構(gòu)，組織成樹(shù)形結(jié)構(gòu)。比較次數(shù)不會(huì)超過(guò)樹(shù)高，提高了效率。先看一個(gè)二叉樹(shù)應(yīng)用例子。設(shè)有序表為（21，25，28，33，36，45），現(xiàn)在要在表中查找元素33。282136253345方法一：順序搜索。效率低，平均比較一半的元素。（21，25，28，33，36，45）比較了4次！比較了3次！3333南京郵電大學(xué)計(jì)算機(jī)學(xué)院定義5.3

二叉樹(shù)(binarytree)是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根和兩個(gè)互不相交的、稱為該根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。上述定義表明二叉樹(shù)可以為空集，因此，二叉樹(shù)有5種基本形態(tài)。5.2.1二叉樹(shù)的定義(a)(b)(c)(d)(e)圖5-4二叉樹(shù)的五種基本形態(tài)南京郵電大學(xué)計(jì)算機(jī)學(xué)院樹(shù)與二叉樹(shù)的區(qū)別：⑴樹(shù)不能是空樹(shù)，即至少有一個(gè)根結(jié)點(diǎn)。而二叉樹(shù)可以是空樹(shù)。⑵一般樹(shù)的子樹(shù)之間是無(wú)序的。而二叉樹(shù)中結(jié)點(diǎn)的子樹(shù)要區(qū)分左、右子樹(shù)，即使只有一棵子樹(shù)。⑶樹(shù)中每個(gè)節(jié)點(diǎn)可有0棵或若干子樹(shù)。而二叉樹(shù)的每個(gè)節(jié)點(diǎn)最多只能有2棵子樹(shù)。EFEF南京郵電大學(xué)計(jì)算機(jī)學(xué)院性質(zhì)5.1二叉樹(shù)的第i(i1)層上至多有2i-1個(gè)結(jié)點(diǎn)?？捎脷w納法證明之。當(dāng)i=1時(shí)，二叉樹(shù)至多只有一個(gè)結(jié)點(diǎn)，結(jié)論成立。設(shè)當(dāng)i=k時(shí)結(jié)論成立，即二叉樹(shù)上至多有2k-1個(gè)結(jié)點(diǎn)，當(dāng)i=k+1時(shí)，∵每個(gè)結(jié)點(diǎn)最多只有兩個(gè)孩子，∴第k+1層上至多有2*2k–1=2k個(gè)結(jié)點(diǎn)，性質(zhì)成立。5.2.2二叉樹(shù)的性質(zhì)南京郵電大學(xué)計(jì)算機(jī)學(xué)院性質(zhì)1、2的圖形解釋性質(zhì)5.1二叉樹(shù)的第i(i1)層上至多有2i-1個(gè)結(jié)點(diǎn)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院性質(zhì)5.2高度為h的二叉樹(shù)上至多有2h–1個(gè)結(jié)點(diǎn)。當(dāng)h=0時(shí)，二叉樹(shù)為空二叉樹(shù)。當(dāng)h>0時(shí)，利用性質(zhì)1，高度為h的二叉樹(shù)中結(jié)點(diǎn)的總數(shù)最多為：南京郵電大學(xué)計(jì)算機(jī)學(xué)院性質(zhì)1、2的圖形解釋南京郵電大學(xué)計(jì)算機(jī)學(xué)院性質(zhì)5.3包含n個(gè)元素的二叉樹(shù)的高度至少為

log2

(n+1)

根據(jù)性質(zhì)2，高度為h的二叉樹(shù)最多有2h–1個(gè)結(jié)點(diǎn)（性質(zhì)2），因而n2h–1,則有hlog2(n+1)。由于h是整數(shù)，所以h

log2

(n+1)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院性質(zhì)5.4任意一棵二叉樹(shù)中，若葉結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則必有n0=n2+1。設(shè)二叉樹(shù)的度為1的結(jié)點(diǎn)數(shù)為n1，樹(shù)中結(jié)點(diǎn)總數(shù)為n，則n=n0+n1+n2……①（∵二叉樹(shù)中只有度為0、1、2三種類型的結(jié)點(diǎn)）設(shè)分支數(shù)為B，n個(gè)結(jié)點(diǎn)的二叉樹(shù)，除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，則B=n-1；分支是由度為1或者度為2的射出的，又有B=2n2+n1；則有：n-1=2n2+n1n=2n2+n1+1……②由①②可得到：n0+n1+n2=2n2+n1+1n0+n2=2n2+1 即n2=n0-1。南京郵電大學(xué)計(jì)算機(jī)學(xué)院定義5.4高度為h的二叉樹(shù)恰好有2h–1個(gè)結(jié)點(diǎn)時(shí)稱為滿二叉樹(shù)。01234567891011121314(a)滿二叉樹(shù)圖5.6幾種特殊的二叉樹(shù)性質(zhì)5.2高度為h的二叉樹(shù)上至多有2h–1個(gè)結(jié)點(diǎn)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院0123456789(b)完全二叉樹(shù)圖5.6幾種特殊的二叉樹(shù)9定義5.5一棵二叉樹(shù)中，只有最下面兩層結(jié)點(diǎn)的度可以小于2，并且最下一層的葉結(jié)點(diǎn)集中在靠左的若干位置上。這樣的二叉樹(shù)稱為完全二叉樹(shù)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院定義5.6擴(kuò)充二叉樹(shù)也稱2-樹(shù)，其中除葉子結(jié)點(diǎn)外，其余結(jié)點(diǎn)都必須有兩個(gè)孩子。532330111213173589南京郵電大學(xué)計(jì)算機(jī)學(xué)院完全二叉樹(shù)的性質(zhì)性質(zhì)5.5具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為log2

(n+1)。證明：根據(jù)性質(zhì)2高度為h-1的完全二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)最多為2h-1-1高度為h的完全二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)最多為2h-1高度為h的完全二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)取值范圍[2h-1,2h)2h-1-1＜n≤2h–1log2(n+1)≤h＜log2(n+1)+1h=log2

(n+1)結(jié)論：⑴n個(gè)結(jié)點(diǎn)的二叉樹(shù)中完全二叉樹(shù)最矮，高度為log2(n+1)。⑵n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)和二叉判定樹(shù)的高度是一樣的2h-1≤n＜2hh-1≤log2n＜h∵h(yuǎn)是整數(shù)∴h=①①②②性質(zhì)2高度為h的二叉樹(shù)上至多有2h–1個(gè)結(jié)點(diǎn)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院性質(zhì)5.6假定對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中的結(jié)點(diǎn)，按從上到下、從左到右的順序，從0到n-1編號(hào)（見(jiàn)圖5.6(c)），設(shè)樹(shù)中一個(gè)結(jié)點(diǎn)的序號(hào)為i，0i＜n，則有以下關(guān)系成立：（1）當(dāng)i=0時(shí)，該結(jié)點(diǎn)為二叉樹(shù)的根。（2）若i>0，則該結(jié)點(diǎn)的雙親的序號(hào)為(i-1)/2（3）若2i+1＜n，則該結(jié)點(diǎn)的左孩子的序號(hào)為2i+1，否則該結(jié)點(diǎn)無(wú)左孩子。（4）若2i+2＜n，則該結(jié)點(diǎn)的右孩子的序號(hào)為2i+2，否則該結(jié)點(diǎn)無(wú)右孩子。0123456789(b)完全二叉樹(shù)南京郵電大學(xué)計(jì)算機(jī)學(xué)院ADTBinaryTree{Data:二叉樹(shù)是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根和兩個(gè)互不相交的稱為該根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

Operations:Create()：創(chuàng)建一棵空二叉樹(shù)。Destroy():撤銷一棵二叉樹(shù)。IsEmpty()：若二叉樹(shù)空，則返回true，否則返回false。Clear():移去所有結(jié)點(diǎn)，成為空二叉樹(shù)。Root(x)：取x為根結(jié)點(diǎn)；若操作成功，則返回true，否則返回falseMakeTree(x,left，right)：創(chuàng)建一棵二叉樹(shù)，x為根結(jié)點(diǎn)，left為左子樹(shù)，right為右子樹(shù)。BreakTree(x,left,right)：拆分二叉樹(shù)為三部分，x為根的值，left和right分別為原樹(shù)的左右子樹(shù)PreOrder：使用函數(shù)Visit訪問(wèn)結(jié)點(diǎn)，先序遍歷二叉樹(shù)。InOrder：使用函數(shù)Visit訪問(wèn)結(jié)點(diǎn)，中序遍歷二叉樹(shù)。PostOrder：使用函數(shù)Visit訪問(wèn)結(jié)點(diǎn)，后序遍歷二叉樹(shù)。}

5.2.3二叉樹(shù)ADT南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.完全二叉樹(shù)的順序表示完全二叉樹(shù)中的結(jié)點(diǎn)可以按層次順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中。根結(jié)點(diǎn)保存在編號(hào)為0的位置上。注意：一般的二叉樹(shù)不適合用這種存儲(chǔ)結(jié)構(gòu)。01234567890123456789圖6.5圖6.4(b)完全二叉樹(shù)的順序表示0123456789圖6.4(b)完全二叉樹(shù)5.2.4二叉樹(shù)的存儲(chǔ)表示南京郵電大學(xué)計(jì)算機(jī)學(xué)院element2.二叉樹(shù)的鏈接表示ABCDEFAB^C^D^^E^^F^(a)二叉樹(shù) (b)二叉樹(shù)的鏈接表示圖6-6二叉樹(shù)的鏈接表示lChildrChild二叉樹(shù)的二叉鏈表結(jié)構(gòu)有利于從雙親到孩子方向的訪問(wèn)。采取從根開(kāi)始，遍歷整個(gè)二叉樹(shù)。root南京郵電大學(xué)計(jì)算機(jī)學(xué)院如果應(yīng)用程序需要經(jīng)常執(zhí)行從孩子到雙親訪問(wèn)，可在二叉鏈表結(jié)點(diǎn)中增加一個(gè)parent域，令它指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。這就實(shí)現(xiàn)了從孩子到雙親，以及從雙親到孩子的雙向鏈接結(jié)構(gòu)，形成多重鏈表。南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>structBTNode//樹(shù)結(jié)點(diǎn){BTNode(){lChild=rChild=NULL;}BTNode(constT&x){element=x;lChild=rChild=NULL;}BTNode(constT&x,BTNode<T>*l,BTNode<T>*r){element=x;lChild=l;rChild=r;}Telement;BTNode<T>*lChild,*rChild;};5.2.5二叉樹(shù)類南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>classBinaryTree{public:BinaryTree(){root=NULL;}

~BinaryTree(){Clear();}boolIsEmpty()const;voidClear();boolRoot(T&x)const;voidMakeTree(constT&e,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&e,BinaryTree<T>&left,BinaryTree<T>&right);voidPreOrder(void(*Visit)(T&x));//公有函數(shù)，用戶接口voidInOrder(void(*Visit)(T&x));voidPostOrder(void(*Visit)(T&x));

protected:BTNode<T>*

;//指向根結(jié)點(diǎn)

private:intSize(BTNode<T>*t);voidClear(BTNode<T>*t);voidPreOrder(void(*Visit)(T&x),BTNode<T>*t);//私有函數(shù)，實(shí)現(xiàn)遍歷voidInOrder(void(*Visit)(T&x),BTNode<T>*t);voidPostOrder(void(*Visit)(T&x),BTNode<T>*t);};程序5.2二叉樹(shù)類root南京郵電大學(xué)計(jì)算機(jī)學(xué)院本小節(jié)中，我們主要實(shí)現(xiàn)MakeTree、BreakTree和Root運(yùn)算，而將二叉樹(shù)遍歷算法留待下一小節(jié)專門討論。Clear()函數(shù)釋放二叉鏈表中的所有結(jié)點(diǎn)，它需要通過(guò)遍歷二叉樹(shù)來(lái)實(shí)現(xiàn)。5.2.6實(shí)現(xiàn)二叉樹(shù)基本運(yùn)算南京郵電大學(xué)計(jì)算機(jī)學(xué)院程序5.3部分二叉樹(shù)運(yùn)算template<classT>boolBinaryTree<T>::Root(T&x)const//取根結(jié)點(diǎn)的數(shù)據(jù)值{if(root){x=root->element;returntrue;}elsereturnfalse;}ABCDEFroot南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>voidBinaryTree<T>::MakeTree(constT&x, BinaryTree<T>&left,BinaryTree<T>&right){if(root||&left==&right)return;root=newBTNode<T>(x,left.root,right.root);left.root=right.root=NULL;}DCEFBTNode(constT&x,BTNode<T>*l,BTNode<T>*r){element=x;lChild=l;rChild=r;}XleftrightnewBTNode<T>(x,left.root,right.root);函數(shù)功能：以x為根，left,right為左右子樹(shù)構(gòu)建一棵新二叉樹(shù)南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>voidBinaryTree<T>::BreakTree(T&x, BinaryTree<T>&left,BinaryTree<T>&right){if(!root||&left==&root||left.root||right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;deleteroot;root=NULL;}DCEFAleft.root→←right.rootroot=∧root函數(shù)功能：將二叉樹(shù)左右子樹(shù)拆分成二棵新的二叉樹(shù)，根結(jié)點(diǎn)刪除南京郵電大學(xué)計(jì)算機(jī)學(xué)院intmain(void){BinaryTree<char>a,b,x,y,z;chare;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('D',a,b);z.MakeTree('B',y,x);z.BreakTree(e,y,x);return0;}程序5.4main函數(shù)——一個(gè)測(cè)試程序abxyzEyCxFzDyBz南京郵電大學(xué)計(jì)算機(jī)學(xué)院ABDCEF5.3二叉樹(shù)的遍歷遍歷（traverse）一個(gè)有限結(jié)點(diǎn)的集合，意味著對(duì)該集合中的每個(gè)結(jié)點(diǎn)訪問(wèn)且僅訪問(wèn)一次。二叉樹(shù)遍歷算法:

(I)先左后右：VLR，LVR，LRV(II)先右后左：VRL，RVL，RLV-逆課堂提要第5章樹(shù)5.1樹(shù)的基本概念5.2二叉樹(shù)5.3二叉樹(shù)的遍歷5.5樹(shù)和森林5.7哈夫曼樹(shù)和哈夫曼編碼南京郵電大學(xué)計(jì)算機(jī)學(xué)院⑴先序遍歷（VLR）若二叉樹(shù)為空，則空操作；否則訪問(wèn)根結(jié)點(diǎn)；

先序遍歷左子樹(shù)；

先序遍歷右子樹(shù)。ABDCEF5.3.1二叉樹(shù)遍歷算法先序遍歷序列：ABDCEF

南京郵電大學(xué)計(jì)算機(jī)學(xué)院先序遍歷序列：ABDGHECF

t→t→t→t→t→t→t=∧t=∧t=∧t=∧t→t→t=∧t=∧t=∧ABCDEFGH任意一個(gè)先序遍歷序列中，根結(jié)點(diǎn)的位置在哪里？若二叉樹(shù)為空，則空操作；否則訪問(wèn)根結(jié)點(diǎn)；

先序遍歷左子樹(shù)；

先序遍歷右子樹(shù)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院⑵中序遍歷（LVR）若二叉樹(shù)為空，則空操作；否則中序遍歷左子樹(shù)；訪問(wèn)根結(jié)點(diǎn)；中序遍歷右子樹(shù)。

ABDCEF中序遍歷序列：BDAECF

南京郵電大學(xué)計(jì)算機(jī)學(xué)院中序遍歷ABCDEFGHIJK南京郵電大學(xué)計(jì)算機(jī)學(xué)院⑶后序遍歷（LRV）若二叉樹(shù)為空，則空操作；

否則

后序遍歷左子樹(shù)；

后序遍歷右子樹(shù)；

訪問(wèn)根結(jié)點(diǎn)。ABDCEF后序遍歷序列：DBEFCA

南京郵電大學(xué)計(jì)算機(jī)學(xué)院后序遍歷ABCDEFGHIJK南京郵電大學(xué)計(jì)算機(jī)學(xué)院層次遍歷ABCDEFGHIJK南京郵電大學(xué)計(jì)算機(jī)學(xué)院對(duì)于遍歷運(yùn)算，設(shè)計(jì)了一個(gè)面向用戶的公有成員函數(shù)和一個(gè)具體實(shí)現(xiàn)遍歷操作的遞歸私有成員函數(shù)，兩者共同完成遍歷運(yùn)算的功能。公有成員函數(shù)：非遞歸函數(shù)，作為與用戶的接口。它調(diào)用私有的遞歸函數(shù)。私有成員函數(shù)：遞歸函數(shù)，具體實(shí)現(xiàn)遍歷操作。被公有成員函數(shù)調(diào)用。5.3.2二叉樹(shù)遍歷的遞歸算法南京郵電大學(xué)計(jì)算機(jī)學(xué)院函數(shù)指針格式：函數(shù)返回類型(*函數(shù)指針名)(參數(shù)1，參數(shù)2…)#include<iostream.h>intmax(intx,inty){returnx>y?x:y;}intmin(intx,inty){returnx<y?x:y;}intadd(intx,inty){returnx+y;}voidprocess(intx,inty,int(*fun)(int,int)){intresult;result=fun(x,y);cout<<result<<endl;}intmain(void){intx=1,y=2;process(1,2,min);process(1,2,max);process(1,2,add);return0;}程序運(yùn)行結(jié)果：123指向函數(shù)的指針保存一個(gè)函數(shù)的入口地址。函數(shù)返回類型(*函數(shù)指針名)(參數(shù)1,參數(shù)2)int(*fun)(int,int)南京郵電大學(xué)計(jì)算機(jī)學(xué)院程序5.5訪問(wèn)元素函數(shù)template<classT>voidVisit(T&x){cout<<x<<"\t";}程序5.6先序遍歷template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x))//非遞歸函數(shù)，作為與用戶的接口，調(diào)用遞歸函數(shù){PreOrder(Visit,root);}template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x),BTNode<T>*t){if(t)//遞歸函數(shù)，實(shí)現(xiàn)遍歷{Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}注：1.函數(shù)名相同，但參數(shù)不同，不是同一個(gè)函數(shù)。2.使用函數(shù)指針(*Visit)(T&x)，只是為了增加程序的靈活性

南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>voidBinaryTree<T>::PreOrder(BTNode<T>*t){if(t){cout<<t->element;PreOrder(t->lChild);PreOrder(t->rChild);}}template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x),BTNode<T>*t){if(t)//遞歸函數(shù)，實(shí)現(xiàn)遍歷{Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}除去函數(shù)指針，以上遞歸的PreOrder函數(shù)可以簡(jiǎn)化為：南京郵電大學(xué)計(jì)算機(jī)學(xué)院CEFt->c{if(t){cout<<c

PreOrder(t->lChild);PreOrder(t->rChild);}}t->E{if(t){cout<<E

PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}t->F{if(t){cout<<F

PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}南京郵電大學(xué)計(jì)算機(jī)學(xué)院補(bǔ)充：中序遍歷template<classT>voidBinaryTree<T>::InOrder(void(*Visit)(T&x)){InOrder(Visit,root);}template<classT>voidBinaryTree<T>::InOrder(void(*Visit)(T&x),BTNode<T>*t){if(t){InOrder(Visit,t->lChild);

Visit(t->element);InOrder(Visit,t->rChild);}}南京郵電大學(xué)計(jì)算機(jī)學(xué)院補(bǔ)充：后序遍歷template<classT>voidBinaryTree<T>::PostOrder(void(*Visit)(T&x)){PostOrder(Visit,root);}template<classT>voidBinaryTree<T>::PostOrder(void(*Visit)(T&x),BTNode<T>*t){if(t){PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);

Visit(t->element);}}南京郵電大學(xué)計(jì)算機(jī)學(xué)院顯然，二叉樹(shù)遍歷算法基本操作是訪問(wèn)結(jié)點(diǎn)，不論按何種次序遍歷，對(duì)含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)間復(fù)雜度均為O(n)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院關(guān)于三種遍歷算法：1.給定一棵二叉樹(shù)，能寫出它的三種遍歷序列。2.給出二叉樹(shù)的先序遍歷序列和中序遍歷序列可以唯一確定一棵二叉樹(shù)。3.給出二叉樹(shù)的后序遍歷序列和中序遍歷序列可以唯一確定一棵二叉樹(shù)。4.當(dāng)n>1時(shí)，給出二叉樹(shù)的先序遍歷序列和后序遍歷序列不可以唯一確定一棵二叉樹(shù)。例如：先序序列：AB，后序序列：BA注意n>1的條件！例如：先序序列：A，后序序列：AAABAB南京郵電大學(xué)計(jì)算機(jī)學(xué)院例已知結(jié)點(diǎn)的先序序列和中序序列分別為：前序序列ABCDEFG中序序列CBEDAFG則可按上述分解求得整棵二叉樹(shù)。其構(gòu)造過(guò)程如下圖所示。首先由前序序列得知二叉樹(shù)的根為A，則其左子樹(shù)的中序序列為（CBED），又右子樹(shù)的中序序列為（FG）。反過(guò)來(lái)得知其左子樹(shù)的前序序列必為（BCDE），右子樹(shù)的前序序列為（FG）。類似地，可由左子樹(shù)的前序序列和中序序列構(gòu)造A的左子樹(shù)，由右子樹(shù)的前序序列和中序序列構(gòu)造得A的右子樹(shù)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.計(jì)算二叉樹(shù)的結(jié)點(diǎn)數(shù)程序5.7求二叉樹(shù)的結(jié)點(diǎn)數(shù)template<classT>intBinaryTree<T>::Size(){returnSize(root);}template<classT>intBinaryTree<T>::Size(BTNode<T>*t){if(!t)return0;returnSize(t->lChild)+Size(t->rChild)+1;}利用二叉樹(shù)遍歷思想可以解決許多二叉樹(shù)的應(yīng)用問(wèn)題。ABDCEF5.3.3二叉樹(shù)遍歷的應(yīng)用實(shí)例南京郵電大學(xué)計(jì)算機(jī)學(xué)院2.二叉樹(shù)復(fù)制程序5.8二叉樹(shù)復(fù)制template<classT>BTNode<T>*BinaryTree<T>::Copy(BTNode<T>*t){if(!root)returnNULL;BTNode<T>*q=newBTNode<T>(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);returnq;}ABDCEFtABDCEFq==>南京郵電大學(xué)計(jì)算機(jī)學(xué)院3.補(bǔ)充：Clear函數(shù)template<classT>voidBinaryTree<T>::Clear(BTNode<T>*t){if(t){Clear(t->lChild);Clear(t->rChild);cout<<"delete"<<t->element<<"..."<<endl;deletet;}}南京郵電大學(xué)計(jì)算機(jī)學(xué)院二叉樹(shù)在很多領(lǐng)域都有著廣泛的應(yīng)用——編譯原理中的表達(dá)式樹(shù)專家系統(tǒng)中的決策樹(shù)猜謎游戲的決策樹(shù)南京郵電大學(xué)計(jì)算機(jī)學(xué)院先序遍歷前綴表達(dá)式中序遍歷中綴表達(dá)式后序遍歷后綴表達(dá)式編譯原理中的表達(dá)式樹(shù)編譯原理中還用了語(yǔ)法樹(shù)(d)a*(b+c*d)/e/*+eb*ab*(c)a*(b+c)*aceb(b)a*b+c+*bca(a)a/b/ab南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.4二叉樹(shù)遍歷的非遞歸算法南京郵電大學(xué)計(jì)算機(jī)學(xué)院

前兩幾節(jié)中，我們已介紹了樹(shù)和森林的定義和概念，并對(duì)二叉樹(shù)作了詳細(xì)介紹，現(xiàn)在再回過(guò)頭來(lái)討論森林和二叉樹(shù)的轉(zhuǎn)換、樹(shù)或森林的存儲(chǔ)表示及其遍歷算法。5.5樹(shù)和森林課堂提要第5章樹(shù)5.1樹(shù)的基本概念5.2二叉樹(shù)5.3二叉樹(shù)的遍歷5.5樹(shù)和森林5.7哈夫曼樹(shù)和哈夫曼編碼南京郵電大學(xué)計(jì)算機(jī)學(xué)院為什么要將森林轉(zhuǎn)換為二叉樹(shù)

如果樹(shù)和森林能夠用二叉樹(shù)表示，則前面對(duì)二叉樹(shù)的討論成果可應(yīng)用于一般樹(shù)和森林。注意：樹(shù)和二叉樹(shù)的區(qū)別—二叉樹(shù)有左右孩子之分，而樹(shù)沒(méi)有左右孩子之分。5.5.1森林與二叉樹(shù)的轉(zhuǎn)換南京郵電大學(xué)計(jì)算機(jī)學(xué)院2.森林(Forest)轉(zhuǎn)換成二叉樹(shù)(BTree)可以將任何森林唯一地表示成一棵二叉樹(shù)。方法如下：(1)若F為空，則B為空二叉樹(shù)(2)若F非空，則B的根是F中第一棵子樹(shù)T1的根R1，B的左子樹(shù)是R1的子樹(shù)森林（T11，T12，…，T1m），B的右子樹(shù)是森林（T2，…，Tn）所對(duì)應(yīng)的二叉樹(shù)最后所形成的二叉樹(shù)就是森林所對(duì)應(yīng)的二叉樹(shù)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.樹(shù)(Tree)轉(zhuǎn)換為二叉樹(shù)(BTree)算法樹(shù)可以唯一地表示成一棵二叉樹(shù)：⑴兄弟手拉手----將樹(shù)中的兄弟用線連接；⑵斷絕非長(zhǎng)子之間的父子關(guān)系----對(duì)各結(jié)點(diǎn)，保留最左孩子的連線，去掉其余孩子的連線；⑶最后抖一抖----調(diào)整為習(xí)慣的二叉樹(shù)形(水平右斜，垂直左斜)。GDEFHJDEHFJG(a)樹(shù)(b)對(duì)應(yīng)的二叉樹(shù)5.5.1森林與二叉樹(shù)的轉(zhuǎn)換南京郵電大學(xué)計(jì)算機(jī)學(xué)院DEFGHJABCKDEFGHJABCKGACKGA==>CK==>再看一例⑴兄弟手拉手⑵斷絕非長(zhǎng)子之間的父子關(guān)系⑶最后抖一抖左孩子右兄弟樹(shù)轉(zhuǎn)換為二叉樹(shù)南京郵電大學(xué)計(jì)算機(jī)學(xué)院注意：⑴左孩子右兄弟。(樹(shù)→二叉樹(shù))

二叉樹(shù)中有兩個(gè)結(jié)點(diǎn)X和Y，且X是Y的雙親

⑵樹(shù)的根結(jié)點(diǎn)沒(méi)有兄弟，所以樹(shù)對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)沒(méi)有右子樹(shù)二叉樹(shù)中樹(shù)中Y是X左孩子Y是X孩子Y是X右孩子Y是X兄弟南京郵電大學(xué)計(jì)算機(jī)學(xué)院森林轉(zhuǎn)換成二叉樹(shù)的具體做法：１.將森林中各樹(shù)的根用線連起來(lái)，２.在樹(shù)中，凡是兄弟用線連起來(lái)--兄弟手拉手；３.去掉從雙親到除了第一個(gè)孩子以外的孩子的連線，只保留雙親到第一個(gè)孩子的連線--斷絕非長(zhǎng)子之間的父子關(guān)系；4.使之稍微傾斜成習(xí)慣的二叉樹(shù)形--最后抖一抖。其實(shí)，這里討論的森林是指有序森林，也可將一般的森林視為有序森林來(lái)對(duì)待。

5.5.1森林與二叉樹(shù)的轉(zhuǎn)換南京郵電大學(xué)計(jì)算機(jī)學(xué)院ABCFFDEGHJABCFFDEGHJABCFFDEGHJ森林轉(zhuǎn)換為二叉樹(shù)南京郵電大學(xué)計(jì)算機(jī)學(xué)院3.二叉樹(shù)轉(zhuǎn)換成森林(B→F)左孩子右兄弟ABCKDEFGHJADEHFJGBCK左孩子仍是孩子，右孩子變?yōu)樾值堋痢痢痢聊暇┼]電大學(xué)計(jì)算機(jī)學(xué)院一棵二叉樹(shù)B轉(zhuǎn)換成的森林中有多少棵樹(shù)？一棵二叉樹(shù)轉(zhuǎn)化成的森林中所具有的樹(shù)的數(shù)目，等于二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始沿右鏈到第一個(gè)沒(méi)有右孩子的結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)數(shù)目。ABECDFGHIJ經(jīng)過(guò)3個(gè)結(jié)點(diǎn)，故森林中3棵樹(shù)南京郵電大學(xué)計(jì)算機(jī)學(xué)院ABCDEFGHIJABCDEFGHIJ南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.多重鏈表表示法其中m是樹(shù)的度。每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)均為m，故又稱為等長(zhǎng)的多重鏈表。優(yōu)點(diǎn)：處理簡(jiǎn)單。 缺點(diǎn)：空指針域多，有浪費(fèi)。設(shè)樹(shù)中有n個(gè)結(jié)點(diǎn)，總共有n*m個(gè)指針域，其中，只有n-1個(gè)非空指針域，故空指針域個(gè)數(shù)為：n*m-(n-1)=n(m-1)+15.5.2樹(shù)和森林的存儲(chǔ)表示elementchild1child2……childm南京郵電大學(xué)計(jì)算機(jī)學(xué)院2.孩子兄弟表示法孩子兄弟(左子/右兄弟)表示法實(shí)質(zhì)上就是樹(shù)所對(duì)應(yīng)的二叉樹(shù)的二叉鏈表表示法。其每個(gè)結(jié)點(diǎn)為：leftChildelementrightSiblingDEFGHJDEFGHJ∧J∧∧G∧F

∧H∧E

D∧南京郵電大學(xué)計(jì)算機(jī)學(xué)院3.雙親表示法每個(gè)結(jié)點(diǎn)有兩個(gè)域：element和parent。parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)?？梢詫?duì)樹(shù)中結(jié)點(diǎn)按自上而下、自左向右(按層次)的次序順序存儲(chǔ)起來(lái)。思考：如何查找結(jié)點(diǎn)的雙親和孩子？012345DEFGHJ-100012elementparent順序存儲(chǔ)的雙親表示法DEFGHJ雙親表示法南京郵電大學(xué)計(jì)算機(jī)學(xué)院4.三重鏈表表示法優(yōu)點(diǎn)：可以很方便地得到節(jié)點(diǎn)的雙親和孩子信息。leftChildelementrightSiblingparentDEFGHJ∧J∧∧G

∧F

∧

H

∧

D

∧∧

E南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.帶右鏈的先序表示法數(shù)據(jù)元素有三個(gè)數(shù)據(jù)項(xiàng)，element,lTag,sibling。

1.sibling指向結(jié)點(diǎn)的兄弟

2.lTag為0表示有孩子，孩子存于相鄰單元lTag為1表示無(wú)孩子3.數(shù)據(jù)元素按對(duì)應(yīng)二叉樹(shù)的先序遍歷的順序存儲(chǔ)結(jié)點(diǎn)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院南京郵電大學(xué)計(jì)算機(jī)學(xué)院

1．按深度方向遍歷對(duì)森林的深度遍歷與二叉樹(shù)類似，根據(jù)樹(shù)的遞歸定義，可以有兩種遍歷次序：先序遍歷和中序遍歷。森林(F)對(duì)應(yīng)二叉樹(shù)(B)先序遍歷等價(jià)于先序遍歷中序遍歷等價(jià)于中序遍歷5.5.3樹(shù)和森林的遍歷南京郵電大學(xué)計(jì)算機(jī)學(xué)院

對(duì)上圖（a)的森林的先序遍歷的結(jié)果是：ABCKDEHFJG它等同于對(duì)(b)的二叉樹(shù)的先序遍歷。⑴先序遍歷

若森林為空，則遍歷結(jié)束。否則

a)訪問(wèn)第一棵樹(shù)的根；

b)按先序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)組成的森林；

c)按先序遍歷其余樹(shù)組成的森林。南京郵電大學(xué)計(jì)算機(jī)學(xué)院⑵中序遍歷若森林為空，則遍歷結(jié)束否則a)按中序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)組成的森林；b)訪問(wèn)第一棵樹(shù)的根；c)按中序遍歷其余樹(shù)組成的森林。南京郵電大學(xué)計(jì)算機(jī)學(xué)院2．按寬度方向遍歷首先訪問(wèn)處于第一層的結(jié)點(diǎn)，然后訪問(wèn)處于第二層的結(jié)點(diǎn)，再訪問(wèn)第三層，…，等，最后訪問(wèn)最下層的結(jié)點(diǎn)。對(duì)上圖的森林按寬度方向的遍歷結(jié)果是：ADBCEFGKHJ南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.6堆和優(yōu)先權(quán)隊(duì)列

堆是一種很有用的數(shù)據(jù)結(jié)構(gòu)，它可以用于高效地實(shí)現(xiàn)優(yōu)先權(quán)隊(duì)列。

優(yōu)先權(quán)隊(duì)列中的元素，按其優(yōu)先級(jí)的高低而不是按元素進(jìn)入隊(duì)列的次序，來(lái)確定出隊(duì)列的次序。南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.6.1堆

一個(gè)大小為n的堆是一棵包含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，該樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于等于其雙親結(jié)點(diǎn)的關(guān)鍵字值。完全二叉樹(shù)的根稱為堆頂。它的關(guān)鍵字值是整棵樹(shù)上最小的。這樣定義的堆稱為最小堆。也可構(gòu)建最大堆。012345堆底堆頂南京郵電大學(xué)計(jì)算機(jī)學(xué)院最小堆的特點(diǎn)：堆頂元素是整個(gè)堆的最小元素南京郵電大學(xué)計(jì)算機(jī)學(xué)院（2）最小堆的另一定義當(dāng)完全二叉樹(shù)以順序方式存儲(chǔ)時(shí)，實(shí)際上得到的是結(jié)點(diǎn)序列，所以最小堆又可以定義為：堆是n個(gè)元素的序列（k0,k1,…,kn-1），當(dāng)且僅當(dāng)滿足kik2i+1且kik2i+2,(i=0,1,2,…,(n-2)/2)時(shí)稱為最小堆。例１：判斷序列（23，53，34，65，83，74）是最小堆嗎

南京郵電大學(xué)計(jì)算機(jī)學(xué)院例２：判斷序列（23，98，34，65，83，74）是最小堆嗎？

98南京郵電大學(xué)計(jì)算機(jī)學(xué)院如何將給定的任意序列調(diào)整成最小堆？1.將序列寫成堆（完全二叉樹(shù)）的形式2.將堆調(diào)整為最小堆。整個(gè)調(diào)整過(guò)程：從下標(biāo)（n-2）/2處的元素開(kāi)始，調(diào)整（n-2）/2到0的每個(gè)元素。在每個(gè)元素調(diào)整的過(guò)程中，要逐個(gè)判斷每個(gè)元素是否滿足最小堆的條件，（即當(dāng)前元素的值要小于等于孩子），若不滿足則此元素向下調(diào)整，即此元素要與左右孩子中的小者交換，交換后再與它的左右孩子中的小者比較，若不滿足條件則再交換，直到不再需要調(diào)整。南京郵電大學(xué)計(jì)算機(jī)學(xué)院例１：一個(gè)元素92向下調(diào)整的過(guò)程南京郵電大學(xué)計(jì)算機(jī)學(xué)院例2:將序列(36,91,24,12,47,30,52,85）調(diào)整為最小堆

2６４３１０７５從（n-2）/2處的元素開(kāi)始，調(diào)整（n-2）/2到0的每個(gè)元素。南京郵電大學(xué)計(jì)算機(jī)學(xué)院1南京郵電大學(xué)計(jì)算機(jī)學(xué)院０南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>voidAdjustDown(Theap[],intr,intj){//對(duì)下標(biāo)為r的元素調(diào)整，使其滿足最小堆的條件intchild=2*r+1;//child是r的左孩子Ttemp=heap[r];while(child<=j){if((child<j)&&(heap[child]>heap[child+1]))child++;//child指向左右孩子中的小者if(temp<=heap[child])break;heap[(child-1)/2]=heap[child];child=2*child+1;}heap[(child-1)/2]=temp;}程序中包含temp<=heap[child]的元素比較要求元素類型Ｔ已實(shí)現(xiàn)從元素類型Ｔ到可比較類型關(guān)鍵字的轉(zhuǎn)換，重載類型轉(zhuǎn)換符可實(shí)現(xiàn)這種轉(zhuǎn)換child//孩子上移到雙親的位置childr南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>voidAdjustDown(Theap[],intr,intj){//對(duì)下標(biāo)為r的元素調(diào)整，使其滿足最小堆的條件intchild=2*r+1;//child是r的左孩子Ttemp=heap[r];while(child<=j){if((child<j)&&(heap[child]>heap[child+1]))child++;//child指向左右孩子中的小者if(temp<=heap[child])break;heap[(child-1)/2]=heap[child];child=2*child+1;}heap[(child-1)/2]=temp;}程序中包含temp<=heap[child]的元素比較要求元素類型Ｔ已實(shí)現(xiàn)從元素類型Ｔ到可比較類型關(guān)鍵字的轉(zhuǎn)換，重載類型轉(zhuǎn)換符可實(shí)現(xiàn)這種轉(zhuǎn)換child//孩子上移到雙親的位置childr南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>voidCreateHeap(Theap[],intn){for(inti=(n-2)/2;i>-1;i--)AdjustDown(heap,i,n-1)；}建堆的時(shí)間為O(nlog2n)。更深入分析可知，建堆時(shí)間復(fù)雜度為O(n)。

r0123456789此例從下標(biāo)（n-2）/2開(kāi)始調(diào)整此函數(shù)功能是建立最小堆，它通過(guò)從第（n-2）/2位置開(kāi)始，直到第一個(gè)元素，重復(fù)調(diào)用AdjustDown函數(shù)實(shí)現(xiàn)之。南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.6.2優(yōu)先權(quán)隊(duì)列ADT

1．優(yōu)先權(quán)隊(duì)列優(yōu)先權(quán)隊(duì)列不同于先進(jìn)先出（FIFO）隊(duì)列，優(yōu)先權(quán)隊(duì)列中的元素，按其優(yōu)先級(jí)的高低而不是按元素進(jìn)入隊(duì)列的次序，來(lái)確定出隊(duì)列的次序。最小值為最高優(yōu)先權(quán)。優(yōu)先級(jí)的最高的元素放在隊(duì)首，最先出隊(duì)。2．堆是實(shí)現(xiàn)優(yōu)先權(quán)隊(duì)列的有效的數(shù)據(jù)結(jié)構(gòu)。

南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.6.2優(yōu)先權(quán)隊(duì)列ADTADTPrioQueue{數(shù)據(jù)：n0個(gè)元素的最小堆。運(yùn)算：Create()：建立一個(gè)空隊(duì)列。Destroy()：撤消一個(gè)隊(duì)列。IsEmpty()：若隊(duì)列空，則返回true；否則返回false。IsFull()：若隊(duì)列滿，則返回true；否則返回falseAppend(x):元素值為x的新元素入隊(duì)列。

Serve(x):在x中返回具有最高優(yōu)先權(quán)的元素值,并從優(yōu)先權(quán)隊(duì)列中刪除該元素。}

南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.6.3優(yōu)先權(quán)隊(duì)列類template<classT>classPrioQueue{public: PrioQueue(intmSize=20); ~PrioQueue(){delete[]q;}; boolIsEmpty()const{returnn==0;} boolIsFull()const{returnn==maxSize;} voidAppend(constT&x); voidServe(T&x);private: voidAdjustDown(intr,intj); voidAdjustUp(intj);

T*q;

intn,maxSize;};南京郵電大學(xué)計(jì)算機(jī)學(xué)院優(yōu)先權(quán)隊(duì)列的構(gòu)造函數(shù)和析構(gòu)函數(shù)template<classT>PriorityQueue<T>::PriorityQueue(intmQSize){maxSize=mSize;n=0;q=newT[maxSize];}~PriorityQueue(){delete[]q;};南京郵電大學(xué)計(jì)算機(jī)學(xué)院

優(yōu)先權(quán)隊(duì)列中插入一個(gè)新元素的算法步驟：

1.首先將新元素插入到優(yōu)先權(quán)隊(duì)列的最后

2.插入元素后，此隊(duì)列應(yīng)保持優(yōu)先權(quán)隊(duì)列的特點(diǎn)，所以，當(dāng)新元素不滿足條件時(shí)，須進(jìn)行調(diào)整，調(diào)整過(guò)程是由下向上，與雙親結(jié)點(diǎn)比較，若雙親結(jié)點(diǎn)大則新元素上浮，雙親結(jié)點(diǎn)下沉。

注：這一過(guò)程中與５.６.１節(jié)堆中的AdjustDown相反的比較路徑

南京郵電大學(xué)計(jì)算機(jī)學(xué)院例１：向優(yōu)先權(quán)隊(duì)列中插入一個(gè)新元素２４南京郵電大學(xué)計(jì)算機(jī)學(xué)院AdjustUp函數(shù)AdjustUp(intj)設(shè)數(shù)組中0到j(luò)-1，這j個(gè)位置上的元素已滿足kik2i+1且kik2i+2,(i=0，1,2,…,（n-2）/2)條件，運(yùn)行AdjustUp(intj)將使得增加一個(gè)元素q[j],這0-j個(gè)元素也滿足堆的特性。南京郵電大學(xué)計(jì)算機(jī)學(xué)院AdjustUp函數(shù)template<classT>voidPriorityQueue<T>::AdjustUp(intj){//將新元素q[j]向上調(diào)整inti=j;Ttemp=q[i];while(i>0&&temp<q[(i-1)/2]){ q[i]=q[(i-1)/2];//雙親下移 i=(i-1)/2;//i上移}q[i]=temp;}iii南京郵電大學(xué)計(jì)算機(jī)學(xué)院Append和Serve函數(shù)

template<classT>voidPriorityQueue<T>::Append(constT&x)//插入新元素到優(yōu)先權(quán)隊(duì)列中{if(IsFull()){cerr<<"OverFlow"<<endl;exit(1);}q[n++]=x;AdjustUp(n-1);}0１３５４２南京郵電大學(xué)計(jì)算機(jī)學(xué)院從空隊(duì)列開(kāi)始，依此向隊(duì)列中插入元素的過(guò)程南京郵電大學(xué)計(jì)算機(jī)學(xué)院

設(shè)從空隊(duì)列開(kāi)始，依此向隊(duì)列中插入元素：71，74，2，72，54，93，52，28，則每次插入后隊(duì)列的狀態(tài)如下表南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>voidPriorityQueue<T>::Serve(T&x){if(IsEmpty()){cerr<<"UnderFlow"<<endl;exit(1);}x=q[0];q[0]=q[--n];

AdjustDown(0,n-1);}0１３５４２66５４３２0１7南京郵電大學(xué)計(jì)算機(jī)學(xué)院Append和Serve函數(shù)的時(shí)間

容易分析優(yōu)先權(quán)隊(duì)列的插入和刪除運(yùn)算的時(shí)間復(fù)雜度。由于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為

log2

(n+1)，所以AdjustDown和AdjustUp兩個(gè)算法中，比較和移動(dòng)元素的次數(shù)均不會(huì)超過(guò)該高度。Append和Serve運(yùn)算分別用一常數(shù)階調(diào)用上述兩個(gè)運(yùn)算，所以它們的時(shí)間復(fù)雜度為O(log2n)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院

本節(jié)將討論：

樹(shù)的路徑長(zhǎng)度哈夫曼樹(shù)和哈夫曼算法5.7哈夫曼樹(shù)和哈夫曼編碼課堂提要第5章樹(shù)5.1樹(shù)的基本概念5.2二叉樹(shù)5.3二叉樹(shù)的遍歷5.5樹(shù)和森林5.7哈夫曼樹(shù)和哈夫曼編碼南京郵電大學(xué)計(jì)算機(jī)學(xué)院定義5.7從根到樹(shù)中任意結(jié)點(diǎn)的路徑長(zhǎng)度是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上所包括的邊的數(shù)目。

5.7.1樹(shù)的路徑長(zhǎng)度路徑(path)：從某個(gè)結(jié)點(diǎn)沿樹(shù)中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。E和N之間存在一條路徑。EAFGBCDLJMNEAFGBCDLJMN南京郵電大學(xué)計(jì)算機(jī)學(xué)院定義5.8如果葉子結(jié)點(diǎn)是帶權(quán)的，則葉子結(jié)點(diǎn)的加權(quán)路徑長(zhǎng)度是從根到該葉子的路徑長(zhǎng)度與葉子的權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的加權(quán)路徑長(zhǎng)度之和，記作其中，m是葉子結(jié)點(diǎn)的個(gè)數(shù)，wk是第k個(gè)葉子結(jié)點(diǎn)的權(quán)，lk是該葉子結(jié)點(diǎn)的路徑長(zhǎng)度。南京郵電大學(xué)計(jì)算機(jī)學(xué)院(1)WPL=2*2+1*3+2*3+6*1=19(2)WPL=2*2+6*3+2*3+1*1=29南京郵電大學(xué)計(jì)算機(jī)學(xué)院一般地，權(quán)越大的葉子離根越近，則二叉樹(shù)的加權(quán)路徑長(zhǎng)度越小。哈夫曼給出了求具有最小加權(quán)路徑長(zhǎng)度二叉樹(shù)的算法，稱為哈夫曼算法。用哈夫曼算法構(gòu)造的二叉樹(shù)稱為哈夫曼樹(shù)。5.7.2哈夫曼樹(shù)和哈夫曼算法南京郵電大學(xué)計(jì)算機(jī)學(xué)院哈夫曼算法可以描述如下：⑴用給定的一組權(quán)值{w1,w2,…,wn}生成一個(gè)森林F={T1，T2，…，Tn},其中每棵二叉樹(shù)Ti只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)均為空。⑵從F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為新樹(shù)根的左、右子樹(shù)，新樹(shù)根的權(quán)值是左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和。(約定左子樹(shù)根權(quán)值小)⑶從F中刪除這兩棵樹(shù)，另將新二叉樹(shù)加入F中。⑷重復(fù)⑵和⑶，直到F中只包含一棵樹(shù)為止。此樹(shù)即為哈夫曼樹(shù)。（重復(fù)執(zhí)行幾次？）南京郵電大學(xué)計(jì)算機(jī)學(xué)院構(gòu)造哈夫曼樹(shù)的過(guò)程(約定左小右大)重復(fù)執(zhí)行幾次？南京郵電大學(xué)計(jì)算機(jī)學(xué)院⑵W={3，5，9，11，12，13}南京郵電大學(xué)計(jì)算機(jī)學(xué)院構(gòu)造哈夫曼樹(shù)的步驟：

1.準(zhǔn)備工作：首先構(gòu)造n棵哈夫曼樹(shù)對(duì)象，每棵樹(shù)只有一個(gè)權(quán)值為w[i]的根結(jié)點(diǎn)，且該對(duì)象的weight為w[i]，將它們逐一加入優(yōu)先權(quán)隊(duì)列。２.構(gòu)建哈夫曼樹(shù)：從優(yōu)先權(quán)隊(duì)列中取出兩棵根結(jié)點(diǎn)值最小和次最小的哈夫曼樹(shù)x和y。以它們根的權(quán)值之和為根的權(quán)值，x和y為左、右子樹(shù)構(gòu)造一棵新哈夫曼樹(shù)，并將新樹(shù)對(duì)象進(jìn)優(yōu)先權(quán)隊(duì)列。重復(fù)執(zhí)行n-1次，此時(shí)，隊(duì)列中只剩下合并完成的哈夫曼樹(shù)。３.從隊(duì)列中取出構(gòu)造完畢的哈夫曼樹(shù)，函數(shù)返回該哈夫曼樹(shù)。⑵W={3，5，9，11，12，13}南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.7.3

哈夫曼樹(shù)類template<classT>classHfmTree:publicBinaryTree<T>{public:

operatorT()const{returnweight;}//重載類型轉(zhuǎn)換運(yùn)算符，為了方便優(yōu)先權(quán)隊(duì)列中，對(duì)象間的比較 TgetW(){returnweight;} voidputW(constT&x){weight=x;}SetNull(){root=NULL;}private:

Tweight;};南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.7.4

構(gòu)造哈夫曼樹(shù)HfmTree<T>CreateHfmTree(Tw[],intn)設(shè)數(shù)組w[]中保存n個(gè)元素類型為T的權(quán)值，函數(shù)返回一棵構(gòu)造成功的哈夫曼樹(shù)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院template<classT>HfmTree<T>CreateHfmTree(Tw[],intn){PrioQueue<HfmTree<T>>pq(n);

//空優(yōu)先權(quán)隊(duì)列HfmTree<T>x,y,z,zero;//空哈夫曼樹(shù)for(inti=0;i<n;i++){//初始化z.MakeTree(w[i],x,y);//構(gòu)造只有一個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)對(duì)象

z.putW(w[i]);//將W[i]的值寫入wight域pq.Append(z);//將哈夫曼樹(shù)對(duì)象加入優(yōu)先權(quán)隊(duì)列z.SetNull();//將z置空 }for(i=1;i<n;i++){ pq.Serve(x);//取出根結(jié)點(diǎn)權(quán)值最小的哈夫曼樹(shù)對(duì)象pq.Serve(y);/取出根結(jié)點(diǎn)權(quán)值次小的哈夫曼樹(shù)對(duì)象

z.MakeTree(x.getW()+y.getW(),x,y); z.putW(x.getW()+y.getW()); pq.Append(z); z.SetNull();}pq.Serve(z);returnz;}

W={3，5，9，11，12，13}南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.等長(zhǎng)編碼

A:00,B:01,C:10,D:11.

電文：ABACABDA.編碼：0001001000011100

譯碼：兩位一個(gè)字符。ASCII編碼是等長(zhǎng)編碼。2.不等長(zhǎng)編碼

A:0,B:01,C:10,D:101.

電文：ABACABDA.編碼：0010100011010

譯碼：產(chǎn)生二義性。原因：一個(gè)字符的編碼是另一個(gè)字符編碼的前綴。前綴編碼：一個(gè)字符的編碼不是另一個(gè)字符編碼的前綴。5.7.5哈夫曼編碼南京郵電大學(xué)計(jì)算機(jī)學(xué)院可以利用哈夫曼樹(shù)得到前綴編碼，即哈夫曼編碼。

方法如下：1.用權(quán)值構(gòu)造哈夫曼樹(shù)2.約定左分支為0，右分支為1。3.哈夫曼編碼電文：

ABF編碼：1100110110

即左0右1南京郵電大學(xué)計(jì)算機(jī)學(xué)院5.8并查集與等價(jià)關(guān)系

首