[理學(xué)]第6章樹

1、第六章 樹樹形結(jié)構(gòu)是一種日常生活中應(yīng)用非常廣泛的非線性結(jié)構(gòu)。算機(jī)領(lǐng)域中的操作系統(tǒng)、 數(shù)據(jù)庫(kù)系統(tǒng)都是樹狀結(jié)構(gòu)的應(yīng)用實(shí)例，是利用樹狀結(jié)構(gòu)的原理設(shè)計(jì)的。從單位的組織結(jié)構(gòu)、 家譜到計(jì)甚至某些數(shù)據(jù)庫(kù)管理系統(tǒng)就6.1 樹簡(jiǎn)介什么是樹結(jié)構(gòu)？先看一下它的定義：樹（ Tree）是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它可以用來(lái)描 述有分支的結(jié)構(gòu)，是由一個(gè)或一個(gè)以上的結(jié)點(diǎn)所組成的有限集合，具有下列性質(zhì)：存在一個(gè)特殊的結(jié)點(diǎn)，稱為根（ Root）。其余結(jié)點(diǎn)為 n0 個(gè)互斥的集合，即 T1， T2， T3， Tn，且每個(gè)集合稱為子樹。如下圖所示， A 為根結(jié)點(diǎn)， B 、 C 、 D 、 E 均為 A 的子結(jié)點(diǎn)。比較下面的兩個(gè)圖形圖(a)

2、是一種合法的樹，符合樹的定義：樹由一個(gè)或一個(gè)以上的結(jié)點(diǎn)組成，結(jié)點(diǎn)間有連接且不形成回路。圖 (b)中結(jié)點(diǎn)有連接但卻形成了回路，故不是一棵合法的樹。接下來(lái)了解一下樹的專有名詞，以下圖為例進(jìn)行說(shuō)明。樹根或根結(jié)點(diǎn)（ Root）：沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，如 A 。父結(jié)點(diǎn) （Parend）： 每一個(gè)結(jié)點(diǎn)的上層結(jié)點(diǎn)稱為其父結(jié)點(diǎn)， 如 B 的父結(jié)點(diǎn)為A， G 的父結(jié)點(diǎn)為 C。子結(jié)點(diǎn)（ Children）：每一個(gè)結(jié)點(diǎn)的下層結(jié)點(diǎn)稱為其子結(jié)點(diǎn)，如為 E 及 F， A 的子結(jié)點(diǎn)為 B 、 C、 D 。兄弟結(jié)點(diǎn)（ Siblings）：有共同父結(jié)點(diǎn)的結(jié)點(diǎn)稱為兄弟結(jié)點(diǎn)，如B 的子結(jié)點(diǎn)B 、C 、 D 的父結(jié)點(diǎn)都是 A

3、，所以彼此為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)的度（ Degree）：子結(jié)點(diǎn)的個(gè)數(shù)為該結(jié)點(diǎn)的度，如 A 的度為 3， B 的度為 2 。葉子結(jié)點(diǎn) （Terminal Node）： 沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)， 即度為零的結(jié)點(diǎn)， 例如 E、 F、 G、 H 、 D 都是葉子結(jié)點(diǎn)。非葉子結(jié)點(diǎn)（Non-Terminal Node)：葉子結(jié)點(diǎn)以外的所有結(jié)點(diǎn)為非葉子結(jié)點(diǎn)， 即度不為零的點(diǎn)，如 A 、 B 、 C 都是非葉子結(jié)點(diǎn)。邊（Edge）：連接兩個(gè)結(jié)點(diǎn)的線段，稱之為邊。上圖中的邊共有 7 條，一般地，具有 n個(gè)結(jié)點(diǎn)的樹，其邊數(shù)為 n-1。層（ Level）：樹的層，即樹根 A 為層 1， B 、 C 、 D 為層 2， E、 F

4、、 G、 H為層 3。高度（ Height）：樹的最大層數(shù)。森林（ Forest）：森林是由 n棵互斥的樹組成的集合（ n0）?！痉独?1】下列哪一種結(jié)構(gòu)不是樹（A. 一個(gè)結(jié)點(diǎn)C. 一個(gè)沒(méi)有回路的連通圖Tree）。B. 環(huán)形序列D. 一個(gè)邊數(shù)比結(jié)點(diǎn)數(shù)少 1 的連通圖解答：選擇 B ，因?yàn)榄h(huán)形序列會(huì)形成循環(huán)回路現(xiàn)象，不符合樹的定義?！痉独?2】下圖中的樹（ Tree）中有幾個(gè)葉子結(jié)點(diǎn)？A. 4 B. 5 C. 9 D. 11解答：由上圖可以看出答案為 A ，共有 E 、 C 、 H 、 I 共 4 個(gè)葉子結(jié)點(diǎn)。6.2 二叉樹簡(jiǎn)介一般的樹狀結(jié)構(gòu)在內(nèi)存中的存儲(chǔ)方式以鏈表為主， 對(duì)于 n 叉樹來(lái)說(shuō)，

5、每個(gè)結(jié)點(diǎn)的度不一定相同，但為了方便起見，必須取 n+1 為鏈表結(jié)點(diǎn)的最長(zhǎng)固定長(zhǎng)度，其數(shù)據(jù)結(jié)構(gòu)如下：data link1 link2 linkn假設(shè) n 叉樹有 m 個(gè)結(jié)點(diǎn)，那么此樹共需要 (n+1) m 個(gè)存儲(chǔ)單元。而每個(gè)結(jié)點(diǎn)不一定都會(huì)指向下一層的 n 個(gè)結(jié)點(diǎn)，會(huì)有大量的空值， 如此一來(lái)，會(huì)造成大量的內(nèi)存空間浪費(fèi)， 為了克服這一缺點(diǎn)，常使用二叉樹結(jié)構(gòu)來(lái)取代樹狀結(jié)構(gòu)。6.2.1 二叉樹的定義二叉樹是由有限個(gè)結(jié)點(diǎn)組成的集合， 此集合可以為空集合， 也可由一個(gè)樹根或者一個(gè)樹根與左右兩棵子樹所組成。簡(jiǎn)單的說(shuō)，二叉樹最多只能有兩個(gè)子結(jié)點(diǎn)，即結(jié)點(diǎn)的度小于等于 2，其數(shù)據(jù)結(jié)構(gòu)如下：left data rig

