《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程(C語(yǔ)言版)》第5章樹.ppt

,數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語(yǔ)言版） 中國(guó)水利水電出版社,第5章 樹,本章中主要介紹下列內(nèi)容： 樹的邏輯定義和存儲(chǔ)結(jié)構(gòu) 二叉樹的邏輯定義、存儲(chǔ)結(jié)構(gòu) 二叉樹的基本操作算法 樹和二叉樹的轉(zhuǎn)換 哈夫曼樹及其應(yīng)用,本章目錄,結(jié)束,5.1 樹,5.1.1 樹的定義 5.1.2 樹的表示方法 5.1.3 樹的基本術(shù)語(yǔ) 5.1.4 樹的存儲(chǔ)結(jié)構(gòu),返回到總目錄,5.1.1 樹的定義,樹是n（n0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)稱為空樹。當(dāng)n0時(shí)，是非空樹，它滿足以下兩個(gè)條件： （1）有且僅有一個(gè)稱為根的結(jié)點(diǎn)； （2）其余結(jié)點(diǎn)分為m（m0）個(gè)互不相交的非空集合T1，T2，Tm，其中每個(gè)集合本身又是一棵樹，稱為根的子樹。,返回到本節(jié)目錄,樹的二元組表示法,樹可用二元組來(lái)表示。其中，D為結(jié)點(diǎn)集合，R為邊的集合。一棵樹T如圖5-1所示，則它的二元組表示方法為： T=（D,R） D=A,B,C,D,E,F,G,H R=,圖5-1 樹的邏輯結(jié)構(gòu)圖,返回到本節(jié)目錄,5.1.2樹的表示方法,樹的邏輯結(jié)構(gòu)表示有樹形表示法，文氏圖表示法，凹入表示法和廣義表表示法等。 1樹形表示法 這是樹的最基本的表示，使用一棵倒置的樹表示樹結(jié)構(gòu)。圖5-1就是采用這種方法。 2文氏表示法 使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。圖5-2（a）就是圖5-1的樹的文氏圖表示法。 3凹入表示法 使用線段的伸縮關(guān)系描述樹的結(jié)構(gòu)。圖5-2（b）就是圖5-1的樹的凹入表示法。 4廣義表表示法 將樹的根結(jié)點(diǎn)寫在括號(hào)的左邊，除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)寫在括號(hào)內(nèi)并用逗號(hào)間隔來(lái)描述樹的結(jié)構(gòu)。圖5-2（c）就是圖5-1的樹的廣義表表示法。,返回到本節(jié)目錄,樹的三種表示方法,(a)文氏圖表示法 (b)凹入圖表示法 (c)廣義表表示法 圖5-2 樹的其它表示方法,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語(yǔ),1結(jié)點(diǎn) 樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。 2結(jié)點(diǎn)的度 結(jié)點(diǎn)所擁有的分支數(shù)目或后繼結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的度（Degree）。例如圖5-1所示的樹中結(jié)點(diǎn)A的度為3，結(jié)點(diǎn)C的度為2，結(jié)點(diǎn)E的度為0。 3樹的度 樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。例如圖5-1所示的樹的度為3。 4葉子（終端結(jié)點(diǎn)） 度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。例如圖5-1所示的樹中結(jié)點(diǎn)E、G、H、I為葉子結(jié)點(diǎn)。,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語(yǔ),5分支結(jié)點(diǎn) 度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。例如圖5-1所示的樹中的A、B、C、D、F都是分支結(jié)點(diǎn)。 6孩子結(jié)點(diǎn) 一個(gè)結(jié)點(diǎn)的后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。例如圖5-1所示的樹中A的孩子結(jié)點(diǎn)為B、C、D。 7雙親結(jié)點(diǎn) 一個(gè)結(jié)點(diǎn)稱其為其后繼結(jié)點(diǎn)的雙親結(jié)點(diǎn)。例如圖5-1所示的樹中A是B、C、D的雙親結(jié)點(diǎn)，C是F、G的雙親。 8兄弟結(jié)點(diǎn) 同一雙親結(jié)點(diǎn)下的孩子結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)。例如圖5-1所示的樹中B、C、D互為兄弟結(jié)點(diǎn)， F、G互為兄弟結(jié)點(diǎn)，但不同雙親的兩個(gè)同層結(jié)點(diǎn)不互為兄弟結(jié)點(diǎn)，如G和H不互為兄弟結(jié)點(diǎn)。,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語(yǔ),9堂兄弟 雙親互為兄弟的兩個(gè)結(jié)點(diǎn)互稱為堂兄弟。例如圖5-1所示的樹中G和H就互為堂兄弟。 10子孫結(jié)點(diǎn) 一個(gè)結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)稱之為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。例如圖5-1所示的樹中A的子孫為B、C、D、E、F、G、H、I。 11祖先結(jié)點(diǎn) 從樹根結(jié)點(diǎn)到達(dá)一個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。例如圖5-1所示的樹中E的祖先結(jié)點(diǎn)為A和B（包括其雙親結(jié)點(diǎn)B）。,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語(yǔ),12層數(shù) 樹的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它雙親結(jié)點(diǎn)的層數(shù)加1。例如圖5-1所示的樹中A的層數(shù)為1，B、C、D的層數(shù)為2，E、F、G、H的層數(shù)為3，I的層數(shù)為4。 13樹的深度 樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的深度（或高度）。例如圖5-1所示的樹中的深度為4。 14有序樹和無(wú)序樹 如果一棵樹中的結(jié)點(diǎn)的各子樹從左到右是有次序的，即若交換了某結(jié)點(diǎn)各子樹的相對(duì)位置，則構(gòu)成了不同的樹，稱這樣的樹為有序樹，反之，則為無(wú)序樹。 15森林 m（m0）棵互不相交樹的集合稱為森林。,返回到本節(jié)目錄,5.1.4 樹的存儲(chǔ)結(jié)構(gòu),1.雙親表示法 用一個(gè)一維數(shù)組存儲(chǔ)樹中的各個(gè)結(jié)點(diǎn)，數(shù)組元素是一個(gè)結(jié)構(gòu)體型數(shù)據(jù)，包含兩個(gè)域：data域和parent域，分別表示結(jié)點(diǎn)的數(shù)據(jù)值和其雙親結(jié)點(diǎn)在數(shù)組中的下標(biāo)。其類型定義如下： typedef struct ElemType data; /*結(jié)點(diǎn)的數(shù)據(jù)域，ElemType可以是任意類型*/ int parent; /*結(jié)點(diǎn)存儲(chǔ)其雙親的數(shù)組下標(biāo)值*/ ParTypeMaxSize;,返回到本節(jié)目錄,1.雙親表示法示例,圖5-1中給出的樹，可以用圖5-3來(lái)存儲(chǔ)表示。其中，規(guī)定數(shù)組下標(biāo)為0的位置存儲(chǔ)的是根結(jié)點(diǎn)，設(shè)根結(jié)點(diǎn)的parent域?yàn)?1。,圖5-3 圖5-1中樹的雙親表示法,返回到本節(jié)目錄,5.1.4 樹的存儲(chǔ)結(jié)構(gòu),2.孩子表示法 將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)構(gòu)成一個(gè)單鏈表，稱之為孩子鏈表。n個(gè)結(jié)點(diǎn)的樹有n個(gè)這樣的孩子鏈表。為了方便起見，我們將每個(gè)結(jié)點(diǎn)存放在一個(gè)順序表中，順序表的每個(gè)元素有兩個(gè)域：一個(gè)是存放該結(jié)點(diǎn)的數(shù)據(jù)值；另一個(gè)是存放該結(jié)點(diǎn)的第一個(gè)孩子的地址。孩子結(jié)點(diǎn)也有兩個(gè)域：一個(gè)域是存放該孩子結(jié)點(diǎn)在順序表中的位置（數(shù)組下標(biāo)），另一個(gè)域是存放下一個(gè)孩子的地址。,返回到本節(jié)目錄,2.孩子表示法舉例,圖5-4是圖5-1所示樹的孩子表示法。其中，規(guī)定表頭下標(biāo)為0的位置存放根結(jié)點(diǎn)。,圖5-4 圖5-1樹的孩子表示法,返回到本節(jié)目錄,5.1.4 樹的存儲(chǔ)結(jié)構(gòu),3.孩子兄弟法 孩子兄弟法存儲(chǔ)結(jié)構(gòu)是一種二叉鏈表，鏈表中每個(gè)結(jié)點(diǎn)包括三個(gè)域：數(shù)據(jù)值和兩個(gè)指針，其中一個(gè)指針指向該結(jié)點(diǎn)的最左邊第一個(gè)孩子，而另一個(gè)指針則指向該結(jié)點(diǎn)的下一個(gè)兄弟。每個(gè)結(jié)點(diǎn)的類型定義如下： typedef struct node2 ElemType data; /*數(shù)據(jù)域*/ Struct node2 *child,*brother; /*其第一個(gè)孩子和其右邊兄弟的地址*/ CBNodeType; /*孩子兄弟結(jié)點(diǎn)類型*/,返回到本節(jié)目錄,圖5-5是圖5-1所示樹的孩子兄弟表示法的存儲(chǔ)結(jié)構(gòu)。其中T指向樹的根結(jié)點(diǎn)。,圖5-5 圖5-1樹的孩子兄弟表示法,返回到本節(jié)目錄,5.2 二叉樹,5.2.1 二叉樹的定義 5.2.2 二叉樹的性質(zhì) 5.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 5.2.4 二叉樹的基本運(yùn)算,返回到總目錄,5.2.1 二叉樹的定義,1二叉樹的定義 二叉樹（Binary Tree）是有n（n0）個(gè)結(jié)點(diǎn)的有限集合。 （1）該集合或者為空（n=0）； （2）或者由一個(gè)根結(jié)點(diǎn)及兩個(gè)不相交的分別稱為左子樹和右子樹組成的非空樹； （3）左子樹和右子樹同樣又都是二叉樹。,返回到本節(jié)目錄,5.2.1 二叉樹的定義,2二叉樹的形態(tài) 二叉樹歸納起來(lái)有五種形態(tài)，如圖5-7所示。,(a)空二叉樹 (b)只有一個(gè)根結(jié)點(diǎn) (c)右子樹為空 (d)左子樹為空 (e)左、右子樹非空 圖5-7 二叉樹的五種形態(tài),返回到本節(jié)目錄,5.2.2 二叉樹的性質(zhì),性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i1）。 性質(zhì)2：深度為k的二叉樹中至多有2k -1個(gè)結(jié)點(diǎn)。 性質(zhì)3：對(duì)任意一棵二叉樹T，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。,返回到本節(jié)目錄,5.2.2 二叉樹的性質(zhì),下面介紹兩種特殊的二叉樹。 （1）滿二叉樹 一棵深度為k，且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。圖5-9（a）所示是一棵深度為4的滿二叉樹，其特點(diǎn)是每一層上的結(jié)點(diǎn)都具有最大的結(jié)點(diǎn)數(shù)。 （2）完全二叉樹 在一棵二叉樹中，除最后一層外，若其它層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)的若干個(gè)結(jié)點(diǎn)，則稱此二叉樹為完全二叉樹。據(jù)此得知滿二叉樹是完全二叉樹的特例。圖5-9（b）是一棵深度為4 的完全二叉樹。,返回到本節(jié)目錄,滿二叉樹和完全二叉樹示例,(a)一棵滿二叉樹 (b)一棵完全二叉樹 圖5-9 一棵滿二叉樹和一棵完全二叉樹示意圖,返回到本節(jié)目錄,5.2.2 二叉樹的性質(zhì),性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。 性質(zhì)5：如果一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為）的結(jié)點(diǎn)按層次（從第1層到第層，每層從左到右。則對(duì)任一結(jié)點(diǎn)i(1in)有： （1）如果i=1，結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙親；如果i1，則其雙親結(jié)點(diǎn)是結(jié)點(diǎn)i/2。 （2）如果2in，則結(jié)點(diǎn)i無(wú)左孩子，該結(jié)點(diǎn)為葉子結(jié)點(diǎn)；否則其左孩子是結(jié)點(diǎn)2i。 （3）如果2i+1n，則結(jié)點(diǎn)i無(wú)右孩子，該結(jié)點(diǎn)為葉子結(jié)點(diǎn)；否則其左孩子是結(jié)點(diǎn)2i+1。,返回到本節(jié)目錄,5.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu),1順序存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)一棵二叉樹時(shí)，先對(duì)該二叉樹中的各結(jié)點(diǎn)進(jìn)行編號(hào)，然后以各結(jié)點(diǎn)的編號(hào)為下標(biāo)，把各結(jié)點(diǎn)的值存到一維數(shù)組中。 其編號(hào)過(guò)程為：首先，把樹的根結(jié)點(diǎn)的編號(hào)定為1，然后按照層次從上到下，從左到右的順序?qū)γ恳唤Y(jié)點(diǎn)進(jìn)行編號(hào)。當(dāng)一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為i時(shí)，若它是左孩子，則編號(hào)為2i，若它是右孩子，則編號(hào)為2i+1。如圖5-10(a)所示的二叉樹（各結(jié)點(diǎn)上方的數(shù)字就是該結(jié)點(diǎn)的編號(hào)）對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)為圖5-10(b)所示。,返回到本節(jié)目錄,順序存儲(chǔ)的二叉樹示例,一棵帶編號(hào)的二叉樹,(b)對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu) 圖5-10 一棵二叉樹及其順序存儲(chǔ)結(jié)構(gòu),返回到本節(jié)目錄,5.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu),2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 對(duì)于一般的二叉樹，通常采用二叉鏈表示。鏈表中的每個(gè)結(jié)點(diǎn)包含兩個(gè)指針，分別指向該結(jié)點(diǎn)的左孩子和右孩子。在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)的類型定義如下： Typedef struct tnode ElemType data; /*數(shù)據(jù)域*/ struct tnode *lchild,*rchild; /*左、右孩子指針域*/ BTNode; /*二叉樹結(jié)點(diǎn)存儲(chǔ)類型*/ 其中，data域中存入結(jié)點(diǎn)的數(shù)據(jù)值，lchild和rchild分別表示左指針域和右指針域，分別存儲(chǔ)其左、右孩子結(jié)點(diǎn)的地址。,返回到本節(jié)目錄,圖5-11 二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),如圖5-10的二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖5-11所示。,返回到本節(jié)目錄,5.2.4 二叉樹的基本運(yùn)算,二叉樹的常用運(yùn)算有以下幾種： （1）bt=CreateBTree(str):根據(jù)二叉樹的廣義表表示法str建立二叉樹bt。 （2）BTHeight(bt)：求一棵二叉樹bt的高度。 （3）NodeCount(bt)：求一棵二叉樹bt的結(jié)點(diǎn)個(gè)數(shù)。 （4）LeafCount(bt): 求一棵二叉樹bt的葉子結(jié)點(diǎn)個(gè)數(shù)。 （5）DispBTree(bt):以廣義表表示法輸出一棵二叉樹bt。,返回到本節(jié)目錄,5.3 二叉樹的建立和遍歷,5.3.1 二叉樹的建立和輸出 5.3.2 二叉樹的遍歷 5.3.3 由遍歷序列恢復(fù)二叉樹,返回到總目錄,5.3.1 二叉樹的建立和輸出,1二叉樹的建立 二叉樹的建立是二叉樹的重要運(yùn)算之一，我們介紹的方法是：用字符ch掃描用廣義表表示法輸入的二叉樹的字符串str。分以下幾種情況： （1）若ch=(，則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧，并置k=1，表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)。 （2）若ch=)，表示棧中結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)處理完畢，退棧。 （3）若ch=,，表示要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn)，并根據(jù)k值建立它與棧中結(jié)點(diǎn)之間的聯(lián)系，當(dāng)k=1時(shí)，表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，當(dāng)k=2時(shí)，表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。如此循環(huán)直到str處理完畢。算法中使用一個(gè)棧st保存雙親結(jié)點(diǎn)，top為其棧頂指針，k指定其后處理的結(jié)點(diǎn)是雙親結(jié)點(diǎn)（保存在棧中）的左孩子結(jié)點(diǎn)（k=1）還是右孩子結(jié)點(diǎn)（k=2）。,返回到本節(jié)目錄,1二叉樹的建立,（1）二叉樹的存儲(chǔ)結(jié)構(gòu)及相關(guān)類型的定義如下： #define NULL 0 /*定義空指針為0*/ #define MaxSize 100 /*樹的最大元素個(gè)數(shù)為100*/ typedef char ElemType; /*重定義char為ElemType類型 */ typedef struct tnode ElemType data; /*數(shù)據(jù)域*/ struct tnode *lchild,*rchild; /*左、右孩子指針*/ BTNode; /*二叉樹結(jié)點(diǎn)類型*/,返回到本節(jié)目錄,1二叉樹的建立算法,（2）二叉樹的建立對(duì)應(yīng)的算法如算法5.1所示。 算法5.1 BTNode *CreateBTree(char *str) BTNode *bt,*stMaxSize,*p=NULL; int top=-1,k,j=0; char ch; bt=NULL; ch=strj; while(ch!=0) switch (ch) case (:top+; /*若是左括號(hào)，則先入棧*/ sttop=p; k=1; break; case ):top-;break; /*若是右括號(hào)，則出棧*/,返回到本節(jié)目錄,1二叉樹的建立算法,case ,:k=2;break; /*若是逗號(hào)，則有右子樹*/ default : /*若是其它字符，則生成新的二叉樹結(jié)點(diǎn)*/ p=(BTNode *)malloc(sizeof(BTNode); p-data=ch; p-lchild=p-rchild=NULL; if(bt=NULL) bt=p; else switch(k) case 1:sttop-lchild=p;break; case 2:sttop-rchild=p;break; j+; ch=strj; return(bt); ,返回到本節(jié)目錄,5.3.1 二叉樹的建立和輸出,2用廣義表表示法輸出二叉樹 其過(guò)程是：對(duì)于非空二叉樹bt，先輸出其元素值，當(dāng)存在左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)時(shí)，輸出一個(gè)(符號(hào)，然后遞歸處理左子樹，輸出一個(gè),符號(hào)，遞歸處理右子樹，最后輸出一個(gè))。對(duì)應(yīng)的算法如算法5.2。,返回到本節(jié)目錄,2用廣義表表示法輸出二叉樹,算法5.2 void DispBTree(BTNode *bt) if (bt!=NULL) printf(“%c“,bt-data); if(bt-lchild!=NULL) printf(“(“); DispBTree(bt-lchild); if(bt-rchild!=NULL) printf(“,“); DispBTree(bt-rchild); printf(“)“); ,返回到本節(jié)目錄,5.3.2 二叉樹的遍歷,一棵二叉樹由根結(jié)點(diǎn)（D）、根結(jié)點(diǎn)的左子樹（L）和根結(jié)點(diǎn)的右子樹（R）三部分組成。 一般限定先左后右的次序，那么只有三種遍歷：DLR（根左右）、LDR（左根右）、LRD（左右根）。我們將這三種遍歷方法稱作前（根）序遍歷，中（根）遍歷和后（根）序遍歷。 也可以對(duì)二叉樹的每個(gè)層次的各結(jié)點(diǎn)按從左至右進(jìn)行遍歷（按層次遍歷），下面我們分別介紹這幾種遍歷方法。,返回到本節(jié)目錄,1.前（根）序遍歷二叉樹（DLR）,有些教材稱為先（根）序遍歷。若二叉樹為空，遍歷結(jié)束。否則依次執(zhí)行以下操作： （1）訪問(wèn)根結(jié)點(diǎn)； （2）前序遍歷根結(jié)點(diǎn)的左子樹； （3）前序遍歷根結(jié)點(diǎn)的右子樹。 前序遍歷的遞歸算法如算法5.3所示。 以圖5-10為例，進(jìn)行前序遍歷的輸出序列為：ABDCEGF。,返回到本節(jié)目錄,前序遍歷的遞歸算法,算法5.3 void PreOrder(BTNode *bt) /* 前序遍歷二叉樹BT*/ if(bt=NULL) return; /* 遞歸調(diào)用的結(jié)束條件*/ else printf(“%c“,bt-data); /* 輸出結(jié)點(diǎn)的數(shù)據(jù)域*/ PreOrder(bt-lchild); /*前序遞歸遍歷左子樹*/ PreOrder(bt-rchild); /* 前序遞歸遍歷右子樹*/ ,返回到本節(jié)目錄,2.中（根）序遍歷二叉樹（LDR）,若二叉樹為空，遍歷結(jié)束。否則依次執(zhí)行以下操作： （1）中序遍歷根結(jié)點(diǎn)的左子樹； （2）訪問(wèn)根結(jié)點(diǎn)； （3）中序遍歷根結(jié)點(diǎn)的右子樹。 中序遍歷的遞歸算法如算法5.4所示。 以圖5-10為例，進(jìn)行中序遍歷的輸出序列為：DBAGECF。,返回到本節(jié)目錄,中序遍歷的遞歸算法,算法5.4 void InOrder(BTNode *bt) /*中序遍歷二叉樹BT*/ if(bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/ else InOrder(bt-lchild); /* 中序遞歸遍歷左子樹*/ printf(“%c“,bt-data); /*輸出結(jié)點(diǎn)的數(shù)據(jù)域*/ InOrder(bt-rchild); /* 中序遞歸遍歷右子樹*/ ,返回到本節(jié)目錄,3后（根）序遍歷二叉樹（LRD）,若二叉樹為空，遍歷結(jié)束。否則依次執(zhí)行以下操作： （1）后序遍歷根結(jié)點(diǎn)的左子樹； （2）后序遍歷根結(jié)點(diǎn)的右子樹。 （3）訪問(wèn)根結(jié)點(diǎn)； 后序遍歷的遞歸算法如算法5.5所示。 以圖5-10為例，進(jìn)行后序遍歷的輸出序列為：DBGEFCA。,返回到本節(jié)目錄,后序遍歷的遞歸算法,算法5.5 void PostOrder(BTNode *bt) /*后序遍歷二叉樹BT*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/ else PostOrder(bt-lchild); /*后序遞歸遍歷左子樹*/ PostOrder(bt-rchild); /*后序遞歸遍歷右子樹*/ printf(“%c“,bt-data); /*輸出結(jié)點(diǎn)的數(shù)據(jù)域*/ ,返回到本節(jié)目錄,4層次遍歷二叉樹,在進(jìn)行層次遍歷時(shí)，對(duì)某一層的結(jié)點(diǎn)訪問(wèn)完后，再按照它們的訪問(wèn)次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左、右孩子順序訪問(wèn)，這樣一層一層進(jìn)行，先訪問(wèn)的結(jié)點(diǎn)其左、右孩子也要先訪問(wèn)。這樣的操作與隊(duì)列的原則比較符合，所以可以用一個(gè)環(huán)形隊(duì)列qu來(lái)實(shí)現(xiàn)。 層次遍歷過(guò)程是先將根結(jié)點(diǎn)進(jìn)隊(duì)，在隊(duì)不空時(shí)循環(huán)；從隊(duì)列中出列一個(gè)結(jié)點(diǎn)*p，訪問(wèn)它；若它有左孩子結(jié)點(diǎn)，將左孩子結(jié)點(diǎn)進(jìn)隊(duì)；若它有右孩子結(jié)點(diǎn)，將右孩子結(jié)點(diǎn)進(jìn)隊(duì)，直到隊(duì)空為止。算法如算法5.6所示。 以圖5-10為例，進(jìn)行按層次遍歷的輸出序列為：ABCDEFG。,返回到本節(jié)目錄,層次遍歷的算法,算法5.6 void LevelOrder(BTNode *bt) BTNode *p; BTNode *quMaxSize; /*定義循環(huán)隊(duì)列，存放結(jié)點(diǎn)指針*/ int front,rear; /*定義隊(duì)頭隊(duì)尾指針*/ front=rear=-1; /*空隊(duì)*/ rear+; qurear=bt; /*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/,返回到本節(jié)目錄,層次遍歷的算法,while(front!=rear) /*隊(duì)列不空時(shí)*/ front=(front+1)%MaxSize; p=qufront; /*隊(duì)頭出隊(duì)列*/ printf(“%c“,p-data); if(p-lchild!=NULL) /*有左孩子時(shí)將其進(jìn)隊(duì)*/ rear=(rear+1)%MaxSize; qurear=p-lchild; if(p-rchild!=NULL) /*有右孩子時(shí)將其進(jìn)隊(duì)*/ rear=(rear+1)%MaxSize; qurear=p-rchild; ,返回到本節(jié)目錄,5.3.3 由遍歷序列恢復(fù)二叉樹,1由前序和中序恢復(fù)二叉樹 （1）根據(jù)前序序列確定樹的根（第一個(gè)結(jié)點(diǎn)），根據(jù)中序序列確定左子樹和右子樹； （2）分別找出左子樹和右子樹的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)聯(lián)到雙親結(jié)點(diǎn)上去； （3）再對(duì)左子樹和右子樹按此法找根結(jié)點(diǎn)和左、右子樹，直到子樹只剩下1個(gè)結(jié)點(diǎn)或2個(gè)結(jié)點(diǎn)或空為止。,返回到本節(jié)目錄,5.3.3 由遍歷序列恢復(fù)二叉樹,2由中序和后序恢復(fù)二叉樹 由二叉樹的后序序列和中序序列也可唯一地確定一棵二叉樹。其方法為： （1）根據(jù)后序序列找出根結(jié)點(diǎn)（最后一個(gè)），根據(jù)中序序列確定左、右子樹； （2）分別找出左子樹和右子樹的根結(jié)點(diǎn)，并把左、右子樹的根結(jié)點(diǎn)聯(lián)到雙親（parent）結(jié)點(diǎn)上去； （3）再對(duì)左子樹和右子樹按此法找根結(jié)點(diǎn)和左、右子樹，直到子樹只剩下1個(gè)結(jié)點(diǎn)或2個(gè)結(jié)點(diǎn)或空為止。,返回到本節(jié)目錄,5.4 樹、森林與二叉樹的轉(zhuǎn)換,5.4.1 樹、森林轉(zhuǎn)換為二叉樹 5.4.2 二叉樹還原為樹、森林,返回到總目錄,5.4.1 樹、森林轉(zhuǎn)換為二叉樹,1樹轉(zhuǎn)換成二叉樹 將一棵樹轉(zhuǎn)換成二叉樹的過(guò)程如下： （1）加線：樹中所有相鄰兄弟之間加一條連線。 （2）抹線：對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪除它與其它孩子結(jié)點(diǎn)之間的連線。 （3）旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)45，使之成為二叉樹。,返回到本節(jié)目錄,【例5.3】將圖5-15（a）所示的樹轉(zhuǎn)換成二叉樹。,轉(zhuǎn)換過(guò)程如圖5-15(b)、(c)、(d)所示。,（a）原始樹 （b）相鄰兄弟之間加連線（虛線）,（c）刪除與雙親結(jié)點(diǎn)的連線 (d)轉(zhuǎn)換之后的二叉樹 圖5-15 一棵樹轉(zhuǎn)換成二叉樹的過(guò)程,返回到本節(jié)目錄,2森林轉(zhuǎn)換為二叉樹,將森林轉(zhuǎn)換為二叉樹的過(guò)程如下： （1）將森林中的每一棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2）第一棵二叉樹保持不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹作為前一棵二叉樹根結(jié)點(diǎn)的右子樹，直到把最后一棵二叉樹作為其前一棵二叉樹的右子樹為止。此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。,返回到本節(jié)目錄,【例5.4】將圖5-16（a）所示的森林轉(zhuǎn)換成二叉樹。,解：轉(zhuǎn)換的過(guò)程如圖5-16（b）5-16（e）所示。,（a）森林 （b）相鄰兄弟加連線（虛線）,（c）刪除與雙親結(jié)點(diǎn)的連線 （d）每棵樹轉(zhuǎn)換成二叉樹,返回到本節(jié)目錄,【例5.4】,（e）所有的二叉樹連接成一棵二叉樹 圖5-16 森林轉(zhuǎn)換成二叉樹的過(guò)程,返回到本節(jié)目錄,5.4.2 二叉樹還原為樹、森林,1二叉樹還原為樹 二叉樹還原為樹的過(guò)程如下： （1）加線：如果某結(jié)點(diǎn)的左孩子有右子樹，在該結(jié)點(diǎn)和其左孩子的右子樹的右分支上各結(jié)點(diǎn)間加線。 （2）抹線：抹掉各結(jié)點(diǎn)的右子樹的右分支取上的連線。 （3）旋轉(zhuǎn)整理得到樹。,返回到本節(jié)目錄,5.4.2 二叉樹還原為樹、森林,2二叉樹還原為森林 二叉樹還原為森林的過(guò)程如下： （1）連線：若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用連線連起來(lái)。 （2）抹線：刪除原二叉樹中原來(lái)雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。 （3）整理由（1）、（2）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。,返回到本節(jié)目錄,5.5 哈夫曼樹,5.5.1相關(guān)概念和哈夫曼樹的定義 5.5.2 哈夫曼樹的構(gòu)造方法 5.5.3 哈夫曼編碼,返回到總目錄,5.5.1相關(guān)概念和哈夫曼樹的定義,1路徑 樹中一個(gè)結(jié)點(diǎn)與另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。樹中不是每對(duì)結(jié)點(diǎn)之間都有路徑，如兄弟結(jié)點(diǎn)之間就無(wú)路徑，而從根結(jié)點(diǎn)到樹中任一結(jié)點(diǎn)都存在一條路徑。 2路徑長(zhǎng)度 樹中路徑上的分支數(shù)目。 3樹的路徑長(zhǎng)度 根結(jié)點(diǎn)到樹中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 4結(jié)點(diǎn)的權(quán)值 所謂權(quán)值是人們根據(jù)需要為每個(gè)葉子結(jié)點(diǎn)賦予的一個(gè)數(shù)值。,返回到本節(jié)目錄,5結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 是指從樹根到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)值的乘積。 6樹的帶權(quán)路徑長(zhǎng)度 樹中所有葉子結(jié)點(diǎn)的權(quán)值乘以該結(jié)點(diǎn)的路徑長(zhǎng)度之和。用公式可以表示為： 其中，wk為第k個(gè)葉子結(jié)點(diǎn)的權(quán)值， lk 是從根結(jié)點(diǎn)到第k個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。 7哈夫曼樹 哈夫曼樹又稱為最優(yōu)二叉樹。它是n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)所構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹。,返回到本節(jié)目錄,求不同二叉樹的WPL,如圖5-19（a）、（b）、（c）所示的三棵二叉樹，它們的帶權(quán)路徑長(zhǎng)度分別為： （a）WPL=22+32+42+62=30 （b）WPL=23+33+42+61=29 （c）WPL=43+63+32+21=38,（a） （b） （c） 圖5-19 相同葉子結(jié)點(diǎn)所構(gòu)成的不同帶權(quán)路徑長(zhǎng)度的二叉樹,返回到本節(jié)目錄,5.5.2 哈夫曼樹的構(gòu)造方法,下面介紹哈夫曼樹的構(gòu)造方法，步驟如下： （1）將給定的n個(gè)權(quán)值w1,w2,.,wn作為n個(gè)根結(jié)點(diǎn)的權(quán)值構(gòu)造一個(gè)具有n棵二叉樹的森林T1,T2,.,Tn，其中每棵二叉樹只有一個(gè)根結(jié)點(diǎn)； （2）在森林中選取兩棵樹根結(jié)點(diǎn)的權(quán)值最小的二叉樹作為左右子樹構(gòu)造一棵新二叉樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為原來(lái)兩棵樹根結(jié)點(diǎn)的權(quán)值之和； （3）在森林中，將上面選擇的這兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹從森林中刪除，并將最新構(gòu)造的二叉樹加入到森林中； （4）重復(fù)上面（2）和（3），直到森林中只有一棵二叉樹為止。這棵二叉樹就是哈夫曼樹。,返回到本節(jié)目錄,【例5.7】假設(shè)有一組權(quán)值2,3,7,8,12,9,6,19，下面我們將利用這組權(quán)值演示構(gòu)造哈夫曼樹的過(guò)程。 解：第一步：以這8個(gè)權(quán)值作為根結(jié)點(diǎn)的權(quán)值構(gòu)造具有8棵樹的森林。,第二步：從中選擇兩個(gè)根的權(quán)值最小的樹2、3作為左右子樹構(gòu)造一棵新樹，并將這兩棵樹從森林中刪除，并將新樹5添加進(jìn)去。,返回到本節(jié)目錄,第三步：重復(fù)第二步過(guò)程，直到森林中只有一棵樹為止 選擇5、6，將11放回。,選擇7、8，將15放回。,返回到本節(jié)目錄,選擇9、11，將20放回,選擇12、15，將27放回。,返回到本節(jié)目錄,選擇19、20，將39放回。,選擇27、39，最后森林中只有一棵樹，結(jié)束操作，這棵樹就是哈夫曼樹。,返回到本節(jié)目錄,為了實(shí)現(xiàn)構(gòu)造哈夫曼樹的算法，設(shè)計(jì)哈夫曼樹中每個(gè)結(jié)點(diǎn)類型如下： typedef struct char data; /*結(jié)點(diǎn)值*/ int weight; /*權(quán)值*/ int parent; /*雙親結(jié)點(diǎn)下標(biāo)*/ int lchild; /*左孩子結(jié)點(diǎn)下標(biāo)*/ int rchild; /*右孩子結(jié)點(diǎn)下標(biāo)*/ HTCode; /*哈夫曼樹結(jié)點(diǎn)類型*/,返回到本節(jié)目錄,用ht數(shù)組存放哈夫曼樹，對(duì)于具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，總共有2n-1個(gè)結(jié)點(diǎn)。其算法思路是：n個(gè)葉子結(jié)點(diǎn)只有data和weight域值，先將所有2n-1個(gè)結(jié)點(diǎn)的parent、lchild和rchild域置為-1。處理每個(gè)非葉子結(jié)點(diǎn)hti（存放在htnht2n-2中）：從ht0hti-2中找出根結(jié)點(diǎn)（即其parent域?yàn)?1）最小的兩個(gè)結(jié)點(diǎn)htlnode和htrnode，將它們作為hti的左右子樹，htlnode和htrnode雙親結(jié)點(diǎn)置為hti，并且hti.weight= htlnode.weight+htrnode.weight。如此這樣直到所有的n-1個(gè)非葉子結(jié)點(diǎn)處理完畢。構(gòu)造哈夫曼樹的算法如算法5.7。,返回到本節(jié)目錄,算法5.7 void CreateHT(HTCode ht,int n) int i,j,k,lnode,rnode; int min1,min2; for(i=0;i2*n-1;i+) /*將雙親、左、右孩子域置初值-1*/ hti.parent=hti.lchild=hti.rchild=-1; for(i=n;i2*n-1;i+) min1=min2=32767; /*兩個(gè)最小值置初值為系統(tǒng)最大值*/ lnode=rnode=-1;,返回到本節(jié)目錄,for(k=0;khtk.weight) min1=htk.weight; /*找出最小的權(quán)值*/ lnode=k; /*最小權(quán)值的結(jié)點(diǎn)下標(biāo)值*/ for(k=0;khtk.weight /*次最小權(quán)值的結(jié)點(diǎn)下標(biāo)值*/ ,返回到本節(jié)目錄,htlnode.parent=i;htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode; ,返回到本節(jié)目錄,5.5.3 哈夫曼編碼,1什么是哈夫編碼？ 在進(jìn)行快速遠(yuǎn)距離的通信時(shí)，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0，1組成的二進(jìn)制代碼，稱之為編碼。 如果在編碼時(shí)考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長(zhǎng)的編碼，構(gòu)造一種不等長(zhǎng)編碼，則電文的代碼就可能更短。哈夫曼編碼是一種用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。,返回到本節(jié)目錄,5.5.3 哈夫曼編碼,2生成哈夫曼編碼的方法 要設(shè)計(jì)長(zhǎng)短不同的編碼，首先要做到不同字符的編碼不會(huì)混淆，即任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴（即不是另一個(gè)字符編碼的開頭一部分），滿足這個(gè)條件的編碼叫做前綴編碼。即前綴編碼是指所編碼的字符可以通過(guò)前綴唯一地正確識(shí)別并譯出。利用哈夫曼樹就可以方便的設(shè)計(jì)。,返回到本節(jié)目錄,2生成哈夫曼編碼的方法,（1）構(gòu)造哈夫曼樹 設(shè)需要編碼的字符集合為d1，d2，dn，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)集合為w1，w2，wn，以d1，d2，dn作為葉子結(jié)點(diǎn)，w1，w2，wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹。 （2）在哈夫曼樹上求葉結(jié)點(diǎn)的編碼。 規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼。,返回到本節(jié)目錄,【例5.8】設(shè)有A，B，C，D，E，F(xiàn) 6個(gè)字符，其出現(xiàn)的頻度分別為0.06、0.02、0.04、0.03、0.07、0.12，試設(shè)計(jì)它們的哈夫曼編碼。 解：將所有頻度全部乘以100，得到各字符的權(quán)值6，2，4，3，7，12，根據(jù)這組權(quán)值構(gòu)造的哈夫曼樹如圖5-21所示。并設(shè)哈夫曼樹的每個(gè)左分支為0，右分支為1進(jìn)行編碼.,返回到本節(jié)目錄,則得到各個(gè)字符的哈夫曼編碼為： A：00 B：1010 C：100 D：1011 E：01 F：11,圖5-21 哈夫曼編碼樹,返回到本節(jié)目錄,3.哈夫曼編碼的算法實(shí)現(xiàn),（1）設(shè)計(jì)哈夫曼編碼的數(shù)據(jù)類型如下： typedef struct char cdN; /*存放當(dāng)前結(jié)點(diǎn)的哈夫曼編碼*/ int start; /*start指向cd數(shù)組中的哈夫曼編碼最開始字符*/ HCode; /*哈夫曼編碼存放類型*/,返回到本節(jié)目錄,3.哈夫曼編碼的算法實(shí)現(xiàn),（2）生成哈夫曼編碼的算法 由于哈夫曼樹中的每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼長(zhǎng)度不同，為此采用HCode類型變量的cdstartcdn存放當(dāng)前結(jié)點(diǎn)的哈夫曼編碼。只需對(duì)葉子結(jié)點(diǎn)求哈夫曼編碼。對(duì)于當(dāng)前葉子結(jié)點(diǎn)hti，先將對(duì)應(yīng)的哈夫曼編碼和hcdi的start域置初值n，找其雙親結(jié)點(diǎn)htf，若當(dāng)前結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則在hcdi的cd數(shù)組中添加1，將start域減1。再對(duì)雙親結(jié)點(diǎn)進(jìn)行同樣的操作，如此直到無(wú)雙親結(jié)點(diǎn)即到達(dá)樹根結(jié)點(diǎn)，最后讓start指向哈夫曼編碼最開始字符。具體算法如算法5.8所示。,返回到本節(jié)目錄,算法5.8 void CreateHCode(HTCode ht,HCode hcd,int n) int i,f,c; HCode hc; for(i=0;in;i+) hc.start=n; c=i; f=hti.parent; while(f!=-1) if(htf.lchild=c) hc.cdhc.start-=0; else hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; hcdi=hc; ,返回到本節(jié)目錄,（3）為了顯示哈夫曼編碼，設(shè)計(jì)輸出函數(shù)如算法5.9所示。 算法5.9 void DispHCode(HTCode ht,HCode hcd,int n) int i,k; int sum=0,m=0; int j; printf(“n各字符的哈夫曼編碼如下:n“); for(i=0;in;i+) j=0; printf(“n字符%c的哈夫曼編碼為:“,hti.data); for(k=hcdi.start;k=n;k+) printf(“%c“,hcdi.cdk); j+; m+=hti.weight; sum+=hti.weight*j; printf(“n“); ,返回到本節(jié)目錄,（4）為了使用以上各函數(shù)（包括生成哈夫曼樹函數(shù)CreateHT()），設(shè)計(jì)主函數(shù)如下： #include “stdio.h“ /* getchar()函數(shù)需用此頭文件*/ #define N 100 /*最大字符個(gè)數(shù)*/ main() HTCode htN; HCode hcdN; int i,n; clrscr(); printf(“n請(qǐng)輸入電文的字符個(gè)數(shù)(0-50):“); scanf(“%d“,返回到本節(jié)目錄,for(i=0;in;i+) printf(“第%d個(gè)字符為:“,i+1); getchar(); scanf(“%c“, ,返回到本節(jié)目錄,（5）程序執(zhí)行一次的結(jié)果如下：（帶下劃線文字為輸入內(nèi)容，表示回車）。,請(qǐng)輸入電文的字符個(gè)數(shù):5 請(qǐng)輸入每個(gè)電文字符: 第1個(gè)字符為:a 第2個(gè)字符為:b 第3個(gè)字符為:c 第4個(gè)字符為:d 第5個(gè)字符為:e 請(qǐng)輸入每個(gè)字符的使用頻率(權(quán)值為正整數(shù)): 第1個(gè)字符的頻率為:8 第2個(gè)字符的頻率為:2 第3個(gè)字符的頻率為:14 第4個(gè)字符的頻率為:6 第5個(gè)字符的頻率為:5 各字符的哈夫曼編碼如下: 字符a的哈夫曼編碼為:10 字符b的哈夫曼編碼為:1110 字符c的哈夫曼編碼為:0 字符d的哈夫曼編碼為:110 字符e的哈夫曼編碼為:1111,返回到本節(jié)目錄,5.6 本章小結(jié),本章中主要介紹下列內(nèi)容： （1）樹的邏輯定義基本術(shù)語(yǔ)，樹的三種存儲(chǔ)結(jié)構(gòu)：雙親表示法，孩子表示法和孩子兄弟表示法。 （2）二叉樹的邏輯定義、存儲(chǔ)結(jié)構(gòu)，二叉樹的常用性質(zhì)。二叉樹的基本操作算法。二叉樹的三種遍歷方式：先（根）序遍歷、中（根）序遍歷、后（根）序遍歷三種。介紹了已知遍歷序列，恢復(fù)二叉樹的方法。 （3）介紹樹和二叉樹的轉(zhuǎn)換，森林與二叉樹之間的轉(zhuǎn)換。 （4）最后介紹了哈夫曼樹的定義與建立方法，及哈夫曼編碼。,返回到總目錄,