數(shù)據(jù)結(jié)構(gòu)單元4樹(shù)與二叉樹(shù)課件

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)目標(biāo) 【知識(shí)目標(biāo)】理解樹(shù)的邏輯結(jié)構(gòu)和基本術(shù)語(yǔ)理解二叉樹(shù)的遞歸定義，掌握二叉樹(shù)的性質(zhì)掌握二叉樹(shù)的遍歷，能確定遍歷所得到的結(jié)點(diǎn)訪問(wèn)序列掌握二叉樹(shù)的存儲(chǔ)方法和二叉樹(shù)的基本操作的算法掌握樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換方法能根據(jù)給定的葉結(jié)點(diǎn)及其權(quán)值構(gòu)造出相應(yīng)的最優(yōu)二叉樹(shù)能根據(jù)最優(yōu)二叉樹(shù)構(gòu)造對(duì)應(yīng)的哈夫曼編碼【能力目標(biāo)】具有用樹(shù)來(lái)描述現(xiàn)實(shí)世界、應(yīng)用二叉樹(shù)解決實(shí)際問(wèn)題的能力具有恰當(dāng)?shù)倪x擇二叉樹(shù)作為數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的能力引例描述文本文件的加密和解密 某公司有一份機(jī)密文件，是由英文字母（包括大小寫(xiě)）、英文逗號(hào)、英文句點(diǎn)、空格和回車(chē)換行等符號(hào)組成的文件名為Jimi.txt的文本文件。公司為保證文件不

2、被泄密，要求技術(shù)人員將文件中的每個(gè)字符都用一個(gè)二進(jìn)制位串進(jìn)行加密，需要時(shí)能進(jìn)行解密，但必須保證加密后的文件不要過(guò)大，且對(duì)加密的文件進(jìn)行解密后與原文件必須完全一致。如果你是技術(shù)人員，你將如何按要求為公司的文件進(jìn)行加密和解密呢？ 演示執(zhí)行 一、樹(shù)的遞歸定義 1.定義 樹(shù)（Tree）是n(n0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹(shù)，否則它滿足如下兩個(gè)條件：有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)；其余的結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限子集Tl，T2，Tm，其中每個(gè)子集本身又是一棵樹(shù)，并稱其為根的子樹(shù)（SubTree）。 4.1 樹(shù)的概念 知識(shí)儲(chǔ)備2樹(shù)的表示 樹(shù)形圖表示：結(jié)點(diǎn)用圓圈表示，結(jié)點(diǎn)名字寫(xiě)

3、在圓圈旁或圓圈內(nèi)，子樹(shù)與其根之間用無(wú)向邊來(lái)連接，如圖4-1是樹(shù)形圖表示表示的樹(shù)T1。 嵌套集合表示法：用集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)，如圖4-2是樹(shù)T1的嵌套集合表示。 凹入表表示法：類(lèi)似于書(shū)的目錄。圖4-1 樹(shù)T1的樹(shù)形圖表示ABCDEFIJGH圖4-2 樹(shù)T1的嵌套集合表示EIJGHABDCF二、樹(shù)結(jié)構(gòu)的基本術(shù)語(yǔ) 1結(jié)點(diǎn)的度 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。樹(shù)的度：該樹(shù)中結(jié)點(diǎn)的最大度數(shù)稱為該樹(shù)的度。葉子結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。即除葉子結(jié)點(diǎn)外的結(jié)點(diǎn)均為分支結(jié)點(diǎn)。內(nèi)部結(jié)點(diǎn)：除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。開(kāi)始結(jié)

4、點(diǎn)：根結(jié)點(diǎn)又稱為開(kāi)始結(jié)點(diǎn)。【示例】圖4-1表示的樹(shù)T1中結(jié)點(diǎn)A的度為3，其它結(jié)點(diǎn)的度都為2或0。【示例】圖4-1表示的樹(shù)T1的度為3。【示例】圖4-1表示的樹(shù)T1中結(jié)點(diǎn)C、E、G、H、I、J都是葉子結(jié)點(diǎn)?！臼纠繄D4-1表示的樹(shù)T1中結(jié)點(diǎn)A、B、D、F都是分支結(jié)點(diǎn)?！臼纠繄D4-1表示的樹(shù)T1中結(jié)點(diǎn)A是開(kāi)始結(jié)點(diǎn)。2結(jié)點(diǎn)之間的關(guān)系孩子（Child）結(jié)點(diǎn)：樹(shù)中某個(gè)結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。雙親（Parent）結(jié)點(diǎn)：孩子結(jié)點(diǎn)的根稱為該結(jié)點(diǎn)的雙親。兄弟結(jié)點(diǎn)：同一個(gè)雙親的孩子互稱為兄弟結(jié)點(diǎn)。堂兄弟：在后面介紹。祖先和子孫：在后面介紹。 【示例】圖4-1表示的樹(shù)T1中結(jié)點(diǎn)B、C、D都是結(jié)點(diǎn)A的孩

5、子結(jié)點(diǎn)，結(jié)點(diǎn)E、F都是結(jié)點(diǎn)B的孩子結(jié)點(diǎn)，結(jié)點(diǎn)G、H都是結(jié)點(diǎn)D的孩子結(jié)點(diǎn)。【示例】圖4-1表示的樹(shù)T1中結(jié)點(diǎn)A是結(jié)點(diǎn)B、C、D的雙親結(jié)點(diǎn)，結(jié)點(diǎn)B是結(jié)點(diǎn)E、F的雙親結(jié)點(diǎn)，結(jié)點(diǎn)D是結(jié)點(diǎn)G、H的雙親結(jié)點(diǎn)。【示例】圖4-1表示的樹(shù)T1中結(jié)點(diǎn)B、C、D互為兄弟結(jié)點(diǎn)，結(jié)點(diǎn)E、F互為兄弟結(jié)點(diǎn)，而結(jié)點(diǎn)F和G非兄弟結(jié)點(diǎn)。3路徑路徑或道路：若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列k1,k2,kj,使得ki是ki+1的雙親(1ij)，則稱該結(jié)點(diǎn)序列是從kl到kj的一條路徑或道路。路徑的長(zhǎng)度：指路徑所經(jīng)過(guò)的邊的數(shù)目。注意：若一個(gè)結(jié)點(diǎn)序列是路徑，則在樹(shù)的樹(shù)形圖表示中，該結(jié)點(diǎn)序列“自上而下”地通過(guò)路徑上的每條邊。從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均

6、存在一條惟一的路徑。 祖先和子孫：若樹(shù)中結(jié)點(diǎn)k到ks存在一條路徑，則稱k是ks的祖先，ks是k的子孫。一個(gè)結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)過(guò)的所有結(jié)點(diǎn)，而一個(gè)結(jié)點(diǎn)的子孫則是以該結(jié)點(diǎn)為根的子樹(shù)中的所有結(jié)點(diǎn)。約定：結(jié)點(diǎn)k的祖先和子孫不包含結(jié)點(diǎn)k本身。 【示例】圖4-1表示的樹(shù)T1中結(jié)點(diǎn)序列ABFI是結(jié)點(diǎn)A到I的一條路徑，因?yàn)樽陨隙翧是B的雙親，B是F的雙親，F(xiàn)是I的雙親。該路徑的長(zhǎng)度為3。而結(jié)點(diǎn)B和G之間不存在路徑，因?yàn)榧炔荒軓腂出發(fā)自上而下地經(jīng)過(guò)若干個(gè)結(jié)點(diǎn)到達(dá)G，也不能從G出發(fā)自上而下地經(jīng)過(guò)若干個(gè)結(jié)點(diǎn)到達(dá)B。4結(jié)點(diǎn)的層數(shù)和樹(shù)的深度結(jié)點(diǎn)的層數(shù)：根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)