6、ht二叉樹和一般樹的不同點(diǎn)如下：樹不可為空集合，但是二叉樹可以。樹的度 d0，但二叉樹的結(jié)點(diǎn)度 0d2。樹的子樹間沒(méi)有次序關(guān)系，但二叉樹有次序關(guān)系。1h6.2.2 特殊二叉樹的介紹1. 滿二叉樹如果二叉樹高度為 n，樹的結(jié)點(diǎn)為 2 n - 1，則稱此樹為滿二叉樹，如下圖所示。2. 完全二叉樹如果二叉樹的高度為 n，則 1 n-1 層都是滿的，第 n 層的葉子結(jié)點(diǎn)嚴(yán)格按從左至右依次排列，則稱此二叉樹為完全二叉樹，如下圖所示?！拘再|(zhì) 1】假設(shè)一棵完全二叉樹具有 n個(gè)節(jié)點(diǎn)，則它的高度（層） h log 2 ( n 1) 。證明：設(shè)完全二叉樹的高度為 h ，則有2 1 n 2h 1， 2 h 1 n

7、1 2h， h 1 log 2 ( n 1) h故 h log 2 ( n 1) 。3. 嚴(yán)格二叉樹如果二叉樹的每個(gè)非葉子結(jié)點(diǎn)都有非空的左、 右子樹， 則稱此二叉樹為嚴(yán)格二叉樹， 如下圖所示。4. 歪斜樹當(dāng)一個(gè)二叉樹完全沒(méi)有右結(jié)點(diǎn)或左結(jié)點(diǎn)時(shí)，稱為左歪斜樹或右歪斜樹，如下圖所示。5. 排序二叉樹設(shè)結(jié)點(diǎn)由關(guān)鍵字值來(lái)表示，用所有結(jié)點(diǎn)的關(guān)鍵字值互異，排序二叉樹或者是一棵空樹，或者是滿足以下條件的樹：（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)的關(guān)鍵字值；（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)的關(guān)鍵字值；（3）左、右子樹也分別是二叉排序樹。創(chuàng)建這種二叉樹是最為方便的

8、， 它的中序遍歷是關(guān)鍵字值的升序排序， 故而稱之為二叉排序樹?！拘再|(zhì) 2】高度為 h 的二叉樹的結(jié)點(diǎn)總數(shù) n2 h - 1。證明：其結(jié)點(diǎn)總數(shù)為各層中度最大的結(jié)點(diǎn)數(shù)之和，即12ih i1【性質(zhì)0 1 22 2 2h 1 23】對(duì)于非空二叉樹 T，如果數(shù)是 n2，試證明： n 0=n 2+1 。證明：假設(shè)結(jié)點(diǎn)總數(shù)為 n， n1 是度為 n= n 0+n 1+n 2， e= n-1， e =2n 2+n 1 由上述三個(gè)式子，有 n 0=n 2+1 。h2 12 1h2 1n0 為葉子（即度為 0 的結(jié)點(diǎn)）結(jié)點(diǎn)數(shù)，且度為 2 的結(jié)點(diǎn)1 的結(jié)點(diǎn)數(shù)，邊數(shù)為 e，于是，我們有以下關(guān)系式6.3 二叉樹的存儲(chǔ)方

9、式樹狀結(jié)構(gòu)在程序中的建立大多使用鏈表來(lái)處理， 因?yàn)殒湵淼闹羔樣脕?lái)處理樹是相當(dāng)方便的， 只需改變指針即可。 當(dāng)然也可以使用數(shù)組這樣的連續(xù)結(jié)構(gòu)來(lái)表示二叉樹， 使用數(shù)組或者鏈表各有利弊，下面將給予說(shuō)明。！6.3.1 二叉樹的數(shù)組表示法如果用一維數(shù)組來(lái)存儲(chǔ)二叉樹， 首先應(yīng)將二叉樹想象成一棵完全二叉樹， 凡空值結(jié)點(diǎn)均用特殊字符或者數(shù)字替代，并且依序?qū)⒔Y(jié)點(diǎn)值存放到一維數(shù)組中?！痉独?3】將下圖所示的二叉樹，用一維字符數(shù)組進(jìn)行表示。首先將二叉樹想象成一棵完全二叉樹，其空值結(jié)點(diǎn)用 * 代替，結(jié)束符用！表示。其一維字符數(shù)組的表示形式為：索引值內(nèi)容值1A2B3C4*5*6D7【范例程序】用一維字符數(shù)組表示結(jié)點(diǎn)值為

10、字符的二叉樹。/*名稱： ch06_01.cpp示范：用一維字符數(shù)組表示結(jié)點(diǎn)值為字符的二叉樹*/#include#includeusing namespace std;#define MaxSize 100/ 數(shù)組的最大維數(shù)#define MaxLevel 6/ 設(shè)定可輸出的二叉樹最大層數(shù)int NodeNum=0;/ 結(jié)點(diǎn)計(jì)數(shù)變量char NodeMaxSize;/ 字符型的結(jié)點(diǎn)數(shù)組/創(chuàng)建二叉樹的結(jié)點(diǎn)數(shù)組void CreateTreeArray() cout 按完全二叉樹方式輸入，若某層有元素為空，用 * 替代，結(jié)束用 !替代 NodeNodeNum;/ 輸入結(jié)點(diǎn)值if(NodeNodeNu

11、m=!)break;if(NodeNum=MaxSize) cout 輸入字符個(gè)數(shù)超限 ,無(wú)法存儲(chǔ)，請(qǐng)?jiān)龃?MaxSize 的值endl;exit(0);/輸出樹void DisplayTree() int i,j,k;/ 循環(huán)控制變量int hight,level,SerialNum;/hight 樹高， level 樹層 ,SerialNum 序號(hào)/確定樹的高度f(wàn)or(i=0;iNodeNum)break;hight=i;/從第 1 層至第 hight 層進(jìn)行二叉樹的輸出level=1;SerialNum=1;while(level=hight)/每層前端空格輸出控制for(i=0;ipo

12、w(2,hight-level);i+)cout ;/每層輸出的結(jié)點(diǎn)個(gè)數(shù)控制for(j=0;jpow(2,level-1);j+,SerialNum+)if(NodeSerialNum!=*&NodeSerialNum!=!)coutNodeSerialNum;/ 輸出元素else if(NodeSerialNum=*)cout ;/ 輸出空格elsebreak;/遇到結(jié)束符 !,跳出輸出for(k=0;kpow(2,hight-level+1)-1;k+)cout ;/ 每層后端空格輸出控制coutendl;/ 一層輸出完畢 ,換行l(wèi)evel+;/ 層數(shù)增 1coutendl;/輸出數(shù)組vo

