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

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

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

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

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

已知在一棵度為3的樹中，度為2的結(jié)點(diǎn)數(shù)為4，度為3的結(jié)點(diǎn)數(shù)為3，求該樹中的葉子結(jié)點(diǎn)數(shù)。提示：分別從樹的結(jié)點(diǎn)總數(shù)和樹的孩子結(jié)點(diǎn)總數(shù)兩個(gè)角度考慮。做一做【課堂實(shí)踐4-1】做一、二叉樹的定義1.二叉樹的遞歸定義二叉樹（BinaryTree）是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。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é)點(diǎn)數(shù)目最多為2i-1(i≥1)個(gè)。性質(zhì)2：深度為k的二叉樹至多有2k-1(k≥1)個(gè)結(jié)點(diǎn)。性質(zhì)3：在任意一棵非空二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。性質(zhì)3說明：在任意非空二叉樹中葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)數(shù)多1個(gè)。證明：

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

當(dāng)i=1時(shí)，因?yàn)榈?層上只有一個(gè)根結(jié)點(diǎn)，而2i-1=20=1。所以命題成立。

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

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

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

因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度數(shù)均不大于2，所以結(jié)點(diǎn)總數(shù)（記為n）應(yīng)等于0度結(jié)點(diǎn)數(shù)n0、1度結(jié)點(diǎn)數(shù)n1和2度結(jié)點(diǎn)數(shù)n2之和： n=n0+n1+n2

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

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

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

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

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

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