7、的層數(shù)加1。堂兄弟：雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹(shù)的深度：樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的深度。注意：要弄清結(jié)點(diǎn)的度、樹(shù)的度和樹(shù)的深度的區(qū)別。5有序樹(shù)和無(wú)序樹(shù)若將樹(shù)中每個(gè)結(jié)點(diǎn)的各子樹(shù)看成是從左到右有次序的，則稱該樹(shù)為有序樹(shù)；否則稱為無(wú)序樹(shù)。若不特別指明，一般討論的樹(shù)都是有序樹(shù)。6森林（Forest）森林是m(m0)棵互不相交的樹(shù)的集合。刪去一棵樹(shù)的根，就得到一個(gè)森林；反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變?yōu)橐豢脴?shù)。三、樹(shù)型結(jié)構(gòu)的邏輯特征 1樹(shù)中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼結(jié)點(diǎn)，但至多只能有一個(gè)直接前驅(qū)結(jié)點(diǎn)。2樹(shù)中只有根結(jié)點(diǎn)無(wú)前驅(qū)，它是開(kāi)始結(jié)點(diǎn)；葉結(jié)點(diǎn)無(wú)后繼，它們是終端結(jié)點(diǎn)。3祖先與子孫的關(guān)系是對(duì)

8、父子關(guān)系的延拓，它定義了樹(shù)中結(jié)點(diǎn)之間的縱向次序。4有序樹(shù)中，同一組兄弟結(jié)點(diǎn)從左到右有長(zhǎng)幼之分。對(duì)這一關(guān)系加以延拓，規(guī)定若k1和k2是兄弟，且k1在k2的左邊，則kl的任一子孫都在k2的任一子孫的左邊，那么就定義了樹(shù)中結(jié)點(diǎn)之間的橫向次序。 樹(shù)中結(jié)點(diǎn)之間的邏輯關(guān)系是“一對(duì)多”的關(guān)系，樹(shù)是一種非線性的結(jié)構(gòu)。 【課堂實(shí)踐4-1】 已知在一棵度為3的樹(shù)中，度為2的結(jié)點(diǎn)數(shù)為4，度為3的結(jié)點(diǎn)數(shù)為3，求該樹(shù)中的葉子結(jié)點(diǎn)數(shù)。 提示：分別從樹(shù)的結(jié)點(diǎn)總數(shù)和樹(shù)的孩子結(jié)點(diǎn)總數(shù)兩個(gè)角度考慮。 做一做一、二叉樹(shù)的定義 1.二叉樹(shù)的遞歸定義 二叉樹(shù)（Binary Tree）是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，

9、或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 2二叉樹(shù)的五種基本形態(tài) 二叉樹(shù)可以是空集；可以有空的左子樹(shù)或空的右子樹(shù)；或者左、右子樹(shù)皆為空。 二叉樹(shù)的五種基本形態(tài)如圖4-3。 4.2 二叉樹(shù)及其性質(zhì) 圖4-3 二叉樹(shù)的五種基本形態(tài)(a)(b)(c)(d)(e)二、二叉樹(shù)的性質(zhì)1性質(zhì)性質(zhì)1：二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為2i-1(i1)個(gè)。性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1(k1)個(gè)結(jié)點(diǎn)。性質(zhì)3：在任意一棵非空二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。性質(zhì)3說(shuō)明：在任意非空二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)數(shù)多1個(gè)。證明： 假

10、設(shè)樹(shù)非空，用數(shù)學(xué)歸納法證明。 當(dāng)i=1時(shí)，因?yàn)榈?層上只有一個(gè)根結(jié)點(diǎn)，而2i-1=20=1。所以命題成立。 假設(shè)對(duì)所有的j(1j2k-1-1。另一方面，由性質(zhì)2知：深度為k的二叉樹(shù)至多有2k-1(k1)個(gè)結(jié)點(diǎn)，因此，n2k-1，即：2k-1-ln2k-1，由此可推出：2k-1n2k，取對(duì)數(shù)后有：k-1lgnk又因k-1和k是相鄰的兩個(gè)整數(shù)，故有 另外，由2k-1-ln2k-1得2k-11，則ki的雙親編號(hào)為i/2；若i=1，則ki是根結(jié)點(diǎn)，無(wú)雙親。（ii）若2in，則ki的左孩子的編號(hào)是2i；若2in，則ki無(wú)左孩子，因此也無(wú)右孩子，即ki必定是葉子。因此完全二叉樹(shù)中編號(hào)in/2的結(jié)點(diǎn)必定是葉

11、結(jié)點(diǎn)。 （iii）若i為奇數(shù)且不為1，則ki是結(jié)點(diǎn)ki/2的右孩子，ki的左兄弟的編號(hào)是i-1；若i=1或i為偶數(shù)，則ki無(wú)左兄弟。（iv）若i為偶數(shù)且小于n，則ki是結(jié)點(diǎn)ki/2的左孩子， ki的右兄弟的編號(hào)是i+1；若i=n或i為奇數(shù)，則ki無(wú)右兄弟。 由此可知，完全二叉樹(shù)中結(jié)點(diǎn)的編號(hào)序列，完全反映了結(jié)點(diǎn)之間的邏輯關(guān)系?！菊n堂實(shí)踐4-3】 已知一棵完全二叉樹(shù)含1000個(gè)結(jié)點(diǎn)，分別求該二叉樹(shù)的度為2的結(jié)點(diǎn)數(shù)、度為1的結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)。 做一做（2）完全二叉樹(shù)的順序存儲(chǔ) 將完全二叉樹(shù)中所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)向量bt0n中。其中：bt1n用來(lái)存儲(chǔ)結(jié)點(diǎn)，bt0不用或用來(lái)存儲(chǔ)結(jié)點(diǎn)數(shù)目。說(shuō)

12、明：完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單又節(jié)省存儲(chǔ)空間；按這種方法存儲(chǔ)的完全二叉樹(shù)，向量元素bti的下標(biāo)i就是對(duì)應(yīng)結(jié)點(diǎn)的編號(hào)。【示例】圖4-7所示的完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如圖4-8。圖4-8 完全二叉樹(shù)BT3的順序存儲(chǔ)BT3ABCDEFGHIJKL12下標(biāo)01234567891011122一般二叉樹(shù)的順序存儲(chǔ)（1）具體方法將一般二叉樹(shù)添上一些“虛結(jié)點(diǎn)”，使其成為完全二叉樹(shù)；為了用結(jié)點(diǎn)在向量中的相對(duì)位置來(lái)表示結(jié)點(diǎn)之間的邏輯關(guān)系，按完全二叉樹(shù)形式給結(jié)點(diǎn)編號(hào)；將結(jié)點(diǎn)按編號(hào)存入向量對(duì)應(yīng)分量，其中“虛結(jié)點(diǎn)”用表示。（2）二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)是存儲(chǔ)結(jié)構(gòu)簡(jiǎn)單；缺點(diǎn)是可能浪費(fèi)大量的存儲(chǔ)空間。在最壞的