13、id DisplayArray() int i=1;do coutNodei ;i+;while(Nodei!=!);coutendl;/主函數(shù)void main() CreateTreeArray();/ 創(chuàng)建二叉樹結(jié)點(diǎn)的一維數(shù)組cout 二叉樹為 endl;DisplayTree();/ 輸出樹cout 結(jié)點(diǎn)數(shù)組為 endl;DisplayArray();/ 輸出數(shù)組system(pause);如果二叉樹的結(jié)點(diǎn)值是由整數(shù)給出的，對(duì)它的處理也是類似的?！痉独?4】將下圖所示的二叉樹，用一維整型數(shù)組進(jìn)行表示。首先將二叉樹想象成一棵完全二叉樹，其空值結(jié)點(diǎn)用 0 代替，結(jié)束符用 -1 表示。14-

14、1其一維整型數(shù)組的表示形式為：索引值 1 2 3 4 5 6 7 8 9 10 11 12 13內(nèi)容值 6 3 9 2 5 7 0 0 0 4 0 0 8僅需要對(duì)上述示范程序作幾處簡(jiǎn)單的修改，就可以用于解決上述問(wèn)題的編程?！痉独绦颉坑靡痪S整型數(shù)組表示結(jié)點(diǎn)值為整數(shù)的二叉樹。/*名稱： ch06_02.cpp示范：用一維整型數(shù)組表示結(jié)點(diǎn)值為整數(shù)的二叉樹*/#include#includeusing namespace std;#define MaxSize 100/ 數(shù)組的最大維數(shù)#define MaxLevel 6/ 設(shè)定可輸出的二叉樹最大層數(shù)int NodeNum=0;/ 結(jié)點(diǎn)計(jì)數(shù)變量int

15、 NodeMaxSize;/ 整型結(jié)點(diǎn)數(shù)組/創(chuàng)建二叉樹的結(jié)點(diǎn)數(shù)組void CreateTreeArray()cout 按完全二叉樹方式輸入，若某層有元素為空，用 0 替代，結(jié)束用 -1 替代 endl;Node0=0;/ 使 Node0 閑置while(1) NodeNum+;cout 請(qǐng)輸入第 NodeNumNodeNodeNum;/ 輸入結(jié)點(diǎn)值if(NodeNodeNum=-1)break;if(NodeNum=MaxSize) cout 輸入字符個(gè)數(shù)超限 ,無(wú)法存儲(chǔ)，請(qǐng)?jiān)龃?MaxSize 的值endl;exit(0);/輸出樹void DisplayTree() int i,j,k;/

16、 循環(huán)控制變量int hight,level,SerialNum;/hight 樹高， level 樹層 ,SerialNum 序號(hào)/確定樹的高度f(wàn)or(i=0;iNodeNum)break;hight=i;/從第 1 層至第 hight 層進(jìn)行二叉樹的輸出level=1;SerialNum=1;while(level=hight)/每層前端空格輸出控制for(i=0;ipow(2,hight-level);i+)cout ;/每層輸出的結(jié)點(diǎn)個(gè)數(shù)控制for(j=0;jpow(2,level-1);j+,SerialNum+)if(NodeSerialNum!=0 & NodeSerialNum

17、!=-1)coutNodeSerialNum;/ 輸出元素else if(NodeSerialNum=0)cout ;/ 輸出空格elsebreak;/遇到結(jié)束符 -1,跳出輸出for(k=0;kpow(2,hight-level+1)-1;k+)cout ;/ 每層后端空格輸出控制coutendl;/ 一層輸出完畢 ,換行l(wèi)evel+;/ 層數(shù)增 1coutendl;/輸出數(shù)組void DisplayArray()int i=1;do coutNodei ;i+;while(Nodei!=-1);coutendl;/主函數(shù)void main() CreateTreeArray();/ 創(chuàng)建二

18、叉樹結(jié)點(diǎn)的一維數(shù)組cout 二叉樹為 endl;DisplayTree();/ 輸出樹cout 結(jié)點(diǎn)數(shù)組為 endl;DisplayArray();/ 輸出數(shù)組system(pause);用一維數(shù)組表示二叉樹， 這一方法的優(yōu)點(diǎn)是： 方法直觀且容易實(shí)現(xiàn)， 而且形象地輸出二叉樹的實(shí)際結(jié)構(gòu)。其缺點(diǎn)是：訪問(wèn)、插入、刪除操作難以實(shí)現(xiàn)，特別是當(dāng)二叉樹不是完全二叉樹時(shí)，會(huì)占用過(guò)多的內(nèi)存空間。例如， 存儲(chǔ)以下含 4 結(jié)點(diǎn)的二叉樹， 卻要多花費(fèi)了 8 個(gè)存儲(chǔ)單元，才能完整地表現(xiàn)這一結(jié)構(gòu)。6.3.2 二叉樹的鏈表表示法二叉樹的鏈表表示法是利用鏈表來(lái)存儲(chǔ)二叉樹，立二叉樹。其結(jié)點(diǎn)結(jié)構(gòu)如下：*left data二叉樹的

19、結(jié)點(diǎn)定義如下：struct BinTreeNode char data;struct BinTreeNode *left,*right;【范例 5】對(duì)下圖所示的二叉樹即運(yùn)用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)和指針的方式來(lái)建*right用鏈表來(lái)表示它，其結(jié)構(gòu)圖如下：構(gòu)建過(guò)程如下：（1）先將倒數(shù)第一層的三個(gè)結(jié)點(diǎn)建子二叉樹，并用相應(yīng)的結(jié)點(diǎn)指針指向其根結(jié)點(diǎn)。（2）再將二層的兩個(gè)結(jié)點(diǎn)建子二叉樹，并用相應(yīng)的結(jié)點(diǎn)指針指向其根結(jié)點(diǎn)。（3）最后將第一層的一個(gè)結(jié)點(diǎn)建子二叉樹，并用一個(gè)結(jié)點(diǎn)指針指向其根結(jié)點(diǎn)。上述子二叉樹經(jīng)過(guò)連接之后， 便成了我們所需要構(gòu)建的二叉樹。 這種建二叉樹的過(guò)程是， 由葉子結(jié)點(diǎn)開始，向上逐層擴(kuò)建成樹?！痉独绦颉坑?/p>

20、鏈表來(lái)表示二叉樹。/*名稱： ch06_03.cpp示范：二叉樹的鏈表表示法*/#includeusing namespace std;/二叉樹結(jié)點(diǎn)定義struct BinTreeNode;char data;/結(jié)點(diǎn)數(shù)據(jù)struct BinTreeNode *left,*right;/ 左、右指針/建二叉樹BinTreeNode *MakeBinTree(char data,BinTreeNode *left,BinTreeNode *right)/ 以 data 為數(shù)據(jù) ,left,right 為左右子樹建樹BinTreeNode *newnode;newnode=new BinTreeNo

