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

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)教學(xué)目標(biāo)

【知識目標(biāo)】理解樹的邏輯結(jié)構(gòu)和基本術(shù)語理解二叉樹的遞歸定義，掌握二叉樹的性質(zhì)掌握二叉樹的遍歷，能確定遍歷所得到的結(jié)點訪問序列掌握二叉樹的存儲方法和二叉樹的基本操作的算法掌握樹和森林與二叉樹之間的轉(zhuǎn)換方法能根據(jù)給定的葉結(jié)點及其權(quán)值構(gòu)造出相應(yīng)的最優(yōu)二叉樹能根據(jù)最優(yōu)二叉樹構(gòu)造對應(yīng)的哈夫曼編碼【能力目標(biāo)】具有用樹來描述現(xiàn)實世界、應(yīng)用二叉樹解決實際問題的能力具有恰當(dāng)?shù)倪x擇二叉樹作為數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的能力教學(xué)目標(biāo)【知識目標(biāo)】引例描述——文本文件的加密和解密

某公司有一份機密文件，是由英文字母（包括大小寫）、英文逗號、英文句點、空格和回車換行等符號組成的文件名為Jimi.txt的文本文件。公司為保證文件不被泄密，要求技術(shù)人員將文件中的每個字符都用一個二進制位串進行加密，需要時能進行解密，但必須保證加密后的文件不要過大，且對加密的文件進行解密后與原文件必須完全一致。如果你是技術(shù)人員，你將如何按要求為公司的文件進行加密和解密呢？演示執(zhí)行

引例描述——文本文件的加密和解密某公司有一份機密文件，一、樹的遞歸定義1.定義樹（Tree）是n(n≥0)個結(jié)點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件：①有且僅有一個特定的稱為根（Root）的結(jié)點；②其余的結(jié)點可分為m(m≥0)個互不相交的有限子集Tl，T2，…，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹（SubTree）。4.1樹的概念知識儲備一、樹的遞歸定義4.1樹的概念知識儲備2．樹的表示①樹形圖表示：結(jié)點用圓圈表示，結(jié)點名字寫在圓圈旁或圓圈內(nèi)，子樹與其根之間用無向邊來連接，如圖4-1是樹形圖表示表示的樹T1。②嵌套集合表示法：用集合的包含關(guān)系描述樹結(jié)構(gòu)，如圖4-2是樹T1的嵌套集合表示。③凹入表表示法：類似于書的目錄。圖4-1樹T1的樹形圖表示ABCDEFIJGH圖4-2樹T1的嵌套集合表示EIJGHABDCF2．樹的表示圖4-1樹T1的樹形圖表示ABCDEFIJ二、樹結(jié)構(gòu)的基本術(shù)語1．結(jié)點的度①結(jié)點的度：一個結(jié)點擁有子樹的個數(shù)稱為該結(jié)點的度。②樹的度：該樹中結(jié)點的最大度數(shù)稱為該樹的度。③葉子結(jié)點：度為零的結(jié)點稱為葉子結(jié)點或終端結(jié)點。④分支結(jié)點：度不為零的結(jié)點稱分支結(jié)點或非終端結(jié)點。即除葉子結(jié)點外的結(jié)點均為分支結(jié)點。⑤內(nèi)部結(jié)點：除根結(jié)點之外的分支結(jié)點統(tǒng)稱為內(nèi)部結(jié)點。⑥開始結(jié)點：根結(jié)點又稱為開始結(jié)點?！臼纠繄D4-1表示的樹T1中結(jié)點A的度為3，其它結(jié)點的度都為2或0。【示例】圖4-1表示的樹T1的度為3?！臼纠繄D4-1表示的樹T1中結(jié)點C、E、G、H、I、J都是葉子結(jié)點?！臼纠繄D4-1表示的樹T1中結(jié)點A、B、D、F都是分支結(jié)點?！臼纠繄D4-1表示的樹T1中結(jié)點A是開始結(jié)點。二、樹結(jié)構(gòu)的基本術(shù)語【示例】圖4-1表示的樹T1中結(jié)點A的2．結(jié)點之間的關(guān)系①孩子（Child）結(jié)點：樹中某個結(jié)點的子樹的根稱為該結(jié)點的孩子結(jié)點。②雙親（Parent）結(jié)點：孩子結(jié)點的根稱為該結(jié)點的雙親。③兄弟結(jié)點：同一個雙親的孩子互稱為兄弟結(jié)點。④堂兄弟：在后面介紹。⑤祖先和子孫：在后面介紹?！臼纠繄D4-1表示的樹T1中結(jié)點B、C、D都是結(jié)點A的孩子結(jié)點，結(jié)點E、F都是結(jié)點B的孩子結(jié)點，結(jié)點G、H都是結(jié)點D的孩子結(jié)點?！臼纠繄D4-1表示的樹T1中結(jié)點A是結(jié)點B、C、D的雙親結(jié)點，結(jié)點B是結(jié)點E、F的雙親結(jié)點，結(jié)點D是結(jié)點G、H的雙親結(jié)點。【示例】圖4-1表示的樹T1中結(jié)點B、C、D互為兄弟結(jié)點，結(jié)點E、F互為兄弟結(jié)點，而結(jié)點F和G非兄弟結(jié)點。2．結(jié)點之間的關(guān)系【示例】圖4-1表示的樹T1中結(jié)點B、C、3．路徑①路徑或道路：若樹中存在一個結(jié)點序列k1,k2,…,kj,使得ki是ki+1的雙親(1≤i<j)，則稱該結(jié)點序列是從kl到kj的一條路徑或道路。②路徑的長度：指路徑所經(jīng)過的邊的數(shù)目。注意：若一個結(jié)點序列是路徑，則在樹的樹形圖表示中，該結(jié)點序列“自上而下”地通過路徑上的每條邊。從樹的根結(jié)點到樹中其余結(jié)點均存在一條惟一的路徑。③祖先和子孫：若樹中結(jié)點k到ks存在一條路徑，則稱k是ks的祖先，ks是k的子孫。一個結(jié)點的祖先是從根結(jié)點到該結(jié)點路徑上所經(jīng)過的所有結(jié)點，而一個結(jié)點的子孫則是以該結(jié)點為根的子樹中的所有結(jié)點。約定：結(jié)點k的祖先和子孫不包含結(jié)點k本身。【示例】圖4-1表示的樹T1中結(jié)點序列ABFI是結(jié)點A到I的一條路徑，因為自上而下A是B的雙親，B是F的雙親，F(xiàn)是I的雙親。該路徑的長度為3。而結(jié)點B和G之間不存在路徑，因為既不能從B出發(fā)自上而下地經(jīng)過若干個結(jié)點到達G，也不能從G出發(fā)自上而下地經(jīng)過若干個結(jié)點到達B。3．路徑【示例】圖4-1表示的樹T1中結(jié)點序列ABFI是結(jié)點4．結(jié)點的層數(shù)和樹的深度①結(jié)點的層數(shù)：根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于其雙親結(jié)點的層數(shù)加1。②堂兄弟：雙親在同一層的結(jié)點互為堂兄弟。③樹的深度：樹中結(jié)點的最大層數(shù)稱為樹的深度。注意：要弄清結(jié)點的度、樹的度和樹的深度的區(qū)別。5．有序樹和無序樹若將樹中每個結(jié)點的各子樹看成是從左到右有次序的，則稱該樹為有序樹；否則稱為無序樹。若不特別指明，一般討論的樹都是有序樹。6．森林（Forest）森林是m(m≥0)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個森林；反之，加上一個結(jié)點作樹根，森林就變?yōu)橐豢脴洹?．結(jié)點的層數(shù)和樹的深度三、樹型結(jié)構(gòu)的邏輯特征1．樹中任一結(jié)點都可以有零個或多個直接后繼結(jié)點，但至多只能有一個直接前驅(qū)結(jié)點。2．樹中只有根結(jié)點無前驅(qū)，它是開始結(jié)點；葉結(jié)點無后繼，它們是終端結(jié)點。3．祖先與子孫的關(guān)系是對父子關(guān)系的延拓，它定義了樹中結(jié)點之間的縱向次序。4．有序樹中，同一組兄弟結(jié)點從左到右有長幼之分。對這一關(guān)系加以延拓，規(guī)定若k1和k2是兄弟，且k1在k2的左邊，則kl的任一子孫都在k2的任一子孫的左邊，那么就定義了樹中結(jié)點之間的橫向次序。樹中結(jié)點之間的邏輯關(guān)系是“一對多”的關(guān)系，樹是一種非線性的結(jié)構(gòu)。三、樹型結(jié)構(gòu)的邏輯特征【課堂實踐4-1】