13、情況下，一個(gè)深度為k的且只有k個(gè)結(jié)點(diǎn)的右單支樹(shù)，需要2k-1個(gè)結(jié)點(diǎn)的存儲(chǔ)空間，浪費(fèi)了2k-1-k個(gè)存儲(chǔ)空間?！臼纠咳鐖D4-9的三個(gè)結(jié)點(diǎn)的添加上4個(gè)虛結(jié)點(diǎn)右單支樹(shù)的存儲(chǔ)結(jié)構(gòu)如圖4-10。圖4-9 添加虛結(jié)點(diǎn)右單支樹(shù)1BAC372456AB3C01234567下標(biāo)bt圖4-10 右單支樹(shù)的順序存儲(chǔ)結(jié)構(gòu)（3）二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)的描述#define MAXSIZE 50 /設(shè)置二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef char DataType; /定義結(jié)點(diǎn)類(lèi)型typedef struct /定義二叉樹(shù)結(jié)構(gòu)DataType btMAXSIZE; /存放二叉樹(shù)的結(jié)點(diǎn)int num; /存放二叉樹(shù)的結(jié)點(diǎn)數(shù)Seq

14、BT;注：如果使用元素bt0存放二叉樹(shù)的結(jié)點(diǎn)數(shù)，成員num可省略或不定義結(jié)構(gòu)而只定義數(shù)組。 二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1結(jié)點(diǎn)的結(jié)構(gòu)：二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。用鏈接方式存儲(chǔ)二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針域lchild和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)的結(jié)構(gòu)如圖4-11。 2結(jié)點(diǎn)的類(lèi)型描述說(shuō)明： 定義新類(lèi)型BinTree為指向BinTNode類(lèi)型結(jié)點(diǎn)的指針類(lèi)型，用于定義指向根結(jié)點(diǎn)的指針。 圖4-11 結(jié)點(diǎn)的結(jié)構(gòu) lchild data rchildtypedef char DataType; /定義結(jié)點(diǎn)數(shù)據(jù)域類(lèi)型typedef struct n

15、ode/定義結(jié)點(diǎn)結(jié)構(gòu)DataType data；struct node *lchild，*rchild； /左右孩子指針BinTNode； /結(jié)點(diǎn)類(lèi)型typedef BinTNode *BinTree；3二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表 在一棵二叉樹(shù)中，所有類(lèi)型為BinTNode的結(jié)點(diǎn)，再加上一個(gè)指向開(kāi)始結(jié)點(diǎn)（即根結(jié)點(diǎn)）的BinTree型頭指針（即根指針）root，就構(gòu)成了二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并將其稱為二叉鏈表。說(shuō)明：一個(gè)二叉鏈表由根指針root惟一確定。若二叉樹(shù)為空，則root=NULL；若結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針為空。具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有2n個(gè)指針域。其中只有n-1個(gè)用來(lái)

16、指示結(jié)點(diǎn)的左、右孩子，其余的n+1個(gè)指針域?yàn)榭铡ＷC明：因?yàn)槎鏄?shù)中結(jié)點(diǎn)總數(shù)n等于0度結(jié)點(diǎn)數(shù)n0、1度結(jié)點(diǎn)數(shù)n1和2度結(jié)點(diǎn)數(shù)n2之和：n=n0+n1+n2 由二叉樹(shù)的性質(zhì)3：n0=n2+1，所以， n1+2n2=n-1。而在二叉鏈表中，度為1的結(jié)點(diǎn)有一個(gè)指針域不空，度為2的結(jié)點(diǎn)的兩個(gè)指針域都不空，即n個(gè)結(jié)點(diǎn)的二叉鏈表中共有n1+2n2個(gè)指針域不空，即n-1個(gè)指針域不空，分別指向左右孩子。因此，其余的n+1個(gè)指針域?yàn)榭铡?【示例】如圖4-12的二叉樹(shù)BT4的二叉鏈表如圖4-13。 圖4-12 二叉樹(shù)BT4ABCDEFGH圖4-13 二叉樹(shù)BT4的二叉鏈表rootABFEDHGC4帶雙親指針的二叉鏈

17、表三叉鏈表 經(jīng)常要在二叉樹(shù)中尋找某結(jié)點(diǎn)的雙親時(shí)，可在每個(gè)結(jié)點(diǎn)上再加一個(gè)指向其雙親的指針parent，形成一個(gè)帶雙親指針的二叉鏈表，也稱為三叉鏈表。 【示例】如圖4-12的二叉樹(shù)BT4的三叉鏈表如圖4-14。 圖4-12 二叉樹(shù)BT4ABCDEFGH圖4-14 二叉樹(shù)BT4的三叉鏈表GHFECDBAroot【課堂實(shí)踐4-4】 畫(huà)出如圖4-15的二叉樹(shù)BT5的二叉鏈表和三叉鏈表的存儲(chǔ)結(jié)構(gòu)。 做一做圖4-15 二叉樹(shù)BT5ABCDEGFH遍歷（Traversal）：是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題。 一、遍歷方案1遍歷方案：由于一

18、棵非空的二叉樹(shù)由根結(jié)點(diǎn)及左、右子樹(shù)這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：訪問(wèn)結(jié)點(diǎn)本身(N)；遍歷該結(jié)點(diǎn)的左子樹(shù)(L)；遍歷該結(jié)點(diǎn)的右子樹(shù)(R)。 以上三種操作有六種遍歷方案：NLR、LNR、LRN、NRL、RNL、RLN。由于前三種次序與后三種次序?qū)ΨQ，所以只討論先左后右的前三種次序。 4.4 二叉樹(shù)的遍歷 2三種遍歷的命名前（先）序遍歷NLR：訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前，又稱為先根遍歷。中序遍歷LNR：訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中（間），又稱為中根遍歷。后序遍歷LRN：訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后，又稱為后根遍歷。3遍歷規(guī)則及

19、算法中序遍歷的遞歸算法若二叉樹(shù)非空，則依次執(zhí)行如下操作：（i）遍歷左子樹(shù)；（ii）訪問(wèn)根結(jié)點(diǎn)；（iii）遍歷右子樹(shù)。中序遍歷的遞歸算法： void InOrder(BinTree T)if(T) /如果二叉樹(shù)非空InOrder(T-lchild); /遍歷左子樹(shù)printf(%c，T-data) /訪問(wèn)根結(jié)點(diǎn)InOrder(T-rchild); /遍歷右子樹(shù) 先序遍歷的遞歸算法若二叉樹(shù)非空，則依次執(zhí)行如下操作：（i）訪問(wèn)根結(jié)點(diǎn)； （ii）遍歷左子樹(shù)；（iii）遍歷右子樹(shù)。先序遍歷的遞歸算法： 后序遍歷得遞歸算法若二叉樹(shù)非空，則依次執(zhí)行如下操作：（i）遍歷左子樹(shù)；（ii）遍歷右子樹(shù)；（iii）訪

20、問(wèn)根結(jié)點(diǎn)。后序遍歷的遞歸算法： void PreOrder(BinTree T)if(T) /如果二叉樹(shù)非空printf(c，T-data); /訪問(wèn)根結(jié)點(diǎn)PreOrder(T-lchild); /遍歷左子樹(shù)PreOrder(T-rchild); /遍歷右子樹(shù) void PostOrder(BinTree T)if(T) /如果二叉樹(shù)非空 PostOrder(T-lchild); /遍歷左子樹(shù)PostOrder(T-rchild); /遍歷右子樹(shù)printf(c，T-data); /訪問(wèn)根結(jié)點(diǎn) 一、遍歷序列1中序序列：中序遍歷二叉樹(shù)時(shí)，按對(duì)結(jié)點(diǎn)的訪問(wèn)次序形成的結(jié)點(diǎn)序列稱為中序序列。說(shuō)明：在中序