21、de;newnode-data=data;newnode-left=left;newnode-right=right;return newnode;/主函數(shù)void main() BinTreeNode *aptr,*bptr,*cptr,*dptr,*eptr,*fptr;dptr=MakeBinTree(D,NULL,NULL);eptr=MakeBinTree(E,NULL,NULL);fptr=MakeBinTree(F,NULL,NULL);bptr=MakeBinTree(B,dptr,eptr); cptr=MakeBinTree(C,NULL,fptr); aptr=MakeB

22、inTree(A,bptr,cptr); system(pause);從上述創(chuàng)建鏈?zhǔn)蕉鏄涞某绦蚩梢园l(fā)現(xiàn)， 其程序控制， 而且還無(wú)法輸出它的實(shí)際結(jié)構(gòu)，這種結(jié)構(gòu)在程序?qū)崿F(xiàn)上十分復(fù)雜， 不便于實(shí)現(xiàn)也無(wú)法查找結(jié)點(diǎn)的父結(jié)點(diǎn)。 但這種結(jié)構(gòu)也有其優(yōu)點(diǎn)： 那就是查找、 插入和刪除操作方便。二叉樹結(jié)點(diǎn)值的輸出需要用它二叉樹的遍歷，在下一節(jié)進(jìn)行介紹。6.4 二叉樹的遍歷遍歷二叉樹最簡(jiǎn)單的方法就是遍歷樹中所有結(jié)點(diǎn)各一次， 并且在遍歷后將樹的數(shù)據(jù)轉(zhuǎn)化為線性關(guān)系。 其實(shí)二叉樹的遍歷， 并不像之前所提到的線性結(jié)構(gòu)那樣簡(jiǎn)單， 就一個(gè)簡(jiǎn)單二叉樹結(jié)點(diǎn)而言，每個(gè)結(jié)點(diǎn)都可以區(qū)分左、右兩個(gè)分支。如下圖所示的二叉樹共有 ABC 、

23、ACB 、 BAC 、 BCA 、 CAB 、 CBA 等 6 種遍歷方式。如果是依照二叉樹特性一律由左向右遍歷，那么只剩下三種遍歷方式，即 BAC 、 ABC 、 BCA 。以上三種遍歷的方式的命名如下。中序遍歷（ BAC， Preorder）：左子樹 -樹根 -右子樹。前序遍歷（ ABC， Inorder）：樹根 -左子樹 -右子樹。后序遍歷（ BCA， Postorder）：左子樹 -右子樹 -樹根。所謂的中序、前序、 后序都是針對(duì)根結(jié)點(diǎn)而言的， 例如中序遍歷是根結(jié)點(diǎn)在中間， 前序遍歷是根結(jié)點(diǎn)在前面，后序遍歷是根結(jié)點(diǎn)在后面。而遍歷方式一定是先左子樹后右子樹。6.4.1 中序遍歷中序遍歷的

24、順序?yàn)椋鹤笞訕?-樹根 -右子樹，即沿樹的左子樹一直往下，直到無(wú)法前進(jìn)時(shí)退后到父結(jié)點(diǎn)， 而后再往右子樹一直往下。 如果右子樹也走完了就退回上層的左結(jié)點(diǎn)， 重復(fù)左、中、右的順序遍歷，下圖是【范例 5】中所給出的二叉樹，它的中序遍歷為： DBEACF 。中序遍歷的遞歸（回溯）算法如下：void Inorder(BinTreeNode *ptr)if(ptr!=NULL) Inorder(ptr-left); / 遍歷左子樹coutdata; / 訪問(wèn)樹根Inorder(ptr-right);/ 遍歷右子樹6.4.2 前序遍歷前序遍歷的順序?yàn)椋簶涓?- 左子樹 -右子樹，即從根結(jié)點(diǎn)開始處理，根結(jié)點(diǎn)處

25、理完后往左子樹走，直到無(wú)法前進(jìn)再處理右子樹。 【范例 5】的前序遍歷為 ABDECF 。前序遍歷的遞歸（回溯）算法如下：void Preorder(BinTreeNode *ptr)if(ptr!=NULL) coutdata; / 訪問(wèn)樹根Preorder(ptr-left);/ 遍歷左子樹Preorder(ptr-right); / 遍歷右子樹6.4.3 后序遍歷后序遍歷的順序?yàn)椋鹤笞訕?- 右子樹 -樹根。后序遍歷和前序遍歷相反，它是把左、右子樹的結(jié)點(diǎn)都處理完才處理樹根。 【范例 5】的后序遍歷為： DEBFCA 。后序遍歷的遞歸（回溯）算法如下：void Postorder(BinTr

26、eeNode *ptr)if(ptr!=NULL) Postorder(ptr-left);/ 遍歷左子樹Postorder(ptr-right); / 遍歷右子樹coutdata; / 訪問(wèn)樹根6.4.4 二叉樹的遍歷實(shí)例對(duì)【范例 5】中二叉樹，進(jìn)行中序、前序與后序遍歷的操作。并將其結(jié)果輸出，請(qǐng)與上 面的討論加以對(duì)照?！痉独绦颉繉?duì)【范例 5】中的二叉樹進(jìn)行中序、前序與后序遍歷，并輸出其結(jié)果。/*名稱： ch06_04.cpp示范：二叉樹的中序、前序、后序遍歷*/#includeusing namespace std;/二叉樹結(jié)點(diǎn)定義struct BinTreeNode char data;

27、/結(jié)點(diǎn)數(shù)據(jù)struct BinTreeNode *left,*right;/ 左、右指針;/建二叉樹BinTreeNode *MakeBinTree(char data,BinTreeNode *left,BinTreeNode *right)/ 以 data 為數(shù)據(jù) ,left,right 為左右子樹建樹BinTreeNode *newnode;newnode=new BinTreeNode;newnode-data=data;newnode-left=left;newnode-right=right;return newnode;/中序遍歷void Inorder(BinTreeNode

28、*ptr)if(ptr!=NULL) Inorder(ptr-left); / 遍歷左子樹coutdata; / 訪問(wèn)樹根Inorder(ptr-right);/ 遍歷右子樹/前序遍歷void Preorder(BinTreeNode *ptr)if(ptr!=NULL) coutdata; / 訪問(wèn)樹根Preorder(ptr-left);/ 遍歷左子樹Preorder(ptr-right); / 遍歷右子樹/后序遍歷void Postorder(BinTreeNode *ptr)if(ptr!=NULL) Postorder(ptr-left);/ 遍歷左子樹Postorder(ptr-r

29、ight); / 遍歷右子樹coutdata; / 訪問(wèn)樹根/主函數(shù)void main()BinTreeNode *aptr,*bptr,*cptr,*dptr,*eptr,*fptr;dptr=MakeBinTree(D,NULL,NULL);eptr=MakeBinTree(E,NULL,NULL);fptr=MakeBinTree(F,NULL,NULL);bptr=MakeBinTree(B,dptr,eptr);cptr=MakeBinTree(C,NULL,fptr);aptr=MakeBinTree(A,bptr,cptr);/aptr 成為二叉樹的根結(jié)點(diǎn)指針cout 中序遍歷為