已知在一棵度為3的樹中，度為2的結(jié)點數(shù)為4，度為3的結(jié)點數(shù)為3，求該樹中的葉子結(jié)點數(shù)。提示：分別從樹的結(jié)點總數(shù)和樹的孩子結(jié)點總數(shù)兩個角度考慮。做一做【課堂實踐4-1】做一、二叉樹的定義1.二叉樹的遞歸定義二叉樹（BinaryTree）是n(n≥0)個結(jié)點的有限集，它或者是空集(n=0)，或者由一個根結(jié)點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。2．二叉樹的五種基本形態(tài)二叉樹可以是空集；可以有空的左子樹或空的右子樹；或者左、右子樹皆為空。二叉樹的五種基本形態(tài)如圖4-3。4.2二叉樹及其性質(zhì)圖4-3二叉樹的五種基本形態(tài)(a)(b)(c)(d)(e)一、二叉樹的定義4.2二叉樹及其性質(zhì)圖4-3二叉樹二、二叉樹的性質(zhì)1．性質(zhì)性質(zhì)1：二叉樹第i層上的結(jié)點數(shù)目最多為2i-1(i≥1)個。性質(zhì)2：深度為k的二叉樹至多有2k-1(k≥1)個結(jié)點。性質(zhì)3：在任意一棵非空二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。性質(zhì)3說明：在任意非空二叉樹中葉子結(jié)點數(shù)總比度為2的結(jié)點數(shù)多1個。證明：

假設(shè)樹非空，用數(shù)學(xué)歸納法證明。

當(dāng)i=1時，因為第1層上只有一個根結(jié)點，而2i-1=20=1。所以命題成立。

假設(shè)對所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個結(jié)點，證明j=i時命題亦成立。

根據(jù)歸納假設(shè)，第i-1層上至多有2i-2個結(jié)點。由于二叉樹的每個結(jié)點至多有兩個孩子，故第i層上的結(jié)點數(shù)至多是第i-1層上的最大結(jié)點數(shù)的2倍。即j=i時，該層上至多有2?2i-2=2i-1個結(jié)點，故命題成立。證明：

由性質(zhì)1，第i層至多有2i-1個(1≤i≤k)結(jié)點，所以深度為k的二叉樹的結(jié)點總數(shù)至多為20+21+…+2k-1=2k-1個。證明：

因為二叉樹中所有結(jié)點的度數(shù)均不大于2，所以結(jié)點總數(shù)（記為n）應(yīng)等于0度結(jié)點數(shù)n0、1度結(jié)點數(shù)n1和2度結(jié)點數(shù)n2之和： n=n0+n1+n2

另一方面，1度結(jié)點有一個孩子，2度結(jié)點有兩個孩子，故二叉樹中孩子結(jié)點總數(shù)是：nl+2?n2，而樹中只有根結(jié)點不是任何結(jié)點的孩子，故二叉樹中的結(jié)點總數(shù)又可表示為： n=n1+2?n2+1綜合以上兩個式子得到： n0=n2+1【示例】如圖4-4所示的二叉樹BT1中葉子結(jié)點數(shù)為6，度為2的結(jié)點數(shù)為5，葉子結(jié)點數(shù)正好比度為2的結(jié)點數(shù)多1個。圖4-4二叉樹BT1二、二叉樹的性質(zhì)證明：證明：證明：【示例】如圖4-4所示的二2．特殊二叉樹（1）滿二叉樹

一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。

滿二叉樹的特點：①每一層上的結(jié)點數(shù)都達到最大值。即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹。②滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層。【示例】如圖4-5所示的二叉樹BT2中是一棵深度為4的滿二叉樹，每一層上的結(jié)點數(shù)都達到最大值2i-1(i≥1)。不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層。圖4-5深度為4的滿二叉樹BT22．特殊二叉樹【示例】如圖4-5所示的二叉樹BT2中圖4-5（2）完全二叉樹

若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可以小于2，并且最下一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。

完全二叉樹特點：①在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹是一棵完全二叉樹。②滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。③在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒有右孩子，即該結(jié)點必是葉結(jié)點。④深度為k的完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結(jié)點?！臼纠咳鐖D4-5和如圖4-6所示的兩顆二叉樹BT2和BT3中（i）BT2是滿二叉樹，也是完全二叉樹；BT3是完全二叉樹，但不是滿二叉樹。（ii）在BT2的最下一層上，從最右邊開始連續(xù)刪去3個結(jié)點后得到完全二叉樹BT3。（iii）在完全二叉樹BT3中，結(jié)點G沒有左孩子，也一定沒有右孩子，即該結(jié)點是葉結(jié)點。（iv）BT3是深度為4的完全二叉樹，它的前3層是深度為3的滿二叉樹，一共有23-1=7個結(jié)點。G圖4-6完全二叉樹BT3（2）完全二叉樹【示例】如圖4-5和如圖4-6所示的兩顆二叉【課堂實踐4-2】

已知一棵含50個結(jié)點的二叉樹中有16個葉子結(jié)點，求該二叉樹中度為1的結(jié)點個數(shù)。做一做

，其中

表示取小于等于lgn的整數(shù)部分，

表示取大于等于lg(n+1)的整數(shù)部分，lg表示以2為底的對數(shù)。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為

證明：設(shè)所求完全二叉樹的深度為k。由完全二叉樹特點知：深度為k的完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結(jié)點。由于完全二叉樹深度為k，故第k層上還有若干個結(jié)點，因此該完全二叉樹的結(jié)點個數(shù)n>2k-1-1。另一方面，由性質(zhì)2知：深度為k的二叉樹至多有2k-1(k≥1)個結(jié)點，因此，n≤2k-1，即：2k-1-l<n≤2k-1，由此可推出：2k-1≤n<2k，取對數(shù)后有：k-1≤lgn<k又因k-1和k是相鄰的兩個整數(shù)，故有

另外，由2k-1-l<n≤2k-1得2k-1<n+1≤2k，兩邊再取對數(shù)便可得到：