21、遍歷序列中，根結(jié)點(diǎn)左邊的結(jié)點(diǎn)在根的左子樹(shù)上，根結(jié)點(diǎn)右邊的結(jié)點(diǎn)在根的右子樹(shù)上。2先序序列：先序遍歷二叉樹(shù)時(shí)，按對(duì)結(jié)點(diǎn)的訪問(wèn)次序形成的結(jié)點(diǎn)序列稱為先序序列。說(shuō)明：在先序遍歷序列中，最左邊的結(jié)點(diǎn)是根結(jié)點(diǎn)。3后序序列：后序遍歷二叉樹(shù)時(shí)，按對(duì)結(jié)點(diǎn)的訪問(wèn)次序形成的結(jié)點(diǎn)序列稱為后序序列。說(shuō)明：在后序遍歷序列中，最右邊的結(jié)點(diǎn)是根結(jié)點(diǎn)。 【示例】對(duì)如圖4-12的二叉樹(shù)BT4，求出它的中序遍歷、先序遍歷和后序遍歷序列。 【課堂實(shí)踐4-5】 寫(xiě)出如圖4-15的二叉樹(shù)T2的先序遍歷序列、中序遍歷序列和后序遍歷序列。 做一做圖4-15 二叉樹(shù)BT5ABCDEGFH4確定二叉樹(shù) 已知中序遍歷序列和先序遍歷序列或后序遍歷序

22、列可以確定一棵二叉樹(shù)。具體方法：先根據(jù)先序遍歷序列確定該二叉樹(shù)的根，再根據(jù)中序遍歷序列確定根的左子樹(shù)和右子樹(shù)上的結(jié)點(diǎn)，而對(duì)于左子樹(shù)和右子樹(shù)可用同樣的方法確定子樹(shù)的根和其左、右子樹(shù)上的結(jié)點(diǎn)，這樣便可確定該二叉樹(shù)?！臼纠恳阎豢枚鏄?shù)的中序遍歷序列和先序遍歷序列分別是：BGDAEHCF和ABDGCEHF，畫(huà)出這棵二叉樹(shù)。 【課堂實(shí)踐4-6】 已知二叉樹(shù)的先序序列和中序序列分別為ABDEHCFI和DBHEACIF，畫(huà)出該二叉樹(shù)的二叉鏈表存儲(chǔ)表示，并寫(xiě)出該二叉樹(shù)的后序序列。 做一做一、二叉鏈表的建立1基本思想 基于先序遍歷建立二叉鏈表，即以二叉樹(shù)的先序遍歷序列為輸入建立二叉鏈表。注：先序遍歷序列中須

23、加入虛結(jié)點(diǎn)以示空指針的位置。 如圖4-15的二叉樹(shù)BT5的帶虛結(jié)點(diǎn)的先序序列為： ABDGCEHF。2建立算法 以二叉樹(shù)的先序序列為輸入建立二叉鏈表，假設(shè)虛結(jié)點(diǎn)輸入時(shí)以空格字符表示，算法如下： 4.5 二叉樹(shù)的基本操作 void CreateBinTree (BinTree *T) /建立二叉鏈表。T是指向根指針的指針char ch；if(ch=getchar()= ) *T=NULL; /讀入空格，將相應(yīng)指針置空else /讀入非空格*T=(BinTNode *)malloc(sizeof(BinTNode);(*T)-data=ch；CreateBinTree(&(*T)-lchild);

24、 /建立左子樹(shù)CreateBinTree(&(*T)-rchild); /建立右子樹(shù) 二、二叉鏈表的基本操作1計(jì)算二叉樹(shù)深度分析： 如果二叉樹(shù)BT為空，即BT=NULL，則BT的深度為0； 如果二叉樹(shù)BT不空，則分別計(jì)算其左、右子樹(shù)的深度，左、右子樹(shù)深度的最大者加1就是該二叉樹(shù)的深度。算法步驟：如果二叉樹(shù)BT為空，返回0，否則執(zhí)行 ；分別計(jì)算BT的左右子樹(shù)的深度；如果左子樹(shù)深度大，返回左子樹(shù)深度+1，否則返回右子樹(shù)深度+1。遞歸算法： int BinTreeDepth(BinTNode *BT)int leftdep,rightdep;/分別記錄左右子樹(shù)深度if (BT=NULL)return

25、(0);elseleftdep=BinTreeDepth(BT-lchild);rightdep=BinTreeDepth(BT-rchild);if (leftdeprightdep)return(leftdep+1);elsereturn(rightdep+1); 2計(jì)算雙孩子結(jié)點(diǎn)個(gè)數(shù)分析： 如果二叉樹(shù)BT為空，即BT=NULL，則BT無(wú)雙孩子； 如果二叉樹(shù)BT不空，但左、右子樹(shù)至少有一個(gè)為空，即BT-lchild=NULL | BT-rchild=NULL，此時(shí)左、右子樹(shù)雙孩子結(jié)點(diǎn)個(gè)數(shù)的和就是該二叉樹(shù)的雙孩子結(jié)點(diǎn)的個(gè)數(shù)； 如果二叉樹(shù)BT不空，且左、右子樹(shù)都不空，此時(shí)左、右子樹(shù)雙孩子結(jié)點(diǎn)個(gè)

26、數(shù)的和再加1就是該二叉樹(shù)的雙孩子結(jié)點(diǎn)的個(gè)數(shù)。算法步驟：如果二叉樹(shù)BT為空，返回0；如果左右子樹(shù)至少有一個(gè)為空，返回左子樹(shù)雙孩子結(jié)點(diǎn)數(shù)與右子樹(shù)雙孩子結(jié)點(diǎn)數(shù)之和；如果左右子樹(shù)都不空，返回左子樹(shù)雙孩子結(jié)點(diǎn)數(shù)與右子樹(shù)雙孩子結(jié)點(diǎn)數(shù)之和+1。遞歸算法： int TwoSonCount(BinTNode *BT)if (BT=NULL)return(0);else if (BT-lchild=NULL | BT-rchild=NULL)return(TwoSonCount (BT-lchild)+ TwoSonCount (BT-rchild);elsereturn(TwoSonCount (BT-lchi

27、ld)+ TwoSonCount (BT-rchild)+1); 3計(jì)算結(jié)點(diǎn)總數(shù)分析： 如果二叉樹(shù)BT為空，即BT=NULL，則BT無(wú)結(jié)點(diǎn)； 如果二叉樹(shù)BT不空，則左、右子樹(shù)結(jié)點(diǎn)的個(gè)數(shù)之和加1就是該二叉樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)。算法步驟：如果二叉樹(shù)BT為空，返回0；如果二叉樹(shù)BT不空，返回左子樹(shù)結(jié)點(diǎn)數(shù)與右子樹(shù)結(jié)點(diǎn)數(shù)之和加1。遞歸算法： int NodeCount(BinTNode *BT)if (BT=NULL)return(0);elsereturn(NodeCount (BT-lchild)+ NodeCount (BT-rchild)+1); 【課堂實(shí)踐4-7】 用遞歸方法分別求二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)

28、和單孩子結(jié)點(diǎn)個(gè)數(shù)。 做一做一、樹(shù)、森林到二叉樹(shù)的轉(zhuǎn)換1將樹(shù)轉(zhuǎn)換為二叉樹(shù)轉(zhuǎn)換方法：加線：在所有兄弟結(jié)點(diǎn)之間加一連線；去線：對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其長(zhǎng)子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線；調(diào)整：按樹(shù)的層次進(jìn)行調(diào)整，將原來(lái)的右兄弟變成其右孩子，原來(lái)的無(wú)兄弟結(jié)點(diǎn)變成左孩子。 4.6 樹(shù)和森林 【示例】將如圖4-17 (a)的樹(shù)T2轉(zhuǎn)換為二叉樹(shù)的全過(guò)程如下： 圖4-17 (a) 樹(shù)T2ABCDEFGHI圖4-17 (b) 第一步 加線ABCDEFGHI圖4-17 (c) 第二步 去線ABCDEFGHI圖4-17 (d) 第三步 調(diào)整ABCDEFGHI2將一個(gè)森林轉(zhuǎn)換為二叉樹(shù)轉(zhuǎn)換方法：樹(shù)轉(zhuǎn)換為二叉樹(shù)：將