30、 :endl;Inorder(aptr);coutendl;cout 前序遍歷為 :endl;Preorder(aptr);coutendl;cout 后序遍歷為 :endl;Postorder(aptr);coutendl;system(pause);（對(duì)于一維數(shù)組所表示的二叉樹如何建立它的中序、 前序、 后序遍歷函數(shù)， 請(qǐng)參見實(shí)驗(yàn)教程。另外，二叉樹的插入與刪除操作也較復(fù)雜，請(qǐng)參考相關(guān)資料。 ）【范例 6】利用后序遍歷法，給出下圖的遍歷結(jié)果。解答：后序遍歷的順序?yàn)椋鹤笞訕?-右子樹 -樹根，可得 DBHEGIFCA ?！痉独?7】給出下圖所示的二叉樹的中序、前序及后序表示法。解答：中序： F

31、DHGIBEAC前序： ABDFGHIEC后序： FHIGDEBCA6.4.5 二元運(yùn)算樹一般的算術(shù)運(yùn)算可以轉(zhuǎn)換成二元運(yùn)算樹，其創(chuàng)建的方法如下：考慮算術(shù)式中運(yùn)算符的結(jié)合性與優(yōu)先權(quán)后先適當(dāng)加上括號(hào)。由最內(nèi)層的括號(hào)逐步向外， 利用運(yùn)算符當(dāng)樹根， 左邊的運(yùn)算對(duì)象當(dāng)左子樹，右邊的運(yùn)算對(duì)象當(dāng)右子樹，其中優(yōu)先權(quán)最低的運(yùn)算符作為此二元運(yùn)算樹的樹根。下面，以算術(shù)表達(dá)式“ A-B*(-C+-3.5)原表達(dá)式一目運(yùn)算符負(fù)號(hào)具有最高優(yōu)先級(jí) 乘法運(yùn)算符具有次高優(yōu)先級(jí)減法運(yùn)算符具有最低優(yōu)先級(jí)”為例，介紹這一問(wèn)題的處理方法。A-B*(-C+-3.5)A-B*(-C)+(-3.5)A-(B*(-C)+(-3.5)(A-(B

32、*(-C)+(-3.5)構(gòu)造二元運(yùn)算樹的過(guò)程如下圖所示：前序表示式為 -A*B+-C-3.5 ，后序表示式為 ABC-3.5-+*- 。6.5 排序二叉樹設(shè)結(jié)點(diǎn)由關(guān)鍵字值來(lái)表示，且所有結(jié)點(diǎn)的關(guān)鍵字值互異，排序二叉樹或者是一棵空樹，或者是滿足以下條件的樹：（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)的關(guān)鍵字值；（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)的關(guān)鍵字值；（3）左、右子樹也分別是二叉排序樹。根據(jù)排序二叉樹的定義，創(chuàng)建排序二叉樹的規(guī)則如下：第一個(gè)輸入的數(shù)據(jù)作為此二叉樹的樹根。其后的數(shù)據(jù)與根進(jìn)行比較，小于樹根的放置到左子樹，大于樹根的放置到右子樹。從上面的規(guī)

33、則可以知道， 左子樹內(nèi)的值一定小于樹根， 右子樹的值一定大于樹根。 因此，利用中序遍歷就可以得到由小到大排好序的數(shù)據(jù)?！痉独?8】利用數(shù)據(jù) 32 、 25 、 16 、 35 、 27 來(lái)建立一棵排序二叉樹。創(chuàng)建過(guò)程由下圖所示：【范例程序】用程序創(chuàng)建排序二叉樹。/*名稱： ch06_05.cpp示范：排序二叉樹的創(chuàng)建*/#includeusing namespace std;#define NodeNum 5/ 結(jié)點(diǎn)數(shù)struct BinTreeNode/ 二叉樹結(jié)點(diǎn)定義 int data;/ 結(jié)點(diǎn)數(shù)據(jù)struct BinTreeNode *left,*right;/ 左、右指針;BinTre

34、eNode *rootNode=NULL;/ 排序二叉樹的根結(jié)點(diǎn)指針/判空int IsEmpty()if(rootNode=NULL)return 1;elsereturn 0;/創(chuàng)建排序二叉樹void CreateSortBinTree(int data) BinTreeNode *ptr,*newnode;/建立新結(jié)點(diǎn)newnode=new BinTreeNode;newnode-data=data;newnode-left=NULL;newnode-right=NULL;int flag=0;/ 新結(jié)點(diǎn)是否入樹標(biāo)識(shí) ,flag=0 表示未入樹if(IsEmpty()/ 空樹rootNod

35、e=newnode;else/非空樹 ptr=rootNode;/ 探測(cè)指針指向根結(jié)點(diǎn)while(!flag)/ 當(dāng)新結(jié)點(diǎn)未入樹時(shí) /如果新結(jié)點(diǎn)關(guān)鍵字值小于其父結(jié)點(diǎn)的關(guān)鍵字值if(datadata) / 進(jìn)入左子樹if(ptr-left=NULL)/ 如果左子樹為空 ptr-left=newnode;/ 直接作為左子樹flag=1;/ 標(biāo)識(shí)符置 1，表示已入樹else/如果左子樹非空ptr=ptr-left;/ 探測(cè)指針向左下移else/如果新結(jié)點(diǎn)關(guān)鍵字值大于其父結(jié)點(diǎn)的關(guān)鍵字值 /中序遍歷/進(jìn)入右子樹if(ptr-right=NULL) ptr-right=newnode;flag=1;els

36、eptr=ptr-right;void Inorder(BinTreeNode *ptr) if(ptr!=NULL)Inorder(ptr-left);/ 遍歷左子樹coutdataright);/ 遍歷右子樹/主函數(shù)void main() int data;cout請(qǐng)輸入二叉樹結(jié)點(diǎn)的值 endl;for(int i=0;iNodeNum;i+) cout 請(qǐng)輸入第 i+1data;CreateSortBinTree(data);/ 創(chuàng)建排序二叉樹cout 中序遍歷為 :endl;Inorder(rootNode);coutendl;system(pause);排序二叉樹的突出優(yōu)點(diǎn)是： 將結(jié)

37、點(diǎn)按關(guān)鍵字值進(jìn)行了中序排序， 結(jié)點(diǎn)按關(guān)鍵字值的插入、查找操作變得極為簡(jiǎn)單。因此，有時(shí)也稱排序二叉樹為線索二叉樹（或二分查找樹） ?！痉独?9】利用數(shù)據(jù) 32、 25 、 16 、 35 、 27 先建一棵排序二叉樹，并畫出該排序二叉樹的結(jié) 構(gòu)圖。再將數(shù)據(jù) 33、 40 插入，再畫出其結(jié)構(gòu)圖。并用程序驗(yàn)證你的結(jié)果。解答：由范例 9 可知， 32 、 25 、 16 、 35 、 27 構(gòu)建的排序二叉樹為按照排序二叉樹的構(gòu)建原理， 33 大于根結(jié)點(diǎn)的關(guān)鍵字值 32，它向右子樹插入，又因右子樹結(jié)點(diǎn)的關(guān)鍵字值為 35， 33 小于 35，故它成為右子樹的左小孩。40 大于 32， 它向右子樹插入， 4

38、0 大于 35， 它又要向右插入， 故 40 為結(jié)點(diǎn) 35 的右子孩。其排序二叉樹為【范例程序】對(duì)排序二叉樹進(jìn)行插入操作。/*名稱： ch06_06.cpp示范：排序二叉樹的插入操作*/#includeusing namespace std;#define NodeNum 5/ 結(jié)點(diǎn)數(shù)struct BinTreeNode/ 二叉樹結(jié)點(diǎn)定義 int data;/ 結(jié)點(diǎn)數(shù)據(jù)struct BinTreeNode *left,*right;/ 左、右指針;BinTreeNode *rootNode=NULL;/ 排序二叉樹的根結(jié)點(diǎn)指針/判空int IsEmpty()if(rootNode=NULL)r

39、eturn 1;elsereturn 0;/創(chuàng)建排序二叉樹void CreateSortBinTree(int data) BinTreeNode *ptr,*newnode;/建立新結(jié)點(diǎn)newnode=new BinTreeNode;newnode-data=data;newnode-left=NULL;newnode-right=NULL;int flag=0;/ 新結(jié)點(diǎn)是否入樹標(biāo)識(shí) ,flag=0 表示未入樹if(IsEmpty()/ 空樹rootNode=newnode;else/非空樹 ptr=rootNode;/ 探測(cè)指針指向根結(jié)點(diǎn)while(!flag)/ 當(dāng)新結(jié)點(diǎn)未入樹時(shí) /如

40、果新關(guān)鍵字值小于其父結(jié)點(diǎn)的關(guān)鍵字值if(datadata) / 進(jìn)入左子樹if(ptr-left=NULL)/ 如果左子樹為空 ptr-left=newnode;/ 直接作為左子樹flag=1;/ 標(biāo)識(shí)符置 1，表示已入樹else/如果左子樹非空ptr=ptr-left;/ 探測(cè)指針向左下移else/如果新關(guān)鍵字值大于或等于其父結(jié)點(diǎn)的關(guān)鍵字值 /進(jìn)入右子樹if(ptr-right=NULL) ptr-right=newnode;flag=1;elseptr=ptr-right;/中序遍歷void Inorder(BinTreeNode *ptr) if(ptr!=NULL)Inorder(pt

41、r-left);/ 遍歷左子樹coutdataright);/ 遍歷右子樹/主函數(shù)void main()int data;cout請(qǐng)輸入二叉樹結(jié)點(diǎn)的值 endl;for(int i=0;iNodeNum;i+) cout 請(qǐng)輸入第 i+1data;CreateSortBinTree(data);/ 創(chuàng)建排序二叉樹cout 中序遍歷為 :endl;Inorder(rootNode);CreateSortBinTree(33);/ 插入 33CreateSortBinTree(40);/ 插入 40coutn 中序遍歷為： endl;Inorder(rootNode);coutendl;syste

42、m(pause);【范例程序】對(duì)于上例所創(chuàng)建的排序二叉樹，編程查找關(guān)鍵字值為 16 、 38，若找到了，顯示找到了的信息，否則顯示找不到的信息。/*名稱 ： ch06_07.cpp示范：利用排序二叉樹進(jìn)行查找操作*/#includeusing namespace std;#define NodeNum 7/ 結(jié)點(diǎn)數(shù)struct BinTreeNode/ 二叉樹結(jié)點(diǎn)定義 int data;/ 結(jié)點(diǎn)數(shù)據(jù)struct BinTreeNode *left,*right;/ 左、右指針;BinTreeNode *rootNode=NULL;/ 排序二叉樹的根結(jié)點(diǎn)指針/判空int IsEmpty()if(

43、rootNode=NULL)return 1;elsereturn 0;/創(chuàng)建排序二叉樹void CreateSortBinTree(int data) BinTreeNode *ptr,*newnode;/建立新結(jié)點(diǎn)newnode=new BinTreeNode;newnode-data=data;newnode-left=NULL;newnode-right=NULL;int flag=0;/ 新結(jié)點(diǎn)是否入樹標(biāo)識(shí) ,flag=0 表示未入樹if(IsEmpty()/ 空樹rootNode=newnode;else/非空樹 ptr=rootNode;/ 探測(cè)指針指向根結(jié)點(diǎn)while(!fla

44、g)/ 當(dāng)新結(jié)點(diǎn)未入樹時(shí) /如果新關(guān)鍵字值小于其父結(jié)點(diǎn)的關(guān)鍵字值if(datadata) / 進(jìn)入左子樹if(ptr-left=NULL)/ 如果左子樹為空 ptr-left=newnode;/ 直接作為左子樹flag=1;/ 標(biāo)識(shí)符置 1，表示已入樹else/如果左子樹非空ptr=ptr-left;/ 探測(cè)指針向左下移else/如果新關(guān)鍵字值大于或等于其父結(jié)點(diǎn)的關(guān)鍵字值 /進(jìn)入右子樹if(ptr-right=NULL) ptr-right=newnode;flag=1;elseptr=ptr-right;/中序遍歷void Inorder(BinTreeNode *ptr) if(ptr!=

45、NULL)Inorder(ptr-left);/ 遍歷左子樹coutdataright);/ 遍歷右子樹/查找關(guān)鍵字值BinTreeNode *Search(BinTreeNode *ptr,int keyVal)while(1) if(ptr=NULL) /沒(méi)有找到返回 NULLreturn NULL;if(ptr-data=keyVal)/ 結(jié)點(diǎn)值等于搜索值return ptr;else if(ptr-datakeyVal)/ 結(jié)點(diǎn)值大于搜索值ptr=ptr-left;/ 朝左子樹搜索else/結(jié)點(diǎn)值小于搜索值ptr=ptr-right;/ 朝右子樹搜索/主函數(shù)void main() in