，其中

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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．計(jì)算二叉樹深度分析：如果二叉樹BT為空，即BT==NULL，則BT的深度為0；如果二叉樹BT不空，則分別計(jì)算其左、右子樹的深度，左、右子樹深度的最大者加1就是該二叉樹的深度。算法步驟：①如果二叉樹BT為空，返回0，否則執(zhí)行②；②分別計(jì)算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．計(jì)算雙孩子結(jié)點(diǎn)個(gè)數(shù)分析：如果二叉樹BT為空，即BT==NULL，則BT無雙孩子；如果二叉樹BT不空，但左、右子樹至少有一個(gè)為空，即BT->lchild==NULL||BT->rchild==NULL，此時(shí)左、右子樹雙孩子結(jié)點(diǎn)個(gè)數(shù)的和就是該二叉樹的雙孩子結(jié)點(diǎn)的個(gè)數(shù)；如果二叉樹BT不空，且左、右子樹都不空，此時(shí)左、右子樹雙孩子結(jié)點(diǎn)個(gè)數(shù)的和再加1就是該二叉樹的雙孩子結(jié)點(diǎn)的個(gè)數(shù)。算法步驟：①如果二叉樹BT為空，返回0；②如果左右子樹至少有一個(gè)為空，返回左子樹雙孩子結(jié)點(diǎn)數(shù)與右子樹雙孩子結(jié)點(diǎn)數(shù)之和；③如果左右子樹都不空，返回左子樹雙孩子結(jié)點(diǎn)數(shù)與右子樹雙孩子結(jié)點(diǎn)數(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．計(jì)算雙孩子結(jié)點(diǎn)個(gè)數(shù)intTwoSonCount(Bin3．計(jì)算結(jié)點(diǎn)總數(shù)分析：如果二叉樹BT為空，即BT==NULL，則BT無結(jié)點(diǎn)；如果二叉樹BT不空，則左、右子樹結(jié)點(diǎn)的個(gè)數(shù)之和加1就是該二叉樹的結(jié)點(diǎn)的個(gè)數(shù)。算法步驟：①如果二叉樹BT為空，返回0；②如果二叉樹BT不空，返回左子樹結(jié)點(diǎn)數(shù)與右子樹結(jié)點(diǎn)數(shù)之和加1。遞歸算法：intNodeCount(BinTNode*BT){ if(BT==NULL) return(0); else return(NodeCount(BT->lchild)+NodeCount(BT->rchild)+1);}3．計(jì)算結(jié)點(diǎn)總數(shù)intNodeCount(BinTNode【課堂實(shí)踐4-7】

用遞歸方法分別求二叉樹的葉子結(jié)點(diǎn)數(shù)和單孩子結(jié)點(diǎn)個(gè)數(shù)。做一做【課堂實(shí)踐4-7】做一、樹、森林到二叉樹的轉(zhuǎn)換1．將樹轉(zhuǎn)換為二叉樹轉(zhuǎn)換方法：①加線：在所有兄弟結(jié)點(diǎn)之間加一連線；②去線：對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其長子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線；③調(diào)整：按樹的層次進(jìn)行調(diào)整，將原來的右兄弟變成其右孩子，原來的無兄弟結(jié)點(diǎn)變成左孩子。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．將一個(gè)森林轉(zhuǎn)換為二叉樹轉(zhuǎn)換方法：①樹轉(zhuǎn)換為二叉樹：將森林中的每棵樹轉(zhuǎn)換為二叉樹；②連接根結(jié)點(diǎn)：再將各二叉樹的根結(jié)點(diǎn)視為兄弟從左至右連在一起；③調(diào)整：按樹的層次進(jìn)行調(diào)整，將原來的右兄弟變成其右孩子，原來的無兄弟結(jié)點(diǎn)變成左孩子?！臼纠繉⑷鐖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é)點(diǎn)，如圖4-18(c)；圖4-18(c)第二步連接根結(jié)點(diǎn)ABCDEFIJKGH第3步：按樹的層次進(jìn)行調(diào)整，調(diào)整為二叉樹，如圖4-18(d)。圖4-18(d)第三步調(diào)整IJKGHABCDEF2．將一個(gè)森林轉(zhuǎn)換為二叉樹【示例】將如圖4-18(a)的森3．二叉樹到樹、森林的轉(zhuǎn)換轉(zhuǎn)換方法：①加線：在左孩子結(jié)點(diǎn)的雙親與左孩子結(jié)點(diǎn)的右孩子、右孩子的右孩子等等之間加一連線；②去線：去掉所有雙親與右孩子之間的連線；③調(diào)整：按樹的層次進(jìn)行調(diào)整，將原來根結(jié)點(diǎn)的右孩子、右孩子的右孩子等等變成森林中樹的根，其它結(jié)點(diǎn)的右孩子、右孩子的右孩子等等變成兄弟?！臼纠繉⑷鐖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二、樹的存儲(chǔ)結(jié)構(gòu)1．雙親鏈表表示法該表示法用向量表示結(jié)點(diǎn)，并用一個(gè)整型量parent指示其雙親的位置，稱為指向其雙親的指針。雙親鏈表向量表示的描述2．孩子鏈表表示法該表示法為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。孩子鏈表表示的描述3．孩子兄弟鏈表表示法結(jié)點(diǎn)的結(jié)構(gòu)：與二叉鏈表類似，在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域leftmostchild和rightsibling，即可得樹的孩子兄弟鏈表表示。孩子兄弟鏈表表示的描述#defineMaxTreeSize100//定義向量空間的容量typedefcharDataType；//定義結(jié)點(diǎn)數(shù)據(jù)域類型typedefstruct{//定義結(jié)點(diǎn) DataTypedata；//定義結(jié)點(diǎn)數(shù)據(jù)域 intparent；//雙親指針，指示雙親的位置}PTreeNode；typedefstruct{//定義鏈表 PTreeNodenodes[MaxTreeSize]; intn；//結(jié)點(diǎn)總數(shù)}PTree；PTreeT；//T是雙親鏈表【示例】如圖4-20的樹T3的雙親鏈表表示為圖4-21。圖4-21樹T3的雙親鏈表dataparentABCDEFGHI…下標(biāo)012345678MaxTreeSize-100011133…-1圖4-20樹T3GCFABEHDI#defineMaxTreeSize100//定義向量空間的容量typedefcharDataType；//定義結(jié)點(diǎn)數(shù)據(jù)域類型typedefstructCnode{//孩子鏈表結(jié)點(diǎn) intchild；//孩子結(jié)點(diǎn)在向量中對(duì)應(yīng)的序號(hào) structCNode*next；}CNode；typedefstruct{

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

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

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

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

圖4-25(e)221210ce15d1376ab2850二、哈夫曼樹的構(gòu)造用哈夫曼算法構(gòu)造哈夫曼樹的過程：給定5個(gè)葉三、哈夫曼樹算法的實(shí)現(xiàn)1．哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu)哈夫曼樹的結(jié)點(diǎn)用一個(gè)大小為2n-1的向量來存儲(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．哈夫曼樹的描述注意：①因?yàn)镃數(shù)組的下界為0，故用-1表示空指針。樹中某結(jié)點(diǎn)的lchild、rchild和parent不等于-1時(shí)，它們分別是該結(jié)點(diǎn)的左、右孩子和雙親結(jié)點(diǎn)在向量中的下標(biāo)。②這里設(shè)置parent域有兩個(gè)作用：其一是使查找某結(jié)點(diǎn)的雙親變得簡單；其二是可通過判定parent的值是否為-1來區(qū)分根與非根結(jié)點(diǎn)。weightlchildrchildparent圖4-26結(jié)點(diǎn)結(jié)構(gòu)#definen100//葉子數(shù)目#definem2*n-1//樹中結(jié)點(diǎn)總數(shù)typedefstruct{//定義結(jié)點(diǎn)類型 floatweight;//定義權(quán)值域 intlchild,rchild,parent;//定義左右孩子及雙親指針}HTNode;typedefHTNodeHuffmanTree[m];/*定義HuffmanTree為新的類型標(biāo)識(shí)符，用該標(biāo)識(shí)符定義的變量是具有HTNode類型的含有m個(gè)元素的向量。*/三、哈夫曼樹算法的實(shí)現(xiàn)weightlchi3．哈夫曼樹T算法實(shí)現(xiàn)的步驟（1）初始化：將T[0…m-1]中2n-1個(gè)結(jié)點(diǎn)里的三個(gè)指針均置為空(即置為-1)，權(quán)值置為0。（2）輸入：讀入n個(gè)葉子的權(quán)值存于向量的前n個(gè)分量(即T[0…n-1])中。它們是初始森林中n個(gè)孤立的根結(jié)點(diǎn)上的權(quán)值。（3）合并：對(duì)森林中的樹共進(jìn)行n-1次合并，所產(chǎn)生的新結(jié)點(diǎn)依次放入向量T的第i個(gè)分量中(n≤i≤m-1)。每次合并分兩步：①在當(dāng)前森林T[0…i-1]的所有結(jié)點(diǎn)中，選取權(quán)最小和次小的兩個(gè)根結(jié)點(diǎn)T[p1]和T[p2]作為合并對(duì)象，這里0≤p1，p2≤i-1。②將根為T[p1]和T[p2]的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結(jié)點(diǎn)T[i]。具體操作：（i）將T[p1]和T[p2]的parent置為i;（ii）將T[i]的lchild和rchild分別置為p1和p2;（iii）新結(jié)點(diǎn)T[i]的權(quán)值置為T[p1]和T[p2]的權(quán)值之和。3．哈夫曼樹T算法實(shí)現(xiàn)的步驟4．哈夫曼樹T算法實(shí)現(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算法實(shí)現(xiàn)②輸入權(quán)值函數(shù)voidInputWeight(HuffmanTreeT){//輸入權(quán)值 floatw; inti; for(i=0;i<n;i++) { printf("\n輸入第%d個(gè)權(quán)值:",i+1); scanf("%f",&w); T[i].weight=w; }}②輸入權(quán)值函數(shù)③選擇兩個(gè)權(quán)最小的根結(jié)點(diǎn)函數(shù)voidSelectMin(HuffmanTreeT,inti,int*p1,int*p2){//選擇兩個(gè)小的結(jié)點(diǎn) 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; }}③選擇兩個(gè)權(quán)最小的根結(jié)點(diǎn)函數(shù)④建立哈夫曼樹函數(shù)voidCreateHuffmanTree(HuffmanTreeT){//構(gòu)造哈夫曼樹，T[m-1]為其根結(jié)點(diǎn) inti,p1,p2; InitHuffmanTree(T);//將T初始化 InputWeight(T);//輸入葉子權(quán)值至weight域 for(i=n;i<m;i++) {//共n-1次合并,新結(jié)點(diǎn)存于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ù)壓縮過程稱為編碼。即將文件中的每個(gè)字符均轉(zhuǎn)換為一個(gè)惟一的二進(jìn)制位串。數(shù)據(jù)解壓過程稱為解碼。即將二進(jìn)制位串轉(zhuǎn)換為對(duì)應(yīng)的字符。2．等長、變長編碼方案給定的字符集C，可能存在多種編碼方案。①等長編碼方案等長編碼方案將給定字符集C中每個(gè)字符的碼長定為[lg|C|]，|C|表示字符集的大小。②變長編碼方案變長編碼方案將頻度高的字符編碼設(shè)置較短，將頻度低的字符編碼設(shè)置較長。注意：變長編碼可能使解碼產(chǎn)生二義性。原因是某些字符的編碼可能與其他字符的編碼開始部分(稱為前綴)相同?！臼纠吭O(shè)待壓縮的數(shù)據(jù)文件共有100000個(gè)字符，這些字符均取自字符集C={a，b，c，d，e，f}，等長編碼需要三位二進(jìn)制數(shù)字來表示六個(gè)字符，因此，整個(gè)文件的編碼長度為300000位?！臼纠吭O(shè)待壓縮的數(shù)據(jù)文件共有100000個(gè)字符，這些字符均取自字符集C={a，b，c，d，e，f}，其中每個(gè)字符在文件中出現(xiàn)的次數(shù)（簡稱頻度）見表4-1。根據(jù)計(jì)算公式：(45*1+13*3+12*3+16*3+9*4+5*4)*1000=224000整個(gè)文件被編碼為224000位，比定長編碼方式節(jié)約了約25％的存儲(chǔ)空間。字符abcdef頻度（千次）4513121695定長編碼000001010011100101變長編碼010010111011101111【示例】設(shè)E、T、W分別編碼為00、01、0001，則解碼時(shí)無法確定信息串0001是ET還是W。四、哈夫曼編碼【示例】設(shè)待壓縮的數(shù)據(jù)文件共有100000個(gè)字3．前綴碼方案對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼稱為前綴（編）碼。注意：等長編碼是前綴碼。4．最優(yōu)前綴碼平均碼長或文件總長最小的前綴編碼稱為最優(yōu)的前綴碼。最優(yōu)的前綴碼對(duì)文件的壓縮效果亦最佳。其中：pi為第i個(gè)字符的概率，li為碼長?！臼纠咳魧⑶氨硭镜奈募鳛榻y(tǒng)計(jì)的樣本，則a至f六個(gè)字符的概率分別為0.45，0.13，0.12，0.16，0.09，0.05，對(duì)變長編碼求得的平均碼長為2.24，優(yōu)于定長編碼（平均碼長為3）。3．前綴碼方案其中：pi為第i個(gè)字符的概率，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)號(hào)依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱哈夫曼編碼）?！臼纠吭O(shè)字符集C={a，b，c，d，e，f}，其中每個(gè)字符在文件中出現(xiàn)的頻度分別為：45，13，12，16，9，5（千次）。求一個(gè)哈夫曼編碼。先構(gòu)造哈夫曼樹并將樹中左分支和右分支分別標(biāo)記為0和1，如圖4-27；再將從根到葉子的路徑上的標(biāo)號(hà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)前綴碼的原因：①每個(gè)葉子字符ci的碼長恰為從根到該葉子的路徑長度li，平均碼長(或文件總長)又是二叉樹的帶權(quán)路徑長度WPL。而哈夫曼樹是WPL最小的二叉樹，因此編碼的平均碼長(或文件總長)亦最小。②樹中沒有一片葉子是另一葉子的祖先，每片葉子對(duì)應(yīng)的編碼就不可能是其它葉子編碼的前綴。即上述編碼是二進(jìn)制的前綴碼。（2）哈夫曼編碼為最優(yōu)前綴碼（3）求哈夫曼編碼的算法①思想方法：給定字符集的哈夫曼樹生成后，求哈夫曼編碼的具體實(shí)現(xiàn)過程是：依次以葉子T[i](0≤i≤n-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)樽址笮閚，故變長編碼的長度不會(huì)超過n，加上一個(gè)結(jié)束符'\0'，bits的大小應(yīng)為n+1。②字符集編碼的存儲(chǔ)結(jié)構(gòu)及其算法描述

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

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

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

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

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

假設(shè)通信電文使用的字符集為{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)造的哈夫曼樹中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(quán)值且按左分支為0和右分支為1的規(guī)則，分別寫出與每個(gè)字符對(duì)應(yīng)的編碼。做一做【課堂實(shí)踐4-9】做引例分析與實(shí)現(xiàn)

1．引例分析

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

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

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

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

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

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

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