29、森林中的每棵樹(shù)轉(zhuǎn)換為二叉樹(shù)；連接根結(jié)點(diǎn)：再將各二叉樹(shù)的根結(jié)點(diǎn)視為兄弟從左至右連在一起；調(diào)整：按樹(shù)的層次進(jìn)行調(diào)整，將原來(lái)的右兄弟變成其右孩子，原來(lái)的無(wú)兄弟結(jié)點(diǎn)變成左孩子。 【示例】將如圖4-18 (a)的森林F1轉(zhuǎn)換為二叉樹(shù)的全過(guò)程如下： 第1步：將森林F1中的各棵樹(shù)轉(zhuǎn)換為二叉樹(shù)，如圖4-18(b)； 圖4-18(b) 第一步 將各樹(shù)轉(zhuǎn)換為二叉樹(shù)ABCDEFIJKGH圖4-18(a) 森林F1ABCDEFIJKGH第2步：連接各二叉樹(shù)的根結(jié)點(diǎn)，如圖4-18(c)； 圖4-18(c) 第二步 連接根結(jié)點(diǎn)ABCDEFIJKGH第3步：按樹(shù)的層次進(jìn)行調(diào)整，調(diào)整為二叉樹(shù)，如圖4-18(d)。 圖4-18

30、(d) 第三步 調(diào)整IJKGHABCDEF3二叉樹(shù)到樹(shù)、森林的轉(zhuǎn)換轉(zhuǎn)換方法： 加線：在左孩子結(jié)點(diǎn)的雙親與左孩子結(jié)點(diǎn)的右孩子、右孩子的右孩子等等之間加一連線；去線：去掉所有雙親與右孩子之間的連線；調(diào)整：按樹(shù)的層次進(jìn)行調(diào)整，將原來(lái)根結(jié)點(diǎn)的右孩子、右孩子的右孩子等等變成森林中樹(shù)的根，其它結(jié)點(diǎn)的右孩子、右孩子的右孩子等等變成兄弟。 【示例】將如圖4-19的二叉樹(shù)BT6轉(zhuǎn)換為樹(shù)或森林的全過(guò)程如圖4-19(a)-(c)： 第1步：加線，如圖4-19(a)； 圖4-19 二叉樹(shù)BT6GJCFABEHDI圖4-19 (a) 第一步 加線GJCFABEHDI第2步：去線，如圖4-19(b)； 第3步：調(diào)整，如圖

31、4-19(c)。 圖4-19(b) 第二步 去線GJCFABEHDI圖4-19(c) 第三步 調(diào)整GABEHDJCFI二、樹(shù)的存儲(chǔ)結(jié)構(gòu)1雙親鏈表表示法 該表示法用向量表示結(jié)點(diǎn)，并用一個(gè)整型量parent指示其雙親的位置，稱為指向其雙親的指針。 雙親鏈表向量表示的描述2孩子鏈表表示法 該表示法為樹(shù)中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。孩子鏈表表示的描述 3孩子兄弟鏈表表示法結(jié)點(diǎn)的結(jié)構(gòu)：與二叉鏈表類(lèi)似，在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域leftmostchild和rightsibling，即可得樹(shù)的孩子兄弟鏈表表示。孩

32、子兄弟鏈表表示的描述 #define MaxTreeSize 100 /定義向量空間的容量typedef char DataType； /定義結(jié)點(diǎn)數(shù)據(jù)域類(lèi)型typedef struct /定義結(jié)點(diǎn)DataType data；/定義結(jié)點(diǎn)數(shù)據(jù)域int parent； /雙親指針，指示雙親的位置PTreeNode；typedef struct/定義鏈表PTreeNode nodesMaxTreeSize;int n； /結(jié)點(diǎn)總數(shù)PTree；PTree T； /T是雙親鏈表 【示例】如圖4-20的樹(shù)T3的雙親鏈表表示為圖4-21。 圖4-21 樹(shù)T3的雙親鏈表dataparentABCDEFGHI下標(biāo)

33、012345678MaxTreeSize-100011133-1圖4-20 樹(shù)T3GCFABEHDI#define MaxTreeSize 100 /定義向量空間的容量typedef char DataType； /定義結(jié)點(diǎn)數(shù)據(jù)域類(lèi)型typedef struct Cnode/孩子鏈表結(jié)點(diǎn)int child； /孩子結(jié)點(diǎn)在向量中對(duì)應(yīng)的序號(hào)struct CNode *next；CNode；typedef structDataType data； /存放樹(shù)中結(jié)點(diǎn)數(shù)據(jù)CNode *firstchild；/孩子鏈表的頭指針PTNode；typedef structPTNode nodesMaxTreeS

34、ize；int n，root； /n為結(jié)點(diǎn)總數(shù)，root指出根在向量中的位置CTree；CTree T； /T為孩子鏈表表示 【示例】如圖4-20的樹(shù)T3的孩子鏈表表示如圖4-22。 圖4-22 樹(shù)T3的孩子鏈表013245678rootdata12345678firstchildnotesIHGFEDCBAtypedef char DataType; /定義結(jié)點(diǎn)數(shù)據(jù)域類(lèi)型typedef struct node/定義結(jié)點(diǎn)結(jié)構(gòu)DataType data;struct node * leftmostchild,* rightsibling; CSTNode; /結(jié)點(diǎn)類(lèi)型CSTNode *T; /指

35、向樹(shù)的開(kāi)始結(jié)點(diǎn)的指針【示例】如圖4-20的樹(shù)T3的孩子兄弟鏈表表示為圖4-23。 圖4-23 樹(shù)T3的孩子兄弟鏈表ABECDFGHIT3三、樹(shù)的遍歷 設(shè)樹(shù)T的根結(jié)點(diǎn)是R，根的子樹(shù)從左到右依次為T(mén)1，T2，Tk。樹(shù)的遍歷分為先序遍歷和后序遍歷兩種。1樹(shù)T的先序遍歷規(guī)則若樹(shù)T非空，則 訪問(wèn)根結(jié)點(diǎn)R；依次先序遍歷根R的各子樹(shù)T1，T2，Tk。 2樹(shù)T的后序遍歷規(guī)則若樹(shù)T非空，則依次后序遍歷根R的各子樹(shù)T1，T2，Tk；訪問(wèn)根結(jié)點(diǎn)R。說(shuō)明：前序遍歷一棵樹(shù)恰好等價(jià)于前序遍歷該樹(shù)對(duì)應(yīng)的二叉樹(shù)；后序遍歷一棵樹(shù)恰好等價(jià)于中序遍歷該樹(shù)對(duì)應(yīng)的二叉樹(shù)。 【示例】圖4-17(a)的樹(shù)T2轉(zhuǎn)換為二叉樹(shù)如圖4-17(d)