46、t data;cout請(qǐng)輸入二叉樹結(jié)點(diǎn)的值 endl;for(int i=0;iNodeNum;i+) cout 請(qǐng)輸入第 i+1data;CreateSortBinTree(data);/ 創(chuàng)建排序二叉樹cout 中序遍歷為 :endl;Inorder(rootNode);while(1) coutdata;if (data=-1)break;else if(Search(rootNode,data)!=NULL)/ 搜索cout 你要找的值 data ，已找到 !endl;elsecout 你要找的值沒(méi)有找到 !k1=17 ， k0=32k2 ，符合最大堆要求，不作調(diào)整。 k3=24k1=

47、17 ，故交換。 k4=35k1=24 ，故交換。 k1=35k0=32 ，故交換。 k5=87k2 ，故交換；而交換之后的 k2=87k0=35 ，故再交換，使它的位置繼續(xù)上升（這就是上滑法的涵義） 。 k6=65k2=35 ，故交換。 k7=4k3=17 ，而 k8=12k3=17 ，故不交換。調(diào)整完畢，業(yè)已成為最大堆。此時(shí)，關(guān)鍵碼集合 K=87,32,65,17,24,16,35,4,12 。【范例程序】給出上述方法的程序演示。/*名稱 ： ch06_08.cpp示范：利用上滑法調(diào)最大堆*/#include#includeusing namespace std;#define NodeN