?！菊n堂實踐4-2】做一、二叉樹的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：把二叉樹所有結(jié)點按照一定的線性次序存儲到一片連續(xù)存儲單元中。結(jié)點在這個序列中的相互位置還能反映出結(jié)點之間的邏輯關(guān)系。1．完全二叉樹的存儲結(jié)構(gòu)（1）完全二叉樹結(jié)點的編號①編號方法：在一棵n個結(jié)點的完全二叉樹中，從樹根起，自上層到下層，每層從左至右給所有結(jié)點編號，開始結(jié)點的編號為1，這樣能得到一個反映整個二叉樹結(jié)構(gòu)的線性序列。4.3二叉樹的存儲結(jié)構(gòu)【示例】如圖4-7所示的結(jié)點編號的完全二叉樹BT3中，編號為5的結(jié)點E的左、右孩子結(jié)點是編號為10（2×5）和11（2×5+1）的結(jié)點J和K，編號為5的結(jié)點E的雙親結(jié)點是編號為2（[5/2]）的結(jié)點B；該完全二叉樹共有17個結(jié)點，其中非葉子結(jié)點數(shù)為8（[17/2]），葉子結(jié)點數(shù)為9（17-8）。圖4-7編號的完全二叉樹BT3CA1B23D4E5F6G7H8I9J10K11L12一、二叉樹的順序存儲結(jié)構(gòu)4.3二叉樹的存儲結(jié)構(gòu)【示例】如圖②編號特點：完全二叉樹中除最下面一層外，各層都充滿了結(jié)點。每一層的結(jié)點個數(shù)恰好是上一層結(jié)點個數(shù)的2倍。從一個結(jié)點的編號就可推得其雙親，左、右孩子，兄弟等結(jié)點的編號。假設(shè)編號為i的結(jié)點是ki(1≤i≤n)，則有：（i）若i>1，則ki的雙親編號為[i/2]；若i=1，則ki是根結(jié)點，無雙親。（ii）若2i≤n，則ki的左孩子的編號是2i；若2i>n，則ki無左孩子，因此也無右孩子，即ki必定是葉子。因此完全二叉樹中編號i>[n/2]的結(jié)點必定是葉結(jié)點。（iii）若i為奇數(shù)且不為1，則ki是結(jié)點k[i/2]的右孩子，ki的左兄弟的編號是i-1；若i=1或i為偶數(shù)，則ki無左兄弟。（iv）若i為偶數(shù)且小于n，則ki是結(jié)點k[i/2]的左孩子，ki的右兄弟的編號是i+1；若i=n或i為奇數(shù)，則ki無右兄弟。

由此可知，完全二叉樹中結(jié)點的編號序列，完全反映了結(jié)點之間的邏輯關(guān)系。②編號特點：完全二叉樹中除最下面一層外，各層都充滿了結(jié)點。每【課堂實踐4-3】

已知一棵完全二叉樹含1000個結(jié)點，分別求該二叉樹的度為2的結(jié)點數(shù)、度為1的結(jié)點數(shù)和葉子結(jié)點數(shù)。

做一做【課堂實踐4-3】做（2）完全二叉樹的順序存儲

將完全二叉樹中所有結(jié)點按編號順序依次存儲在一個向量bt[0…n]中。其中：bt[1…n]用來存儲結(jié)點，bt[0]不用或用來存儲結(jié)點數(shù)目。說明：完全二叉樹的順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間；按這種方法存儲的完全二叉樹，向量元素bt[i]的下標(biāo)i就是對應(yīng)結(jié)點的編號?！臼纠繄D4-7所示的完全二叉樹的順序存儲結(jié)構(gòu)如圖4-8。圖4-8完全二叉樹BT3的順序存儲BT3ABCDEFGHIJKL12下標(biāo)0123456789101112（2）完全二叉樹的順序存儲【示例】圖4-7所示的完全二叉樹的2．一般二叉樹的順序存儲（1）具體方法①將一般二叉樹添上一些“虛結(jié)點”，使其成為完全二叉樹；②為了用結(jié)點在向量中的相對位置來表示結(jié)點之間的邏輯關(guān)系，按完全二叉樹形式給結(jié)點編號；③將結(jié)點按編號存入向量對應(yīng)分量，其中“虛結(jié)點”用Φ表示。（2）二叉樹的順序存儲結(jié)構(gòu)的優(yōu)缺點：優(yōu)點是存儲結(jié)構(gòu)簡單；缺點是可能浪費大量的存儲空間。在最壞的情況下，一個深度為k的且只有k個結(jié)點的右單支樹，需要2k-1個結(jié)點的存儲空間，浪費了2k-1-k個存儲空間。【示例】如圖4-9的三個結(jié)點的添加上4個虛結(jié)點右單支樹的存儲結(jié)構(gòu)如圖4-10。圖4-9添加虛結(jié)點右單支樹1ΦΦΦΦBAC372456ABΦ3ΦΦΦC01234567下標(biāo)bt圖4-10右單支樹的順序存儲結(jié)構(gòu)2．一般二叉樹的順序存儲【示例】如圖4-9的三個結(jié)點的添加上（3）二叉樹順序存儲結(jié)構(gòu)的描述#defineMAXSIZE50//設(shè)置二叉樹的最大結(jié)點數(shù)typedefcharDataType;//定義結(jié)點類型typedefstruct{//定義二叉樹結(jié)構(gòu) DataTypebt[MAXSIZE];//存放二叉樹的結(jié)點 intnum;//存放二叉樹的結(jié)點數(shù)}SeqBT;注：如果使用元素bt[0]存放二叉樹的結(jié)點數(shù)，成員num可省略或不定義結(jié)構(gòu)而只定義數(shù)組。（3）二叉樹順序存儲結(jié)構(gòu)的描述二、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)1．結(jié)點的結(jié)構(gòu)：二叉樹的每個結(jié)點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結(jié)點除了存儲結(jié)點本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針域lchild和rchild，分別指向該結(jié)點的左孩子和右孩子。結(jié)點的結(jié)構(gòu)如圖4-11。2．結(jié)點的類型描述說明：定義新類型BinTree為指向BinTNode類型結(jié)點的指針類型，用于定義指向根結(jié)點的指針。圖4-11結(jié)點的結(jié)構(gòu)lchilddatarchildtypedefcharDataType;//定義結(jié)點數(shù)據(jù)域類型typedefstructnode{//定義結(jié)點結(jié)構(gòu) DataTypedata； structnode*lchild，*rchild；//左右孩子指針}BinTNode；//結(jié)點類型typedefBinTNode*BinTree；二、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)圖4-11結(jié)點的結(jié)構(gòu)lchi3．二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)——二叉鏈表在一棵二叉樹中，所有類型為BinTNode的結(jié)點，再加上一個指向開始結(jié)點（即根結(jié)點）的BinTree型頭指針（即根指針）root，就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，并將其稱為二叉鏈表。說明：①一個二叉鏈表由根指針root惟一確定。若二叉樹為空，則root==NULL；若結(jié)點的某個孩子不存在，則相應(yīng)的指針為空。②具有n個結(jié)點的二叉鏈表中，共有2n個指針域。其中只有n-1個用來指示結(jié)點的左、右孩子，其余的n+1個指針域為空。證明：因為二叉樹中結(jié)點總數(shù)n等于0度結(jié)點數(shù)n0、1度結(jié)點數(shù)n1和2度結(jié)點數(shù)n2之和： n=n0+n1+n2由二叉樹的性質(zhì)3：n0=n2+1，所以，n1+2·n2=n-1。而在二叉鏈表中，度為1的結(jié)點有一個指針域不空，度為2的結(jié)點的兩個指針域都不空，即n個結(jié)點的二叉鏈表中共有n1+2n2個指針域不空，即n-1個指針域不空，分別指向左右孩子。因此，其余的n+1個指針域為空。【示例】如圖4-12的二叉樹BT4的二叉鏈表如圖4-13。圖4-12二叉樹BT4ABCDEFGH圖4-13二叉樹BT4的二叉鏈表rootABF^^E^D^H^^G^^C^3．二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)——二叉鏈表證明：因為二叉樹中結(jié)點總4．帶雙親指針的二叉鏈表——三叉鏈表經(jīng)常要在二叉樹中尋找某結(jié)點的雙親時，可在每個結(jié)點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉鏈表，也稱為三叉鏈表。【示例】如圖4-12的二叉樹BT4的三叉鏈表如圖4-14。圖4-12二叉樹BT4ABCDEFGH圖4-14二叉樹BT4的三叉鏈表G^^H^^F^^E^C^D^BAroot4．帶雙親指針的二叉鏈表——三叉鏈表【示例】如圖4-12的二【課堂實踐4-4】