36、樹(shù)T2的先序序列為：ABEFGCHDI。轉(zhuǎn)換得到的二叉樹(shù)的先序序列為：ABEFGCHDI。樹(shù)T2的后序序列為：EFGBHCIDA。轉(zhuǎn)換得到的二叉樹(shù)的中序序列為：EFGBHCIDA。轉(zhuǎn)換得到的二叉樹(shù)的后序序列為：GFEHIDCBA。 顯然，前序遍歷一棵樹(shù)恰好等價(jià)于前序遍歷該樹(shù)對(duì)應(yīng)的二叉樹(shù)，后序遍歷一棵樹(shù)恰好等價(jià)于中序遍歷該樹(shù)對(duì)應(yīng)的二叉樹(shù)。 【課堂實(shí)踐4-8】 已知一個(gè)森林的前序遍歷序列為CBADHEGF，后序遍歷序列為ABCDEFGH，畫(huà)出該森林所對(duì)應(yīng)的二叉樹(shù)，并畫(huà)出該森林。 做一做一、哈夫曼樹(shù)（Huffman Tree）的有關(guān)概念1樹(shù)的路徑長(zhǎng)度：從根結(jié)點(diǎn)到樹(shù)中每一結(jié)點(diǎn)的路徑長(zhǎng)度之和稱為樹(shù)的路徑

37、長(zhǎng)度。說(shuō)明：在結(jié)點(diǎn)數(shù)目相同的二叉樹(shù)中，完全二叉樹(shù)的路徑長(zhǎng)度最短。2樹(shù)的帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的權(quán)（Weight）：賦予樹(shù)中某結(jié)點(diǎn)的一個(gè)有某種意義的實(shí)數(shù)，稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：結(jié)點(diǎn)到樹(shù)根之間路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積，稱為結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。樹(shù)的帶權(quán)路徑長(zhǎng)度（Weighted Path Length of Tree）：樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，稱為樹(shù)的帶權(quán)路徑長(zhǎng)度，亦稱為樹(shù)的代價(jià)。記為：4.7 哈夫曼樹(shù)及其應(yīng)用 ，n表示葉子結(jié)點(diǎn)的數(shù)目，wi和li表示葉結(jié)點(diǎn)ki的權(quán)值和根到ki之間的路徑長(zhǎng)度。3哈夫曼樹(shù)：在權(quán)為wl,w2,wn的n個(gè)葉子所構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最小（即代價(jià)

38、最小）的二叉樹(shù)稱為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)。說(shuō)明： 葉子上的權(quán)值均相同時(shí)，完全二叉樹(shù)一定是最優(yōu)二叉樹(shù)，否則完全二叉樹(shù)不一定是最優(yōu)二叉樹(shù)；哈夫曼樹(shù)中，權(quán)越大的葉子離根越近；哈夫曼樹(shù)的形態(tài)不唯一，但WPL值相同且最小。 【示例】給定5個(gè)葉子結(jié)點(diǎn)a，b，c， d和e，分別帶權(quán)7，6，12，15和10。可構(gòu)造出許多棵二叉樹(shù)，如圖4-24所示的是其中兩棵二叉樹(shù)。它們的帶權(quán)路徑長(zhǎng)度分別為：(a)WPL=7*2+6*3+12*3+15*3+10*3=143(b) WPL=7*3+6*3+12*2+15*2+10*2=113 實(shí)際上圖(b)的二叉樹(shù)是所有以a，b，c，d和e為葉子的二叉樹(shù)中WPL最小的二叉樹(shù)，它就

39、是哈夫曼樹(shù)。acbed圖4-24 兩棵二叉樹(shù)(a)(b)cdbae二、哈夫曼樹(shù)的構(gòu)造1哈夫曼算法基本思想：根據(jù)給定的n個(gè)權(quán)值wl,w2,wn構(gòu)成n棵二叉樹(shù)的森林F=T1,T2,Tn，其中每棵二叉樹(shù)Ti中都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左右子樹(shù)均空；在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)（當(dāng)這樣的樹(shù)不止兩棵樹(shù)時(shí)，可以從中任選兩棵），將這兩棵樹(shù)合并成一棵新樹(shù)，為了保證新樹(shù)仍是二叉樹(shù)，需要增加一個(gè)新結(jié)點(diǎn)作為新樹(shù)的根，并將所選的兩棵樹(shù)的根分別作為新根的左右孩子（誰(shuí)左，誰(shuí)右無(wú)關(guān)緊要），將這兩個(gè)孩子的權(quán)值之和作為新樹(shù)根的權(quán)值；對(duì)新的森林F重復(fù)，直到森林F中只剩下一棵樹(shù)為止。這棵樹(shù)便是哈夫曼樹(shù)。 用哈夫曼算法

40、構(gòu)造哈夫曼樹(shù)的過(guò)程：給定5個(gè)葉子結(jié)點(diǎn)a，b，c， d和e，分別帶權(quán)7，6，12，15和10。用哈夫曼算法構(gòu)造哈夫曼樹(shù)的過(guò)程如下：第1步：根據(jù)給定的5個(gè)權(quán)值7，6，12，15和10構(gòu)成5棵二叉樹(shù)的森林F=T1,T2,T3,T4,T5，如圖4-25(a)； 第2步：在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)，將這兩棵樹(shù)合并成一棵新樹(shù)，并添加到森林中，得到新的森林，如圖4-25(b)； 圖4-25 (a) 76121510abcde圖4-25 (b) 121510cde1376ab第3步：重復(fù)第2步，進(jìn)行第二次合并，得到新的森林，如圖4-25(c)； 第4步：重復(fù)第2步，進(jìn)行第三次合并，得到新的森林，如圖

41、4-25(d)； 圖4-25 (c) 15d1376ab221210ce圖4-25 (d) 221210ce15d1376ab28第5步：重復(fù)第2步，進(jìn)行第四次合并，由于森林F中只剩下一棵樹(shù)，所以它就是哈夫曼樹(shù)，如圖4-25(e)。 圖4-25 (e) 221210ce15d1376ab2850三、哈夫曼樹(shù)算法的實(shí)現(xiàn) 1哈夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu) 哈夫曼樹(shù)的結(jié)點(diǎn)用一個(gè)大小為2n-1的向量來(lái)存儲(chǔ)，每個(gè)結(jié)點(diǎn)包含權(quán)值域weight 、指示左右孩子結(jié)點(diǎn)在向量中下標(biāo)的整型量lchild和rchild、指示雙親結(jié)點(diǎn)在向量中下標(biāo)的整型量parent 。結(jié)點(diǎn)結(jié)構(gòu)如圖4-26。 2哈夫曼樹(shù)的描述注意：因?yàn)镃數(shù)組的下界為

42、0，故用-1表示空指針。樹(shù)中某結(jié)點(diǎn)的lchild、rchild和parent不等于-1時(shí)，它們分別是該結(jié)點(diǎn)的左、右孩子和雙親結(jié)點(diǎn)在向量中的下標(biāo)。這里設(shè)置parent域有兩個(gè)作用：其一是使查找某結(jié)點(diǎn)的雙親變得簡(jiǎn)單；其二是可通過(guò)判定parent的值是否為-1來(lái)區(qū)分根與非根結(jié)點(diǎn)。 weight lchild rchild parent圖4-26 結(jié)點(diǎn)結(jié)構(gòu)#define n 100 /葉子數(shù)目#define m 2*n-1/樹(shù)中結(jié)點(diǎn)總數(shù)typedef struct /定義結(jié)點(diǎn)類(lèi)型float weight; /定義權(quán)值域int lchild,rchild,parent; /定義左右孩子及雙親指針HTNo

43、de;typedef HTNode HuffmanTreem; /*定義HuffmanTree為新的類(lèi)型標(biāo)識(shí)符，用該標(biāo)識(shí)符定義的變量是具有HTNode類(lèi)型的含有m個(gè)元素的向量。*/ 3哈夫曼樹(shù)T算法實(shí)現(xiàn)的步驟（1）初始化：將T0m-1中2n-1個(gè)結(jié)點(diǎn)里的三個(gè)指針均置為空(即置為-1)，權(quán)值置為0。（2）輸入：讀入n個(gè)葉子的權(quán)值存于向量的前n個(gè)分量(即T0 n-1)中。它們是初始森林中n個(gè)孤立的根結(jié)點(diǎn)上的權(quán)值。（3）合并：對(duì)森林中的樹(shù)共進(jìn)行n-1次合并，所產(chǎn)生的新結(jié)點(diǎn)依次放入向量T的第i個(gè)分量中(nim-1)。每次合并分兩步：在當(dāng)前森林T0 i-1的所有結(jié)點(diǎn)中，選取權(quán)最小和次小的兩個(gè)根結(jié)點(diǎn)Tp1