48、um 9 / 完全二叉樹的結(jié)點(diǎn)數(shù)/輸出void Display(int *data) for(int i=0;iNodeNum;i+)coutsetw(3)datai;cout0) if(temp=dataj)break;/雙親的值大 ,不做交換else datai=dataj;/ 交換i=j;/i 指向交換結(jié)點(diǎn)位置j=(i-1)/2;/j 指向雙親datai=temp;/ 原 datastart 歸位/創(chuàng)建最大堆void CreateHeap(int *data) int i,j;cout 原始數(shù)組 : ;Display(data);for(i=1;iNodeNum;i+)/ 從下標(biāo) 1 的

49、結(jié)點(diǎn)開始 ,采用上滑法調(diào)最大堆 SiftUpAdjustHeap(data,i);couti 次調(diào)堆 : ;Display(data);/主函數(shù)void main() int dataNodeNum=32,17,16,24,35,87,65,4,12;/ 完全二叉樹的結(jié)點(diǎn)值CreateHeap(data);/將 data 改造成最大堆system(pause);2. 下滑法調(diào)最大堆【范例 11】采用上滑法將關(guān)鍵碼集合K=32,17,16,24,35,87,65,4,12 調(diào)成一個(gè)最大堆。（1）將該關(guān)鍵碼集合按完全二叉樹存儲(chǔ)到數(shù)組 K ，其對(duì)應(yīng)的結(jié)構(gòu)圖是以下二叉樹。（2）這并非最大堆，采用下滑調(diào)

50、堆算法，可將它調(diào)成最大堆，具體步驟如下： 從下標(biāo)為 NodeNum/2=9/2=4 的結(jié)點(diǎn)開始， k4 無(wú)子女，不需要調(diào)。 再?gòu)南聵?biāo)為 3 的結(jié)點(diǎn)開始， k3 的值大于其子女的值，也不需要調(diào)。 再?gòu)南聵?biāo)為 2 的結(jié)點(diǎn)開始， k2=16k5=87 ，故交換。 再?gòu)南聵?biāo)為 1 的結(jié)點(diǎn)開始， k1=17k4=35 ，故交換。 再?gòu)南聵?biāo)為 0 的結(jié)點(diǎn)開始， k0=32k2 ，故交換。 由于 k2=32k6=65 ，故 k2 的位置繼續(xù)下滑（這就是下滑法的涵義所在） 交換。 調(diào)整完畢，業(yè)已成為最大堆。此時(shí)， 關(guān)鍵碼集合 K=87,35,65,24,17,16,32,4,12 ， 與上滑法做出的最大堆不一

51、樣，與 k6 做但仍是最大堆，這表明一棵完全二叉樹對(duì)應(yīng)的最大堆是不惟一的?！痉独绦颉拷o出下滑法調(diào)最大堆的程序演示。/*名稱 ： ch06_9.cpp示范：利用下滑法調(diào)最大堆*/#include#includeusing namespace std;#define NodeNum 9/ 完全二叉樹的結(jié)點(diǎn)數(shù)/輸出void Display(int *data)for(int i=0;iNodeNum;i+)coutdataisetw(4);coutendl;/下滑法調(diào)最大堆void SiftDownAdjustHeap(int *data,int start,int end)/ 從下標(biāo)為 star

52、t 的結(jié)點(diǎn)開始 , 到下標(biāo)為 end的結(jié)點(diǎn)為止 , 向下調(diào)堆int i,j,temp,flag;i=start;temp=datai;/temp 暫存結(jié)點(diǎn) i 的值j=2*i+1;/j 指向結(jié)點(diǎn) i 的左子女flag=0;/ 假設(shè)樹根值小 , 需要做交換while(j=end&flag=0) if(jend) if(dataj=dataj)flag=1;/ 若樹根較大 ,不做交換else datai=dataj;/ 交換i=j;/i 指向交換結(jié)點(diǎn)位置j=2*i+1;/j 指向其左子女datai=temp;/ 結(jié)點(diǎn)值歸位/創(chuàng)建最大堆void CreateHeap(int *data) int i

53、;cout=0;i-)/ 從完全二叉樹的首個(gè)非葉子結(jié)點(diǎn)開始 ,采用下滑調(diào)最大堆 SiftDownAdjustHeap(data,i,NodeNum-1);coutNodeNum/2-i 次調(diào)堆 : ;Display(data);/主函數(shù)void main()int dataNodeNum=32,17,16,24,35,87,65,4,12;/ 完全二叉樹的結(jié)點(diǎn)值CreateHeap(data);/將 data 改造成最大堆system(pause);將上滑法、 下滑法調(diào)最大堆的程序稍作改動(dòng)， 可得到調(diào)最小堆的程序代碼， 這里不作敘述，留作練習(xí)。6.7 哈夫曼樹在學(xué)習(xí)本節(jié)內(nèi)容之前，讓我們先處理一

54、個(gè)實(shí)際問(wèn)題：在某通信系統(tǒng)中，要發(fā)送由 A 、 B 、 C 、 D 四個(gè)字符組成的信息， A 出現(xiàn)的概率為 0.5，B 出現(xiàn)的概率為 0.25， C 出現(xiàn)的概率為 0.1， D 出現(xiàn)的概率為 0.15。如何對(duì) A 、 B 、 C、 D 四個(gè)字符進(jìn)行編碼，能使總的編碼長(zhǎng)度最短？分析：對(duì)于該問(wèn)題，讀者很容易想到用如下表 6.1 所示：表 6.1 等長(zhǎng)編碼字符ABC2 位等長(zhǎng)的二進(jìn)制數(shù) (0 或 1)。其具體表示方法字符編碼000110D 11在 10000 次的通信過(guò)程中，通信傳輸?shù)拈L(zhǎng)度L=( 2 0.5+2 0.25+2 0.1+2 0.15) 10000=20000 個(gè) bit假定按表 6.2