畫出如圖4-15的二叉樹BT5的二叉鏈表和三叉鏈表的存儲結(jié)構(gòu)。做一做圖4-15二叉樹BT5ABCDEGFH【課堂實踐4-4】做圖4-15二叉樹BT5ABCDEGFH遍歷（Traversal）：是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。一、遍歷方案1．遍歷方案：由于一棵非空的二叉樹由根結(jié)點及左、右子樹這三個基本部分組成。因此，在任一給定結(jié)點上，可以按某種次序執(zhí)行三個操作：①訪問結(jié)點本身(N)；②遍歷該結(jié)點的左子樹(L)；③遍歷該結(jié)點的右子樹(R)。以上三種操作有六種遍歷方案：NLR、LNR、LRN、NRL、RNL、RLN。由于前三種次序與后三種次序?qū)ΨQ，所以只討論先左后右的前三種次序。4.4二叉樹的遍歷

遍歷（Traversal）：是指沿著某條搜索路線，依次對樹中2．三種遍歷的命名①前（先）序遍歷NLR：訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之前，又稱為先根遍歷。②中序遍歷LNR：訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間），又稱為中根遍歷。③后序遍歷LRN：訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之后，又稱為后根遍歷。3．遍歷規(guī)則及算法①中序遍歷的遞歸算法若二叉樹非空，則依次執(zhí)行如下操作：（i）遍歷左子樹；（ii）訪問根結(jié)點；（iii）遍歷右子樹。中序遍歷的遞歸算法：