44、和Tp2作為合并對(duì)象，這里0p1，p2i-1。將根為T(mén)p1和Tp2的兩棵樹(shù)作為左右子樹(shù)合并為一棵新的樹(shù)，新樹(shù)的根是新結(jié)點(diǎn)Ti。具體操作：（i）將Tp1和Tp2的parent置為i;（ii）將Ti的lchild和rchild分別置為p1和p2;（iii）新結(jié)點(diǎn)Ti的權(quán)值置為T(mén)p1和Tp2的權(quán)值之和。4哈夫曼樹(shù)T算法實(shí)現(xiàn)初始化函數(shù)void InitHuffmanTree(HuffmanTree T) /初始化int i;for (i=0; im; i+)Ti.weight=0;Ti.lchild=-1;Ti.rchild=-1;Ti.parent=-1;輸入權(quán)值函數(shù)void InputWeight

45、(HuffmanTree T)/輸入權(quán)值float w;int i;for (i=0; in;i+)printf(n輸入第%d個(gè)權(quán)值:,i+1);scanf(%f,&w);Ti.weight=w; 選擇兩個(gè)權(quán)最小的根結(jié)點(diǎn)函數(shù)void SelectMin(HuffmanTree T, int i, int *p1,int *p2)/選擇兩個(gè)小的結(jié)點(diǎn)float min1=999999;/定義并初始化最小權(quán)值float min2=999999;/定義并初始化次小權(quán)值int j;for (j=0;j=i;j+)if(Tj.parent=-1)if(Tj.weightmin1)min2=min1; mi

46、n1=Tj.weight; *p2=*p1;*p1=j;else if(Tj.weightmin2)min2=Tj.weight*p2=j; 建立哈夫曼樹(shù)函數(shù)void CreateHuffmanTree(HuffmanTree T)/構(gòu)造哈夫曼樹(shù)，Tm-1為其根結(jié)點(diǎn)int i,p1,p2;InitHuffmanTree(T); /將T初始化InputWeight(T); /輸入葉子權(quán)值至weight域for(i=n;im;i+)/共n-1次合并,新結(jié)點(diǎn)存于Ti中SelectMin(T,i-1,&p1,&p2); Tp1.parent=Tp2.parent=i;Ti.lchild=p1; Ti.

47、rchild=p2; Ti.weight=Tp1.weight+Tp2.weight;四、哈夫曼編碼1編碼和解碼 數(shù)據(jù)壓縮過(guò)程稱為編碼。即將文件中的每個(gè)字符均轉(zhuǎn)換為一個(gè)惟一的二進(jìn)制位串。 數(shù)據(jù)解壓過(guò)程稱為解碼。即將二進(jìn)制位串轉(zhuǎn)換為對(duì)應(yīng)的字符。2等長(zhǎng)、變長(zhǎng)編碼方案 給定的字符集C，可能存在多種編碼方案。等長(zhǎng)編碼方案 等長(zhǎng)編碼方案將給定字符集C中每個(gè)字符的碼長(zhǎng)定為lg|C|，|C|表示字符集的大小。變長(zhǎng)編碼方案 變長(zhǎng)編碼方案將頻度高的字符編碼設(shè)置較短，將頻度低的字符編碼設(shè)置較長(zhǎng)。注意：變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。原因是某些字符的編碼可能與其他字符的編碼開(kāi)始部分(稱為前綴)相同。 【示例】設(shè)待壓縮

48、的數(shù)據(jù)文件共有100000個(gè)字符，這些字符均取自字符集C=a，b，c，d，e，f，等長(zhǎng)編碼需要三位二進(jìn)制數(shù)字來(lái)表示六個(gè)字符，因此，整個(gè)文件的編碼長(zhǎng)度為300000位。【示例】設(shè)待壓縮的數(shù)據(jù)文件共有100000個(gè)字符，這些字符均取自字符集C=a，b，c，d，e，f，其中每個(gè)字符在文件中出現(xiàn)的次數(shù)（簡(jiǎn)稱頻度）見(jiàn)表4-1。 根據(jù)計(jì)算公式：(45*1+13*3+12*3+16*3+9*4+5*4)*1000=224000整個(gè)文件被編碼為224000位，比定長(zhǎng)編碼方式節(jié)約了約25的存儲(chǔ)空間。字符abcdef頻度（千次）4513121695定長(zhǎng)編碼000001010011100101變長(zhǎng)編碼0100101

49、11011101111【示例】設(shè)E、T、W分別編碼為00、01、0001，則解碼時(shí)無(wú)法確定信息串0001是ET還是W。 3前綴碼方案 對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼稱為前綴（編）碼。注意：等長(zhǎng)編碼是前綴碼。4最優(yōu)前綴碼 平均碼長(zhǎng)或文件總長(zhǎng)最小的前綴編碼稱為最優(yōu)的前綴碼。最優(yōu)的前綴碼對(duì)文件的壓縮效果亦最佳。 其中：pi為第i個(gè)字符的概率，li為碼長(zhǎng)?！臼纠咳魧⑶氨硭镜奈募鳛榻y(tǒng)計(jì)的樣本，則a至f六個(gè)字符的概率分別為0.45，0.13，0.12，0.16，0.09，0.05，對(duì)變長(zhǎng)編碼求得的平均碼長(zhǎng)為2.24，優(yōu)于定長(zhǎng)編碼（平均碼長(zhǎng)為3）。

50、5根據(jù)最優(yōu)二叉樹(shù)構(gòu)造哈夫曼編碼 利用哈夫曼樹(shù)很容易求出給定字符集及其概率(或頻度)分布的最優(yōu)前綴碼。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉20至90，其壓縮效率取決于被壓縮文件的特征。（1）編碼構(gòu)造方法用字符ci作為葉子，概率pi或頻度f(wàn)i作為葉子ci的權(quán)，構(gòu)造一棵哈夫曼樹(shù)，并將樹(shù)中左分支和右分支分別標(biāo)記為0和1；將從根到葉子的路徑上的標(biāo)號(hào)依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱哈夫曼編碼）。 【示例】設(shè)字符集C=a，b，c，d，e，f，其中每個(gè)字符在文件中出現(xiàn)的頻度分別為：45，13，12，16，9，5（千次）。求一個(gè)哈夫曼編

51、碼。 先構(gòu)造哈夫曼樹(shù)并將樹(shù)中左分支和右分支分別標(biāo)記為0和1，如圖4-27； 再將從根到葉子的路徑上的標(biāo)號(hào)依次相連，得到如下哈夫曼編碼。a：0b：100c：101d：110e：1110f：1111 圖4-2716251312bc1495efd3055451000000011111（2）哈夫曼編碼為最優(yōu)前綴碼 由哈夫曼樹(shù)求得編碼為最優(yōu)前綴碼的原因：每個(gè)葉子字符ci的碼長(zhǎng)恰為從根到該葉子的路徑長(zhǎng)度li，平均碼長(zhǎng)(或文件總長(zhǎng))又是二叉樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。而哈夫曼樹(shù)是WPL最小的二叉樹(shù)，因此編碼的平均碼長(zhǎng)(或文件總長(zhǎng))亦最小。樹(shù)中沒(méi)有一片葉子是另一葉子的祖先，每片葉子對(duì)應(yīng)的編碼就不可能是其它葉子編碼