55、編碼表 6.2 不等長(zhǎng)編碼字符 字符編碼A 0B 10C 110D 111在 10000 次的通信過(guò)程中，通信傳輸?shù)拈L(zhǎng)度為L(zhǎng)=( 1 0.5+2 0.25+3 0.1+3 0.15) 10000=14500 個(gè) bit顯然第二種編碼方案優(yōu)于第一種編碼方案， 因?yàn)橥ㄐ胚^(guò)程中出現(xiàn)次數(shù)較多的字符采用了較短編碼，而出現(xiàn)次發(fā)數(shù)較少的字符則采用較長(zhǎng)編碼，從而使總的編碼長(zhǎng)度變短為什么不同的編碼方案會(huì)出現(xiàn)不同的效果？第二種編碼較優(yōu)的理論根據(jù)是什么？它是最好的編碼嗎？如何編碼能夠使得存儲(chǔ)效率高？在學(xué)習(xí)哈夫曼樹之后， 我們就能夠回答這些問(wèn)題了。首先介紹有關(guān)哈夫曼樹的基本術(shù)語(yǔ)和基本概念。6.7.1 基本術(shù)語(yǔ)路徑 (

56、path) 從樹中一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間路徑。路徑長(zhǎng)度 (path length) 路徑上的分支數(shù)目。樹的路徑長(zhǎng)度 (tree path length) 根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和。樹的帶權(quán)路徑長(zhǎng)度 (weighted path length) 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，且記作nWPL wil ii1其中 wi 是第 i 個(gè)葉子結(jié)點(diǎn)的權(quán)值， li 為從根到第 i 個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度， n為樹的葉子結(jié)點(diǎn)的個(gè)數(shù)。最優(yōu)二叉樹 (Huffman 哈夫曼樹 ) 設(shè)有 n個(gè)權(quán)值 w1 , w2 , , wn ，構(gòu)造一棵有 n個(gè)葉子結(jié)點(diǎn)的二叉樹，第 i 個(gè)葉子結(jié)點(diǎn)的

57、權(quán)值為 wi ，則帶權(quán)路徑長(zhǎng)度 WPL 最小的二叉樹被稱作最優(yōu)二叉樹，又稱哈夫曼樹 (Huffman) ?！痉独?12】對(duì)下圖所給出的三棵二叉樹，試分別計(jì)算葉子結(jié)點(diǎn)的 WPL 值。解答：（1） WPL= 9 1+152+33+43=60（2） WPL= 15 1+92+33+43=54（3） WPL= 4 1+152+93+33=70可見，第 (2) 棵二叉樹的 WPL 值最小。6.7.2 哈夫曼算法1952 年哈夫曼 （D.A.Huffman ）針對(duì)如何減少通信系統(tǒng)中字符編碼所需的二進(jìn)制位長(zhǎng)度， 提出了用于產(chǎn)生不定長(zhǎng)的前綴編碼算法，所謂前綴編碼是指任一編碼都不是其他編碼的前綴。 由本節(jié)開始所

58、給出的例子可知， 前綴編碼算法的基本思想就是對(duì)于出現(xiàn)概率較大的字符采用短編碼方式， 而出現(xiàn)概率較小的字符采用長(zhǎng)編碼方式。 哈夫曼提出的算法能夠使得其構(gòu)造的二叉樹的 WPL 值最小，從而保證在通信過(guò)程中，傳輸二進(jìn)制位總長(zhǎng)度最短。該算法主要是根據(jù)給定的不同字符的出現(xiàn)概率 （或頻數(shù)） 建立一棵最優(yōu)二叉樹， 通常也稱它為哈夫曼樹。哈夫曼樹應(yīng)用十分廣泛，哈夫曼算法也是數(shù)據(jù)庫(kù)壓縮最基本的算法之一。哈夫曼樹的具體構(gòu)造算法描述如下：根據(jù)給定的 n 個(gè)權(quán)值w 1， w2， wn ，構(gòu)成 n棵二叉樹的集合 T=T 1，T2， Tn ，其中每個(gè) Ti 只有一個(gè)帶權(quán)為 wi 的根結(jié)點(diǎn)，其左右子樹均為空。從 T 中選兩

59、棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹，不妨設(shè)為 Ti， Tj 并作為左右子樹構(gòu)成一棵新的二叉樹 Tk， 并用置新二叉樹的根值為左右子樹的根結(jié)點(diǎn)的權(quán)值之和。從 T 中刪除 Ti， Tj ，再將 Tk 并入 T 中。重復(fù)第 2、 3 步，直到 T 中只有一棵樹為止。這棵樹便是哈夫曼樹。下面就以具體實(shí)例來(lái)說(shuō)明哈夫曼算法的思想與哈夫曼樹的構(gòu)造過(guò)程?！痉独?13】設(shè)集合 3， 4， 5， 6， 8， 10， 12， 18 為葉子結(jié)點(diǎn)的權(quán)值。（1）、構(gòu)造其哈夫曼樹；（2）、計(jì)算該哈夫曼樹的 WPL；（3）、假設(shè)權(quán)值集合中的元素分別代表字符a、 b 、 c、 d、 e、 f 、 g、 h 在一個(gè)文本中出現(xiàn)的頻次，請(qǐng)你

60、為這些字符設(shè)計(jì)一種不定長(zhǎng)的前綴二進(jìn)制編碼。解答（ 1）：第 1 步 將這些數(shù)變成單結(jié)點(diǎn)的二叉樹集合，使 T 變?yōu)椋旱?2 步 選出兩棵根值最小的二叉樹，作為左右子樹，造棵新二叉樹，使 T 變?yōu)椋旱?3 步 再選出兩棵根值最小的二叉樹，作為左右子樹，再造棵新二叉樹，使 T 變?yōu)椋旱?4 步 以下可類似地處理，可使 T 變?yōu)椋旱?5 步 T 又變?yōu)椋旱?6 步 T 又變?yōu)椋旱?7 步 T 又變?yōu)椋旱?8 步 T 最終變?yōu)橐韵滦问?，它已成為了一棵哈夫曼樹。解答?2）： WPL =12 2+182+8 3+103+34+4 4+54+64=186解答（ 3）：不定長(zhǎng)的前綴二進(jìn)制編碼方案：首先將哈夫曼