voidInOrder(BinTreeT){ if(T) {//如果二叉樹非空

InOrder(T->lchild);//遍歷左子樹

printf("%c"，T->data)//訪問根結(jié)點

InOrder(T->rchild);//遍歷右子樹

}}2．三種遍歷的命名voidInOrder(BinTree②先序遍歷的遞歸算法若二叉樹非空，則依次執(zhí)行如下操作：（i）訪問根結(jié)點；（ii）遍歷左子樹；（iii）遍歷右子樹。先序遍歷的遞歸算法：

③后序遍歷得遞歸算法若二叉樹非空，則依次執(zhí)行如下操作：（i）遍歷左子樹；（ii）遍歷右子樹；（iii）訪問根結(jié)點。后序遍歷的遞歸算法：voidPreOrder(BinTreeT){ if(T) {//如果二叉樹非空

printf("％c"，T->data);//訪問根結(jié)點

PreOrder(T->lchild);//遍歷左子樹

PreOrder(T->rchild);//遍歷右子樹

}}voidPostOrder(BinTreeT){ if(T) {//如果二叉樹非空

PostOrder(T->lchild);//遍歷左子樹

PostOrder(T->rchild);//遍歷右子樹

printf("％c"，T->data);//訪問根結(jié)點

}}②先序遍歷的遞歸算法voidPreOrder(BinTre一、遍歷序列1．中序序列：中序遍歷二叉樹時，按對結(jié)點的訪問次序形成的結(jié)點序列稱為中序序列。說明：在中序遍歷序列中，根結(jié)點左邊的結(jié)點在根的左子樹上，根結(jié)點右邊的結(jié)點在根的右子樹上。2．先序序列：先序遍歷二叉樹時，按對結(jié)點的訪問次序形成的結(jié)點序列稱為先序序列。說明：在先序遍歷序列中，最左邊的結(jié)點是根結(jié)點。3．后序序列：后序遍歷二叉樹時，按對結(jié)點的訪問次序形成的結(jié)點序列稱為后序序列。說明：在后序遍歷序列中，最右邊的結(jié)點是根結(jié)點?！臼纠繉θ鐖D4-12的二叉樹BT4，求出它的中序遍歷、先序遍歷和后序遍歷序列。一、遍歷序列【課堂實踐4-5】

寫出如圖4-15的二叉樹T2的先序遍歷序列、中序遍歷序列和后序遍歷序列。做一做圖4-15二叉樹BT5ABCDEGFH【課堂實踐4-5】做圖4-15二叉樹BT5ABCDEGFH4．確定二叉樹已知中序遍歷序列和先序遍歷序列或后序遍歷序列可以確定一棵二叉樹。具體方法：先根據(jù)先序遍歷序列確定該二叉樹的根，再根據(jù)中序遍歷序列確定根的左子樹和右子樹上的結(jié)點，而對于左子樹和右子樹可用同樣的方法確定子樹的根和其左、右子樹上的結(jié)點，這樣便可確定該二叉樹?！臼纠恳阎豢枚鏄涞闹行虮闅v序列和先序遍歷序列分別是：BGDAEHCF和ABDGCEHF，畫出這棵二叉樹。4．確定二叉樹【課堂實踐4-6】

已知二叉樹的先序序列和中序序列分別為ABDEHCFI和DBHEACIF，畫出該二叉樹的二叉鏈表存儲表示，并寫出該二叉樹的后序序列。做一做【課堂實踐4-6】做一、二叉鏈表的建立1．基本思想基于先序遍歷建立二叉鏈表，即以二叉樹的先序遍歷序列為輸入建立二叉鏈表。注：先序遍歷序列中須加入虛結(jié)點以示空指針的位置。如圖4-15的二叉樹BT5的帶虛結(jié)點的先序序列為：ABΦDGΦΦΦCEΦHΦΦFΦΦ。2．建立算法以二叉樹的先序序列為輸入建立二叉鏈表，假設(shè)虛結(jié)點輸入時以空格字符表示，算法如下：

4.5二叉樹的基本操作

voidCreateBinTree(BinTree*T) {//建立二叉鏈表。T是指向根指針的指針 charch； if((ch=getchar())=='') *T=NULL;//讀入空格，將相應(yīng)指針置空

else {//讀入非空格 *T=(BinTNode*)malloc(sizeof(BinTNode)); (*T)->data=ch； CreateBinTree(&(*T)->lchild);//建立左子樹 CreateBinTree(&(*T)->rchild);//建立右子樹 }}一、二叉鏈表的建立4.5二叉樹的基本操作voidC二、二叉鏈表的基本操作1．計算二叉樹深度分析：如果二叉樹BT為空，即BT==NULL，則BT的深度為0；如果二叉樹BT不空，則分別計算其左、右子樹的深度，左、右子樹深度的最大者加1就是該二叉樹的深度。算法步驟：①如果二叉樹BT為空，返回0，否則執(zhí)行②；②分別計算BT的左右子樹的深度；③如果左子樹深度大，返回左子樹深度+1，否則返回右子樹深度+1。遞歸算法：intBinTreeDepth(BinTNode*BT){ intleftdep,rightdep;//分別記錄左右子樹深度 if(BT==NULL) return(0); else { leftdep=BinTreeDepth(BT->lchild); rightdep=BinTreeDepth(BT->rchild); } if(leftdep>rightdep) return(leftdep+1); else return(rightdep+1);}二、二叉鏈表的基本操作intBinTreeDepth(Bi2．計算雙孩子結(jié)點個數(shù)分析：如果二叉樹BT為空，即BT==NULL，則BT無雙孩子；如果二叉樹BT不空，但左、右子樹至少有一個為空，即BT->lchild==NULL||BT->rchild==NULL，此時左、右子樹雙孩子結(jié)點個數(shù)的和就是該二叉樹的雙孩子結(jié)點的個數(shù)；如果二叉樹BT不空，且左、右子樹都不空，此時左、右子樹雙孩子結(jié)點個數(shù)的和再加1就是該二叉樹的雙孩子結(jié)點的個數(shù)。算法步驟：①如果二叉樹BT為空，返回0；②如果左右子樹至少有一個為空，返回左子樹雙孩子結(jié)點數(shù)與右子樹雙孩子結(jié)點數(shù)之和；③如果左右子樹都不空，返回左子樹雙孩子結(jié)點數(shù)與右子樹雙孩子結(jié)點數(shù)之和+1。遞歸算法：intTwoSonCount(BinTNode*BT){ if(BT==NULL) return(0); elseif(BT->lchild==NULL||BT->rchild==NULL) return(TwoSonCount(BT->lchild)+TwoSonCount(BT->rchild)); else return(TwoSonCount(BT->lchild)+TwoSonCount(BT->rchild)+1);}2．計算雙孩子結(jié)點個數(shù)intTwoSonCount(Bin3．計算結(jié)點總數(shù)分析：如果二叉樹BT為空，即BT==NULL，則BT無結(jié)點；如果二叉樹BT不空，則左、右子樹結(jié)點的個數(shù)之和加1就是該二叉樹的結(jié)點的個數(shù)。算法步驟：①如果二叉樹BT為空，返回0；②如果二叉樹BT不空，返回左子樹結(jié)點數(shù)與右子樹結(jié)點數(shù)之和加1。遞歸算法：intNodeCount(BinTNode*BT){ if(BT==NULL) return(0); else return(NodeCount(BT->lchild)+NodeCount(BT->rchild)+1);}3．計算結(jié)點總數(shù)intNodeCount(BinTNode【課堂實踐4-7】

用遞歸方法分別求二叉樹的葉子結(jié)點數(shù)和單孩子結(jié)點個數(shù)。做一做【課堂實踐4-7】做一、樹、森林到二叉樹的轉(zhuǎn)換1．將樹轉(zhuǎn)換為二叉樹轉(zhuǎn)換方法：①加線：在所有兄弟結(jié)點之間加一連線；②去線：對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其它孩子的連線；③調(diào)整：按樹的層次進行調(diào)整，將原來的右兄弟變成其右孩子，原來的無兄弟結(jié)點變成左孩子。4.6樹和森林【示例】將如圖4-17(a)的樹T2轉(zhuǎn)換為二叉樹的全過程如下：圖4-17(a)樹T2ABCDEFGHI圖4-17(b)第一步加線ABCDEFGHI圖4-17(c)第二步去線ABCDEFGHI圖4-17(d)第三步調(diào)整ABCDEFGHI一、樹、森林到二叉樹的轉(zhuǎn)換4.6樹和森林【示例】將如圖42．將一個森林轉(zhuǎn)換為二叉樹轉(zhuǎn)換方法：①樹轉(zhuǎn)換為二叉樹：將森林中的每棵樹轉(zhuǎn)換為二叉樹；②連接根結(jié)點：再將各二叉樹的根結(jié)點視為兄弟從左至右連在一起；③調(diào)整：按樹的層次進行調(diào)整，將原來的右兄弟變成其右孩子，原來的無兄弟結(jié)點變成左孩子?！臼纠繉⑷鐖D4-18(a)的森林F1轉(zhuǎn)換為二叉樹的全過程如下：第1步：將森林F1中的各棵樹轉(zhuǎn)換為二叉樹，如圖4-18(b)；圖4-18(b)第一步將各樹轉(zhuǎn)換為二叉樹ABCDEFIJKGH圖4-18(a)森林F1ABCDEFIJKGH第2步：連接各二叉樹的根結(jié)點，如圖4-18(c)；圖4-18(c)第二步連接根結(jié)點ABCDEFIJKGH第3步：按樹的層次進行調(diào)整，調(diào)整為二叉樹，如圖4-18(d)。圖4-18(d)第三步調(diào)整IJKGHABCDEF2．將一個森林轉(zhuǎn)換為二叉樹【示例】將如圖4-18(a)的森3．二叉樹到樹、森林的轉(zhuǎn)換轉(zhuǎn)換方法：①加線：在左孩子結(jié)點的雙親與左孩子結(jié)點的右孩子、右孩子的右孩子等等之間加一連線；②去線：去掉所有雙親與右孩子之間的連線；③調(diào)整：按樹的層次進行調(diào)整，將原來根結(jié)點的右孩子、右孩子的右孩子等等變成森林中樹的根，其它結(jié)點的右孩子、右孩子的右孩子等等變成兄弟?！臼纠繉⑷鐖D4-19的二叉樹BT6轉(zhuǎn)換為樹或森林的全過程如圖4-19(a)-(c)：第1步：加線，如圖4-19(a)；圖4-19二叉樹BT6GJCFABEHDI圖4-19(a)第一步加線GJCFABEHDI第2步：去線，如圖4-19(b)；第3步：調(diào)整，如圖4-19(c)。

圖4-19(b)第二步去線GJCFABEHDI圖4-19(c)第三步調(diào)整GABEHDJCFI3．二叉樹到樹、森林的轉(zhuǎn)換【示例】將如圖4-19的二叉樹BT二、樹的存儲結(jié)構(gòu)1．雙親鏈表表示法該表示法用向量表示結(jié)點，并用一個整型量parent指示其雙親的位置，稱為指向其雙親的指針。雙親鏈表向量表示的描述2．孩子鏈表表示法該表示法為樹中每個結(jié)點設(shè)置一個孩子鏈表，并將這些結(jié)點及相應(yīng)的孩子鏈表的頭指針存放在一個向量中。孩子鏈表表示的描述3．孩子兄弟鏈表表示法結(jié)點的結(jié)構(gòu)：與二叉鏈表類似，在存儲結(jié)點信息的同時，附加兩個分別指向該結(jié)點最左孩子和右鄰兄弟的指針域leftmostchild和rightsibling，即可得樹的孩子兄弟鏈表表示。孩子兄弟鏈表表示的描述#defineMaxTreeSize100//定義向量空間的容量typedefcharDataType；//定義結(jié)點數(shù)據(jù)域類型typedefstruct{//定義結(jié)點 DataTypedata；//定義結(jié)點數(shù)據(jù)域 intparent；//雙親指針，指示雙親的位置}PTreeNode；typedefstruct{//定義鏈表 PTreeNodenodes[MaxTreeSize]; intn；//結(jié)點總數(shù)}PTree；PTreeT；//T是雙親鏈表【示例】如圖4-20的樹T3的雙親鏈表表示為圖4-21。圖4-21樹T3的雙親鏈表dataparentABCDEFGHI…下標(biāo)012345678MaxTreeSize-100011133…-1圖4-20樹T3GCFABEHDI#defineMaxTreeSize100//定義向量空間的容量typedefcharDataType；//定義結(jié)點數(shù)據(jù)域類型typedefstructCnode{//孩子鏈表結(jié)點 intchild；//孩子結(jié)點在向量中對應(yīng)的序號 structCNode*next；}CNode；typedefstruct{

DataTypedata；//存放樹中結(jié)點數(shù)據(jù) CNode*firstchild；//孩子鏈表的頭指針}PTNode；typedefstruct{ PTNodenodes[MaxTreeSize]； intn，root；//n為結(jié)點總數(shù)，root指出根在向量中的位置}CTree；CTreeT；//T為孩子鏈表表示【示例】如圖4-20的樹T3的孩子鏈表表示如圖4-22。圖4-22樹T3的孩子鏈表013245678rootdata123^456^78^firstchildnotes^I^H^G^F^ED^CBAtypedefcharDataType;//定義結(jié)點數(shù)據(jù)域類型typedefstructnode{//定義結(jié)點結(jié)構(gòu) DataTypedata; structnode*leftmostchild,*rightsibling;}CSTNode;//結(jié)點類型CSTNode*T;//指向樹的開始結(jié)點的指針【示例】如圖4-20的樹T3的孩子兄弟鏈表表示為圖4-23。圖4-23樹T3的孩子兄弟鏈表A^B^E^CD^^F^G^^H^I^T3二、樹的存儲結(jié)構(gòu)#defineMaxTreeSize10三、樹的遍歷設(shè)樹T的根結(jié)點是R，根的子樹從左到右依次為T1，T2，…，Tk。樹的遍歷分為先序遍歷和后序遍歷兩種。1．樹T的先序遍歷規(guī)則若樹T非空，則①訪問根結(jié)點R；②依次先序遍歷根R的各子樹T1，T2，…，Tk。2．樹T的后序遍歷規(guī)則若樹T非空，則①依次后序遍歷根R的各子樹T1，T2，…，Tk；②訪問根結(jié)點R。說明：①前序遍歷一棵樹恰好等價于前序遍歷該樹對應(yīng)的二叉樹；②后序遍歷一棵樹恰好等價于中序遍歷該樹對應(yīng)的二叉樹?！臼纠繄D4-17(a)的樹T2轉(zhuǎn)換為二叉樹如圖4-17(d)樹T2的先序序列為：ABEFGCHDI。轉(zhuǎn)換得到的二叉樹的先序序列為：ABEFGCHDI。樹T2的后序序列為：EFGBHCIDA。轉(zhuǎn)換得到的二叉樹的中序序列為：EFGBHCIDA。轉(zhuǎn)換得到的二叉樹的后序序列為：GFEHIDCBA。顯然，前序遍歷一棵樹恰好等價于前序遍歷該樹對應(yīng)的二叉樹，后序遍歷一棵樹恰好等價于中序遍歷該樹對應(yīng)的二叉樹。三、樹的遍歷【示例】圖4-17(a)的樹T2轉(zhuǎn)換為二叉樹如圖【課堂實踐4-8】

已知一個森林的前序遍歷序列為CBADHEGF，后序遍歷序列為ABCDEFGH，畫出該森林所對應(yīng)的二叉樹，并畫出該森林。做一做【課堂實踐4-8】做一、哈夫曼樹（HuffmanTree）的有關(guān)概念1．樹的路徑長度：從根結(jié)點到樹中每一結(jié)點的路徑長度之和稱為樹的路徑長度。說明：在結(jié)點數(shù)目相同的二叉樹中，完全二叉樹的路徑長度最短。2．樹的帶權(quán)路徑長度①結(jié)點的權(quán)（Weight）：賦予樹中某結(jié)點的一個有某種意義的實數(shù)，稱為該結(jié)點的權(quán)。②結(jié)點的帶權(quán)路徑長度：結(jié)點到樹根之間路徑長度與該結(jié)點上權(quán)的乘積，稱為結(jié)點的帶權(quán)路徑長度。③樹的帶權(quán)路徑長度（WeightedPathLengthofTree）：樹中所有葉結(jié)點的帶權(quán)路徑長度之和，稱為樹的帶權(quán)路徑長度，亦稱為樹的代價。記為：4.7哈夫曼樹及其應(yīng)用，n表示葉子結(jié)點的數(shù)目，wi和li表示葉結(jié)點ki的權(quán)值和根到ki之間的路徑長度。一、哈夫曼樹（HuffmanTree）的有關(guān)概念4.7哈3．哈夫曼樹：在權(quán)為wl,w2,…,wn的n個葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長度最小（即代價最?。┑亩鏄浞Q為哈夫曼樹或最優(yōu)二叉樹。說明：①葉子上的權(quán)值均相同時，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹；②哈夫曼樹中，權(quán)越大的葉子離根越近；③哈夫曼樹的形態(tài)不唯一，但WPL值相同且最小?！臼纠拷o定5個葉子結(jié)點a，b，c，d和e，分別帶權(quán)7，6，12，15和10?？蓸?gòu)造出許多棵二叉樹，如圖4-24所示的是其中兩棵二叉樹。它們的帶權(quán)路徑長度分別為：(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實際上圖(b)的二叉樹是所有以a，b，c，d和e為葉子的二叉樹中WPL最小的二叉樹，它就是哈夫曼樹。acbed圖4-24兩棵二叉樹(a)(b)cdbae3．哈夫曼樹：在權(quán)為wl,w2,…,wn的n個葉子所構(gòu)成的所二、哈夫曼樹的構(gòu)造1．哈夫曼算法基本思想：①根據(jù)給定的n個權(quán)值wl,w2,…,wn構(gòu)成n棵二叉樹的森林F={T1,T2,…,Tn}，其中每棵二叉樹Ti中都只有一個權(quán)值為wi的根結(jié)點，其左右子樹均空；②在森林F中選出兩棵根結(jié)點權(quán)值最小的樹（當(dāng)這樣的樹不止兩棵樹時，可以從中任選兩棵），將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結(jié)點作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子（誰左，誰右無關(guān)緊要），將這兩個孩子的權(quán)值之和作為新樹根的權(quán)值；③對新的森林F重復(fù)②，直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼樹。用哈夫曼算法構(gòu)造哈夫曼樹的過程：給定5個葉子結(jié)點a，b，c，d和e，分別帶權(quán)7，6，12，15和10。用哈夫曼算法構(gòu)造哈夫曼樹的過程如下：第1步：根據(jù)給定的5個權(quán)值7，6，12，15和10構(gòu)成5棵二叉樹的森林F={T1,T2,T3,T4,T5}，如圖4-25(a)；第2步：在森林F中選出兩棵根結(jié)點權(quán)值最小的樹，將這兩棵樹合并成一棵新樹，并添加到森林中，得到新的森林，如圖4-25(b)；

圖4-25(a)76121510abcde圖4-25(b)121510cde1376ab第3步：重復(fù)第2步，進行第二次合并，得到新的森林，如圖4-25(c)；第4步：重復(fù)第2步，進行第三次合并，得到新的森林，如圖4-25(d)；

圖4-25(c)15d1376ab221210ce圖4-25(d)221210ce15d1376ab28第5步：重復(fù)第2步，進行第四次合并，由于森林F中只剩下一棵樹，所以它就是哈夫曼樹，如圖4-25(e)。

圖4-25(e)221210ce15d1376ab2850二、哈夫曼樹的構(gòu)造用哈夫曼算法構(gòu)造哈夫曼樹的過程：給定5個葉三、哈夫曼樹算法的實現(xiàn)1．哈夫曼樹結(jié)點的結(jié)構(gòu)哈夫曼樹的結(jié)點用一個大小為2n-1的向量來存儲，每個結(jié)點包含權(quán)值域weight、指示左右孩子結(jié)點在向量中下標(biāo)的整型量lchild和rchild、指示雙親結(jié)點在向量中下標(biāo)的整型量parent。結(jié)點結(jié)構(gòu)如圖4-26。2．哈夫曼樹的描述注意：①因為C數(shù)組的下界為0，故用-1表示空指針。樹中某結(jié)點的lchild、rchild和parent不等于-1時，它們分別是該結(jié)點的左、右孩子和雙親結(jié)點在向量中的下標(biāo)。②這里設(shè)置parent域有兩個作用：其一是使查找某結(jié)點的雙親變得簡單；其二是可通過判定parent的值是否為-1來區(qū)分根與非根結(jié)點。weightlchildrchildparent圖4-26結(jié)點結(jié)構(gòu)#definen100//葉子數(shù)目#definem2*n-1//樹中結(jié)點總數(shù)typedefstruct{//定義結(jié)點類型 floatweight;//定義權(quán)值域 intlchild,rchild,parent;//定義左右孩子及雙親指針}HTNode;typedefHTNodeHuffmanTree[m];/*定義HuffmanTree為新的類型標(biāo)識符，用該標(biāo)識符定義的變量是具有HTNode類型的含有m個元素的向量。*/三、哈夫曼樹算法的實現(xiàn)weightlchi3．哈夫曼樹T算法實現(xiàn)的步驟（1）初始化：將T[0…m-1]中2n-1個結(jié)點里的三個指針均置為空(即置為-1)，權(quán)值置為0。（2）輸入：讀入n個葉子的權(quán)值存于向量的前n個分量(即T[0…n-1])中。它們是初始森林中n個孤立的根結(jié)點上的權(quán)值。（3）合并：對森林中的樹共進行n-1次合并，所產(chǎn)生的新結(jié)點依次放入向量T的第i個分量中(n≤i≤m-1)。每次合并分兩步：①在當(dāng)前森林T[0…i-1]的所有結(jié)點中，選取權(quán)最小和次小的兩個根結(jié)點T[p1]和T[p2]作為合并對象，這里0≤p1，p2≤i-1。②將根為T[p1]和T[p2]的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結(jié)點T[i]。具體操作：（i）將T[p1]和T[p2]的parent置為i;（ii）將T[i]的lchild和rchild分別置為p1和p2;（iii）新結(jié)點T[i]的權(quán)值置為T[p1]和T[p2]的權(quán)值之和。3．哈夫曼樹T算法實現(xiàn)的步驟4．哈夫曼樹T算法實現(xiàn)①初始化函數(shù)voidInitHuffmanTree(HuffmanTreeT){//初始化 inti; for(i=0;i<m;i++) { T[i].weight=0;

T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1; }}4．哈夫曼樹T算法實現(xiàn)②輸入權(quán)值函數(shù)voidInputWeight(HuffmanTreeT){//輸入權(quán)值 floatw; inti; for(i=0;i<n;i++) { printf("\n輸入第%d個權(quán)值:",i+1); scanf("%f",&w); T[i].weight=w; }}②輸入權(quán)值函數(shù)③選擇兩個權(quán)最小的根結(jié)點函數(shù)voidSelectMin(HuffmanTreeT,inti,int*p1,int*p2){//選擇兩個小的結(jié)點 floatmin1=999999;//定義并初始化最小權(quán)值 floatmin2=999999;//定義并初始化次小權(quán)值 intj; for(j=0;j<=i;j++) if(T[j].parent==-1) if(T[j].weight<min1) { min2=min1;

min1=T[j].weight; *p2=*p1; *p1=j; } elseif(T[j].weight<min2) { min2=T[j].weight *p2=j; }}③選擇兩個權(quán)最小的根結(jié)點函數(shù)④建立哈夫曼樹函數(shù)voidCreateHuffmanTree(HuffmanTreeT){//構(gòu)造哈夫曼樹，T[m-1]為其根結(jié)點 inti,p1,p2; InitHuffmanTree(T);//將T初始化 InputWeight(T);//輸入葉子權(quán)值至weight域 for(i=n;i<m;i++) {//共n-1次合并,新結(jié)點存于T[i]中 SelectMin(T,i-1,&p1,&p2); T[p1].parent=T[p2].parent=i; T[i].lchild=p1; T[i].rchild=p2; T[i].weight=T[p1].weight+T[p2].weight; }}④建立哈夫曼樹函數(shù)四、哈夫曼編碼1．編碼和解碼數(shù)據(jù)壓縮過程稱為編碼。即將文件中的每個字符均轉(zhuǎn)換為一個惟一的二進制位串。數(shù)據(jù)解壓過程稱為解碼。即將二進制位串轉(zhuǎn)換為對應(yīng)的字符。2．等長、變長編碼方案給定的字符集C，可能存在多種編碼方案。①等長編碼方案等長編碼方案將給定字符集C中每個字符的碼長定為[lg|C|]，|C|表示字符集的大小。②變長編碼方案變長編碼方案將頻度高的字符編碼設(shè)置較短，將頻度低的字符編碼設(shè)置較長。注意：變長編碼可能使解碼產(chǎn)生二義性。原因是某些字符的編碼可能與其他字符的編碼開始部分(稱為前綴)相同?！臼纠吭O(shè)待壓縮的數(shù)據(jù)文件共有100000個字符，這些字符均取自字符集C={a，b，c，d，e，f}，等長編碼需要三位二進制數(shù)字來表示六個字符，因此，整個文件的編碼長度為300000位。【示例】設(shè)待壓縮的數(shù)據(jù)文件共有100000個字符，這些字符均取自字符集C={a，b，c，d，e，f}，其中每個字符在文件中出現(xiàn)的次數(shù)（簡稱頻度）見表4-1。根據(jù)計算公式：(45*1+13*3+12*3+16*3+9*4+5*4)*1000=224000整個文件被編碼為224000位，比定長編碼方式節(jié)約了約25％的存儲空間。字符abcdef頻度（千次）4513121695定長編碼000001010011100101變長編碼010010111011101111【示例】設(shè)E、T、W分別編碼為00、01、0001，則解碼時無法確定信息串0001是ET還是W。四、哈夫曼編碼【示例】設(shè)待壓縮的數(shù)據(jù)文件共有100000個字3．前綴碼方案對字符集進行編碼時，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼稱為前綴（編）碼。注意：等長編碼是前綴碼。4．最優(yōu)前綴碼平均碼長或文件總長最小的前綴編碼稱為最優(yōu)的前綴碼。最優(yōu)的前綴碼對文件的壓縮效果亦最佳。其中：pi為第i個字符的概率，li為碼長。【示例】若將前表所示的文件作為統(tǒng)計的樣本，則a至f六個字符的概率分別為0.45，0.13，0.12，0.16，0.09，0.05，對變長編碼求得的平均碼長為2.24，優(yōu)于定長編碼（平均碼長為3）。3．前綴碼方案其中：pi為第i個字符的概率，li為碼長。5．根據(jù)最優(yōu)二叉樹構(gòu)造哈夫曼編碼利用哈夫曼樹很容易求出給定字符集及其概率(或頻度)分布的最優(yōu)前綴碼。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉20％至90％，其壓縮效率取決于被壓縮文件的特征。（1）編碼構(gòu)造方法①用字符ci作為葉子，概率pi或頻度fi作為葉子ci的權(quán)，構(gòu)造一棵哈夫曼樹，并將樹中左分支和右分支分別標(biāo)記為0和1；②將從根到葉子的路徑上的標(biāo)號依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱哈夫曼編碼）?！臼纠吭O(shè)字符集C={a，b，c，d，e，f}，其中每個字符在文件中出現(xiàn)的頻度分別為：45，13，12，16，9，5（千次）。求一個哈夫曼編碼。先構(gòu)造哈夫曼樹并將樹中左分支和右分支分別標(biāo)記為0和1，如圖4-27；再將從根到葉子的路徑上的標(biāo)號依次相連，得到如下哈夫曼編碼。a：0 b：100 c：101d：110 e：1110 f：1111圖4-2716251312bc1495efd30554510000000111115．根據(jù)最優(yōu)二叉樹構(gòu)造哈夫曼編碼【示例】設(shè)字符集C={a，b（2）哈夫曼編碼為最優(yōu)前綴碼由哈夫曼樹求得編碼為最優(yōu)前綴碼的原因：①每個葉子字符ci的碼長恰為從根到該葉子的路徑長度li，平均碼長(或文件總長)又是二叉樹的帶權(quán)路徑長度WPL。而哈夫曼樹是WPL最小的二叉樹，因此編碼的平均碼長(或文件總長)亦最小。②樹中沒有一片葉子是另一葉子的祖先，每片葉子對應(yīng)的編碼就不可能是其它葉子編碼的前綴。即上述編碼是二進制的前綴碼。（2）哈夫曼編碼為最優(yōu)前綴碼（3）求哈夫曼編碼的算法①思想方法：給定字符集的哈夫曼樹生成后，求哈夫曼編碼的具體實現(xiàn)過程是：依次以葉子T[i](0≤i≤n-1)為出發(fā)點，向上回溯至根為止。上溯時走左分支則生成代碼0，走右分支則生成代碼1。注意：（i）由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個臨時向量中，并設(shè)一個指針start指示編碼在該向量中的起始位置（start初始時指示向量的結(jié)束位置）。（ii）當(dāng)某字符編碼完成時，從臨時向量的start處將編碼復(fù)制到該字符相應(yīng)的位串bits中即可。（ii）因為字符集大小為n，故變長編碼的長度不會超過n，加上一個結(jié)束符'\0'，bits的大小應(yīng)為n+1。②字符集編碼的存儲結(jié)構(gòu)及其算法描述

typedefstruct{ charch;//存儲字符 charbits[n+1];//存放編碼位串}CodeNode;typedefCodeNodeHuffmanCode[n];

（3）求哈夫曼編碼的算法typedefstruct③算法實現(xiàn)

voidCharSetHuffmanEncoding(HuffmanTreeT,HuffmanCodeH){//根據(jù)哈夫曼樹T求哈夫曼編碼表H intc,p,i;//c和p分別指示T中孩子和雙親的位置 charcd[n+1];//臨時存放編碼 intstart;//指示編碼在cd中的起始位置 cd[n]=‘\0’;//編碼結(jié)束符 for(i=0;i<n;i++) {//依次求葉子T[i]的編碼

H[i].ch=getchar();//讀入葉子T[i]對應(yīng)的字符

start=n;//編碼起始位置的初值

c=i;//從葉子T[i]開始上溯

while((p=T[c].parent)>=0) { cd[--start]=(T[p].lchild==c)?'0'：'1'; c=p;//繼續(xù)上溯

} strcpy(H[i].bits,&cd[start]);//復(fù)制編碼位串 }}③算法實現(xiàn)6．文件的編碼和解碼有了字符集的哈夫曼編碼表之后，對數(shù)據(jù)文件的編碼過程是：依次讀入文件中的字符c，在哈夫曼編碼表H中找到此字符，若H[i].ch=c，則將字符c轉(zhuǎn)換為H[i].bits中存放的編碼串。對壓縮后的數(shù)據(jù)文件進行解碼則必須借助于哈夫曼樹T，其過程是：依次讀入文件的二進制碼，從哈夫曼樹的根結(jié)點(即T[m-1])出發(fā)，若當(dāng)前讀入0，則走向左孩子，否則走向右孩子。一旦到達某一葉子T[i]時便譯出相應(yīng)的字符H[i].ch。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。

6．文件的編碼和解碼【課堂實踐4-9】

假設(shè)通信電文使用的字符集為{a，b，c，d，e，f，g，h}，各字符在電文中出現(xiàn)的頻度分別為：7，26，2，28，13，10，3，11，請為這8個字符設(shè)計哈夫曼編碼。要求：你所構(gòu)造的哈夫曼樹中左孩子結(jié)點的權(quán)值不大于右孩子結(jié)點的權(quán)值且按左分支為0和右分支為1的規(guī)則，分別寫出與每個字符對應(yīng)的編碼。做一做【課堂實踐4-9】做引例分析與實現(xiàn)

1．引例分析

此問題可通過設(shè)計一個哈夫曼編碼、譯碼系統(tǒng)來解決。對文本文件中的字符用二進制位串進行哈夫曼編碼，形成加密文件；反過來，可將加密文件進行譯碼還原成文本文件。首先從文本文件中讀入各字符，統(tǒng)計不同字符在文件中出現(xiàn)的次數(shù)（空格、換行、標(biāo)點等也按字符處理），作為該字符的權(quán)值；然后根據(jù)字符及其權(quán)值構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼；再將文本文件利用哈夫曼樹進行編碼，存儲成由二進制位串組成的加密文件；最后對加密文件進行解密，將加密文件還原成原來的文本文件。

引例分析與實現(xiàn)1．引例分析（1）數(shù)據(jù)結(jié)構(gòu)描述#definen2*26+4 /*文件含字符的最大個數(shù)（大小寫字母+2個標(biāo)點符號+空格+回車換行）*/#definem2*n-1 //哈夫曼樹中結(jié)點總數(shù)最大值#defineMax10000 //文件含字符的最大個數(shù)/*n1表示文件實際含字符個數(shù)，m1表示哈夫曼樹中實際結(jié)點總數(shù)，數(shù)組size用于存放各字符出現(xiàn)的次數(shù)（權(quán)值）*/intn1,m1,size[n];charCharSet[n]; //用于存放文件中所使用的不同字符charStr[Max+1],BM[Max*n+1]; /*數(shù)組Str用于存放原文件字符串，BM用于存放加密后的二進制串*/charStr1[Max+1]; //數(shù)組Str1用于存放解密字符串引例分析與實現(xiàn)

（1）數(shù)據(jù)結(jié)構(gòu)描述引例分析與實現(xiàn)typedefstruct{//定義結(jié)點類型

intweight; //定義權(quán)值域

intlchild,rchild,parent;//定義左右孩子及雙親指針}HTNode;/*定義HuffmanTree為新的類型標(biāo)識符，用該標(biāo)識符定義的變量是具有HTNode類型的含有m個元素的向量。*/typedefHTNodeHuffmanTree[m];typedefstruct{ charch; //存儲字符

charbits[n+1]; //存放編碼位串}CodeNode;typedefCodeNodeHuffmanCode[n];引例分析與實現(xiàn)

typedefstruct引例分析與實現(xiàn)（2）功能函數(shù)①哈夫曼樹T初始化函數(shù)：voidInitHuffmanTree(HuffmanTreeT)②寫入權(quán)值函數(shù)函數(shù)：voidWriteWeight(HuffmanTreeT)③選擇兩個權(quán)最小的根結(jié)點函數(shù)：voidSelectMin(HuffmanTreeT,inti,int*p1,int*p2)④構(gòu)造哈夫曼樹函數(shù)：voidCreateHuffmanTree(HuffmanTreeT)⑤根據(jù)哈夫曼樹T求哈夫曼編碼表H：voidCharSetHuffmanEncoding(HuffmanTreeT,HuffmanCodeH)⑥讀文本文件統(tǒng)計實際不同字符及個數(shù)n1函數(shù)：voidReadFile()引例分析與實現(xiàn)

voidInitHuffmanTree(HuffmanTreeT){//哈夫曼樹T初始化

inti; for(i=0;i<m1;i++) { T[i].weight=0; T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1; }}voidWriteWeight(HuffmanTreeT){//寫入權(quán)值函數(shù)

inti,j,k=0; for(i=0;i<n1;i++) for(j=k;j<n;j++) if(size[j]) {

T[i].weight=size[j]; k=j+1; break; }}voidSelectMin(HuffmanTreeT,inti,int*p1,int*p2){//選擇兩個權(quán)最小的根結(jié)點函數(shù)

intmin1=999999; //定義并初始化最小權(quán)值

intmin2=999999; //定義并初始化次小權(quán)值

intj; for(j=0;j<=i;j++) if(T[j].parent==-1) if(T[j].weight<min1) { min2=min1;

min1=T[j].weight; *p2=*p1; *p1=j; } elseif(T[j].weight<min2) { min2=T[j].weight; *p2