52、的前綴。即上述編碼是二進(jìn)制的前綴碼。 （3）求哈夫曼編碼的算法思想方法：給定字符集的哈夫曼樹(shù)生成后，求哈夫曼編碼的具體實(shí)現(xiàn)過(guò)程是：依次以葉子Ti(0in-1)為出發(fā)點(diǎn)，向上回溯至根為止。上溯時(shí)走左分支則生成代碼0，走右分支則生成代碼1。注意：（i）由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個(gè)臨時(shí)向量中，并設(shè)一個(gè)指針start指示編碼在該向量中的起始位置（start初始時(shí)指示向量的結(jié)束位置）。（ii）當(dāng)某字符編碼完成時(shí)，從臨時(shí)向量的start處將編碼復(fù)制到該字符相應(yīng)的位串bits中即可。（ii）因?yàn)樽址笮閚，故變長(zhǎng)編碼的長(zhǎng)度不會(huì)超過(guò)n，加上一個(gè)結(jié)束符0，bits的大

53、小應(yīng)為n+1。字符集編碼的存儲(chǔ)結(jié)構(gòu)及其算法描述 typedef struct char ch;/存儲(chǔ)字符char bitsn+1;/存放編碼位串CodeNode;typedef CodeNode HuffmanCoden; 算法實(shí)現(xiàn) void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H)/根據(jù)哈夫曼樹(shù)T求哈夫曼編碼表Hint c,p,i;/c和p分別指示T中孩子和雙親的位置char cdn+1; /臨時(shí)存放編碼int start;/指示編碼在cd中的起始位置cdn=0;/編碼結(jié)束符for(i=0;i=0)cd-start=(Tp.lch

54、ild=c)?0：1;c=p; /繼續(xù)上溯strcpy(Hi.bits,&cdstart); /復(fù)制編碼位串 6文件的編碼和解碼 有了字符集的哈夫曼編碼表之后，對(duì)數(shù)據(jù)文件的編碼過(guò)程是：依次讀入文件中的字符c，在哈夫曼編碼表H中找到此字符，若Hi.ch=c，則將字符c轉(zhuǎn)換為Hi.bits中存放的編碼串。 對(duì)壓縮后的數(shù)據(jù)文件進(jìn)行解碼則必須借助于哈夫曼樹(shù)T，其過(guò)程是：依次讀入文件的二進(jìn)制碼，從哈夫曼樹(shù)的根結(jié)點(diǎn)(即Tm-1)出發(fā)，若當(dāng)前讀入0，則走向左孩子，否則走向右孩子。一旦到達(dá)某一葉子Ti時(shí)便譯出相應(yīng)的字符Hi.ch。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。 【課堂實(shí)踐4-9】 假設(shè)通信電文使用的

55、字符集為a，b，c，d，e，f，g，h，各字符在電文中出現(xiàn)的頻度分別為：7，26，2，28，13，10，3，11，請(qǐng)為這8個(gè)字符設(shè)計(jì)哈夫曼編碼。要求：你所構(gòu)造的哈夫曼樹(shù)中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(quán)值且按左分支為0和右分支為1的規(guī)則，分別寫(xiě)出與每個(gè)字符對(duì)應(yīng)的編碼。 做一做引例分析與實(shí)現(xiàn) 1引例分析 此問(wèn)題可通過(guò)設(shè)計(jì)一個(gè)哈夫曼編碼、譯碼系統(tǒng)來(lái)解決。對(duì)文本文件中的字符用二進(jìn)制位串進(jìn)行哈夫曼編碼，形成加密文件；反過(guò)來(lái)，可將加密文件進(jìn)行譯碼還原成文本文件。 首先從文本文件中讀入各字符，統(tǒng)計(jì)不同字符在文件中出現(xiàn)的次數(shù)（空格、換行、標(biāo)點(diǎn)等也按字符處理），作為該字符的權(quán)值； 然后根據(jù)字符及其權(quán)值構(gòu)造

56、哈夫曼樹(shù)，并給出每個(gè)字符的哈夫曼編碼； 再將文本文件利用哈夫曼樹(shù)進(jìn)行編碼，存儲(chǔ)成由二進(jìn)制位串組成的加密文件； 最后對(duì)加密文件進(jìn)行解密，將加密文件還原成原來(lái)的文本文件。 （1）數(shù)據(jù)結(jié)構(gòu)描述#define n 2*26+4/*文件含字符的最大個(gè)數(shù)（大小寫(xiě)字母+2個(gè)標(biāo)點(diǎn)符號(hào)+空格+回車(chē)換行）*/#define m 2*n-1/哈夫曼樹(shù)中結(jié)點(diǎn)總數(shù)最大值#define Max 10000/文件含字符的最大個(gè)數(shù)/*n1表示文件實(shí)際含字符個(gè)數(shù)，m1表示哈夫曼樹(shù)中實(shí)際結(jié)點(diǎn)總數(shù)，數(shù)組size用于存放各字符出現(xiàn)的次數(shù)（權(quán)值）*/int n1,m1,sizen;char CharSetn;/用于存放文件中所使用的不

57、同字符char StrMax+1,BMMax*n+1;/*數(shù)組Str用于存放原文件字符串，BM用于存放加密后的二進(jìn)制串*/char Str1Max+1;/數(shù)組Str1用于存放解密字符串引例分析與實(shí)現(xiàn) typedef struct /定義結(jié)點(diǎn)類(lèi)型int weight;/定義權(quán)值域int lchild,rchild,parent;/定義左右孩子及雙親指針HTNode;/*定義HuffmanTree為新的類(lèi)型標(biāo)識(shí)符，用該標(biāo)識(shí)符定義的變量是具有HTNode類(lèi)型的含有m個(gè)元素的向量。*/typedef HTNode HuffmanTreem;typedef struct char ch;/存儲(chǔ)字符cha

58、r bitsn+1;/存放編碼位串CodeNode;typedef CodeNode HuffmanCoden;引例分析與實(shí)現(xiàn) （2）功能函數(shù)哈夫曼樹(shù)T初始化函數(shù)：void InitHuffmanTree(HuffmanTree T)寫(xiě)入權(quán)值函數(shù)函數(shù)：void WriteWeight(HuffmanTree T)選擇兩個(gè)權(quán)最小的根結(jié)點(diǎn)函數(shù)：void SelectMin(HuffmanTree T, int i, int *p1,int *p2)構(gòu)造哈夫曼樹(shù)函數(shù)：void CreateHuffmanTree(HuffmanTree T)根據(jù)哈夫曼樹(shù)T求哈夫曼編碼表H：void CharSetHu

59、ffmanEncoding(HuffmanTree T,HuffmanCode H)讀文本文件統(tǒng)計(jì)實(shí)際不同字符及個(gè)數(shù)n1函數(shù)：void ReadFile()引例分析與實(shí)現(xiàn) void InitHuffmanTree(HuffmanTree T) /哈夫曼樹(shù)T初始化int i;for (i=0; im1; i+)Ti.weight=0;Ti.lchild=-1;Ti.rchild=-1;Ti.parent=-1; void WriteWeight(HuffmanTree T)/寫(xiě)入權(quán)值函數(shù)int i,j,k=0;for (i=0; in1;i+)for(j=k;jn;j+)if(sizej)Ti.weight=sizej;k=j+1;break; void SelectMin(HuffmanTree T, int i, int *p1,int *p2)/選擇兩個(gè)權(quán)最小的根結(jié)點(diǎn)函數(shù)int min1=99