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

第5章樹引言樹形結(jié)構(gòu)是元素之間具有分層關(guān)系的結(jié)構(gòu)，它類似于自然界中的樹，應(yīng)用廣泛，是一類很重要的非線性數(shù)據(jù)結(jié)構(gòu)。在計(jì)算機(jī)應(yīng)用中，常出現(xiàn)嵌套的數(shù)據(jù)，樹結(jié)構(gòu)提供了對(duì)該類數(shù)據(jù)的自然表示；利用樹結(jié)構(gòu)，可以有效地解決一些算法問(wèn)題。由于結(jié)構(gòu)特征，樹形結(jié)構(gòu)常采用遞歸方式定義。被稱為遞歸數(shù)據(jù)結(jié)構(gòu)。有關(guān)樹的許多算法是遞歸的。數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE南京郵電大學(xué)計(jì)算機(jī)學(xué)院內(nèi)容提要1、樹的基本概念；給出樹的定義，關(guān)于樹中的一些術(shù)語(yǔ)；2、二叉樹的定義、性質(zhì)及其規(guī)范；3、二叉樹的遍歷等算法的實(shí)現(xiàn)；4、樹和森林的表示、存儲(chǔ)和遍歷；5、二叉樹的應(yīng)用實(shí)例——哈夫曼樹和哈夫曼編碼。南京郵電大學(xué)計(jì)算機(jī)學(xué)院層次結(jié)構(gòu)的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。國(guó)家、省、市、縣和區(qū)。書的章節(jié)、回目。上級(jí)和下級(jí)。整體和部分。祖先和后裔。5.1樹的基本概念5.1.1樹的定義課堂提要第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的遍歷5.5樹和森林5.7哈夫曼樹和哈夫曼編碼南京郵電大學(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é)院樹形結(jié)構(gòu)操作系統(tǒng)的目錄結(jié)構(gòu)南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.樹的定義定義5.1有根數(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為樹的根。（2）除根r以外的所有結(jié)點(diǎn)u∈D，都有且僅有一個(gè)結(jié)點(diǎn)v∈D，v≠u，使得<v,u>∈R。這樣定義的樹也稱有根樹，簡(jiǎn)稱樹。樹不為空集合，樹中至少有一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前驅(qū)，其余結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)。因此樹形成層次結(jié)構(gòu)。南京郵電大學(xué)計(jì)算機(jī)學(xué)院2.樹的遞歸定義定義5.2

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

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)沿樹中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。E和N之間存在一條路徑。根結(jié)點(diǎn)和它的子樹根（如果存在）之間形成一條邊。路徑(path)：從某個(gè)結(jié)點(diǎn)沿樹中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。E和N之間存在一條路徑。EAFGBCDLJMN路徑(path)：從某個(gè)結(jié)點(diǎn)沿樹中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。E和N之間存在一條路徑。南京郵電大學(xué)計(jì)算機(jī)學(xué)院雙親(parent)：若一個(gè)結(jié)點(diǎn)有子樹，那么該結(jié)點(diǎn)稱為子樹根的雙親。A、F、B的雙親是E。C、D的雙親是F。孩子(child)：某結(jié)點(diǎn)子樹的根是該結(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)的所有子樹上的任何結(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ù)。結(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)。樹的度：樹中結(jié)點(diǎn)的最大的度。該樹的度為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。樹的高度：樹中結(jié)點(diǎn)的最大層次?！邩渲薪Y(jié)點(diǎn)的最大層次為5。∴樹的高度為5。12345EAFGBCDLJMN南京郵電大學(xué)計(jì)算機(jī)學(xué)院AG無(wú)序樹：如果樹中結(jié)點(diǎn)的各子樹之間的次序是不重要的，可以交換位置。下列是同一棵無(wú)序樹：將左邊樹中所有結(jié)點(diǎn)的子樹互換次序就是右邊的樹。EAFGBCDLJMNEFBCDLJNM南京郵電大學(xué)計(jì)算機(jī)學(xué)院有序樹：如果樹中結(jié)點(diǎn)的各棵子樹看成是從左到右有次序的，則稱該樹為有序樹。有序樹的各子樹從左到右為第一棵子樹、第二棵，…如果下列是有序樹，則二者是二棵不同的樹AGEAFGBCDLJMNEFBCDLJNM南京郵電大學(xué)計(jì)算機(jī)學(xué)院森林：是樹的集合。0個(gè)或多個(gè)不相交的樹組成森林。果園或有序森林：有序樹的有序集合。森林與樹只有很小的差別，若將樹中的根去掉，則得到根的子樹組成的森林。BEAGFCDLJMNE若增加一個(gè)結(jié)點(diǎn)，將森林中各樹的根作為新增結(jié)點(diǎn)的孩子，則森林即成為樹。南京郵電大學(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*(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ù)據(jù)結(jié)構(gòu)。很多從實(shí)際問(wèn)題中抽象出來(lái)的數(shù)據(jù)是二叉樹形的；以后我們將看到任意樹或森林可方便地轉(zhuǎn)換成二叉樹，從而為一般樹和森林的存儲(chǔ)和處理提供了有效方法。5.2二叉樹課堂提要第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的遍歷5.5樹和森林5.7哈夫曼樹和哈夫曼編碼南京郵電大學(xué)計(jì)算機(jī)學(xué)院方法二：改進(jìn)結(jié)構(gòu)，組織成樹形結(jié)構(gòu)。比較次數(shù)不會(huì)超過(guò)樹高，提高了效率。先看一個(gè)二叉樹應(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

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

log2

(n+1)

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

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

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

5.2.3二叉樹ADT南京郵電大學(xué)計(jì)算機(jī)學(xué)院1.完全二叉樹的順序表示完全二叉樹中的結(jié)點(diǎn)可以按層次順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中。根結(jié)點(diǎn)保存在編號(hào)為0的位置上。注意：一般的二叉樹不適合用這種存儲(chǔ)結(jié)構(gòu)。01234567890123456789圖6.5圖6.4(b)完全二叉樹的順序表示0123456789圖6.4(b)完全二叉樹5.2.4二叉樹的存儲(chǔ)表示南京郵電大學(xué)計(jì)算機(jī)學(xué)院element2.二叉樹的鏈接表示ABCDEFAB^C^D^^E^^F^(a)二叉樹 (b)二叉樹的鏈接表示圖6-6二叉樹的鏈接表示lChildrChild二叉樹的二叉鏈表結(jié)構(gòu)有利于從雙親到孩子方向的訪問(wèn)。采取從根開始，遍歷整個(gè)二叉樹。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//樹結(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二叉樹類南京郵電大學(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二叉樹類root南京郵電大學(xué)計(jì)算機(jī)學(xué)院本小節(jié)中，我們主要實(shí)現(xiàn)MakeTree、BreakTree和Root運(yùn)算，而將二叉樹遍歷算法留待下一小節(jié)專門討論。Clear()函數(shù)釋放二叉鏈表中的所有結(jié)點(diǎn)，它需要通過(guò)遍歷二叉樹來(lái)實(shí)現(xiàn)。5.2.6實(shí)現(xiàn)二叉樹基本運(yùn)算南京郵電大學(xué)計(jì)算機(jī)學(xué)院程序5.3部分二叉樹運(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為左右子樹構(gòu)建一棵新二叉樹南京郵電大學(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ù)功能：將二叉樹左右子樹拆分成二棵新的二叉樹，根結(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二叉樹的遍歷遍歷（traverse）一個(gè)有限結(jié)點(diǎn)的集合，意味著對(duì)該集合中的每個(gè)結(jié)點(diǎn)訪問(wèn)且僅訪問(wèn)一次。二叉樹遍歷算法:

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

先序遍歷左子樹；

先序遍歷右子樹。ABDCEF5.3.1二叉樹遍歷算法先序遍歷序列：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)的位置在哪里？若二叉樹為空，則空操作；否則訪問(wèn)根結(jié)點(diǎn)；

先序遍歷左子樹；

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

ABDCEF中序遍歷序列：BDAECF

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

否則

后序遍歷左子樹；

后序遍歷右子樹；

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

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

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

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

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

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

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

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

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

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

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

c)按先序遍歷其余樹組成的森林。南京郵電大學(xué)計(jì)算機(jī)學(xué)院⑵中序遍歷若森林為空，則遍歷結(jié)束否則a)按中序遍歷第一棵樹的根結(jié)點(diǎn)的子樹組成的森林；b)訪問(wèn)第一棵樹的根；c)按中序遍歷其余樹組成的森林。南京郵電大學(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)的完全二叉樹，該樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于等于其雙親結(jié)點(diǎn)的關(guān)鍵字值。完全二叉樹的根稱為堆頂。它的關(guān)鍵字值是整棵樹上最小的。這樣定義的堆稱為最小堆。也可構(gòu)建最大堆。012345堆底堆頂南京郵電大學(xué)計(jì)算機(jī)學(xué)院最小堆的特點(diǎn)：堆頂元素是整個(gè)堆的最小元素南京郵電大學(xué)計(jì)算機(jī)學(xué)院（2）最小堆的另一定義當(dāng)完全二叉樹以順序方式存儲(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.將序列寫成堆（完全二叉樹）的形式2.將堆調(diào)整為最小堆。整個(gè)調(diào)整過(guò)程：從下標(biāo)（n-2）/2處的元素開始，調(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處的元素開始，調(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開始調(diào)整此函數(shù)功能是建立最小堆，它通過(guò)從第（n-2）/2位置開始，直到第一個(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ì)列開始，依此向隊(duì)列中插入元素的過(guò)程南京郵電大學(xué)計(jì)算機(jī)學(xué)院

設(shè)從空隊(duì)列開始，依此向隊(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)的完全二叉樹的高度為

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é)將討論：

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

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

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

哈夫曼樹類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)造哈夫曼樹HfmTree<T>CreateHfmTree(Tw[],intn)設(shè)數(shù)組w[]中保存n個(gè)元素類型為T的權(quán)值，函數(shù)返回一棵構(gòu)造成功的哈夫曼樹。南京郵電大學(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;//空哈夫曼樹for(inti=0;i<n;i++){//初始化z.MakeTree(w[i],x,y);//構(gòu)造只有一個(gè)結(jié)點(diǎn)的哈夫曼樹對(duì)象

z.putW(w[i]);//將W[i]的值寫入wight域pq.Append(z);//將哈夫曼樹對(duì)象加入優(yōu)先權(quán)隊(duì)列z.SetNull();//將z置空 }for(i=1;i<n;i++){ pq.Serve(x);//取出根結(jié)點(diǎn)權(quán)值最小的哈夫曼樹對(duì)象pq.Serve(y);/取出根結(jié)點(diǎn)權(quán)值次小的哈夫曼樹對(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é)院可以利用哈夫曼樹得到前綴編碼，即哈夫曼編碼。

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

ABF編碼：1100110110

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

首