數(shù)據(jù)結構單元4樹與二叉樹課件

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

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

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

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

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

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

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

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

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

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

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

12、明：完全二叉樹的順序存儲結構既簡單又節(jié)省存儲空間；按這種方法存儲的完全二叉樹，向量元素bti的下標i就是對應結點的編號?！臼纠繄D4-7所示的完全二叉樹的順序存儲結構如圖4-8。圖4-8 完全二叉樹BT3的順序存儲BT3ABCDEFGHIJKL12下標01234567891011122一般二叉樹的順序存儲（1）具體方法將一般二叉樹添上一些“虛結點”，使其成為完全二叉樹；為了用結點在向量中的相對位置來表示結點之間的邏輯關系，按完全二叉樹形式給結點編號；將結點按編號存入向量對應分量，其中“虛結點”用表示。（2）二叉樹的順序存儲結構的優(yōu)缺點：優(yōu)點是存儲結構簡單；缺點是可能浪費大量的存儲空間。在最壞的

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

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

15、ode/定義結點結構DataType data；struct node *lchild，*rchild； /左右孩子指針BinTNode； /結點類型typedef BinTNode *BinTree；3二叉樹的鏈式存儲結構二叉鏈表 在一棵二叉樹中，所有類型為BinTNode的結點，再加上一個指向開始結點（即根結點）的BinTree型頭指針（即根指針）root，就構成了二叉樹的鏈式存儲結構，并將其稱為二叉鏈表。說明：一個二叉鏈表由根指針root惟一確定。若二叉樹為空，則root=NULL；若結點的某個孩子不存在，則相應的指針為空。具有n個結點的二叉鏈表中，共有2n個指針域。其中只有n-1個用來

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

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

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

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

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

21、遍歷序列中，根結點左邊的結點在根的左子樹上，根結點右邊的結點在根的右子樹上。2先序序列：先序遍歷二叉樹時，按對結點的訪問次序形成的結點序列稱為先序序列。說明：在先序遍歷序列中，最左邊的結點是根結點。3后序序列：后序遍歷二叉樹時，按對結點的訪問次序形成的結點序列稱為后序序列。說明：在后序遍歷序列中，最右邊的結點是根結點。 【示例】對如圖4-12的二叉樹BT4，求出它的中序遍歷、先序遍歷和后序遍歷序列。 【課堂實踐4-5】 寫出如圖4-15的二叉樹T2的先序遍歷序列、中序遍歷序列和后序遍歷序列。 做一做圖4-15 二叉樹BT5ABCDEGFH4確定二叉樹 已知中序遍歷序列和先序遍歷序列或后序遍歷序

22、列可以確定一棵二叉樹。具體方法：先根據(jù)先序遍歷序列確定該二叉樹的根，再根據(jù)中序遍歷序列確定根的左子樹和右子樹上的結點，而對于左子樹和右子樹可用同樣的方法確定子樹的根和其左、右子樹上的結點，這樣便可確定該二叉樹。【示例】已知一棵二叉樹的中序遍歷序列和先序遍歷序列分別是：BGDAEHCF和ABDGCEHF，畫出這棵二叉樹。 【課堂實踐4-6】 已知二叉樹的先序序列和中序序列分別為ABDEHCFI和DBHEACIF，畫出該二叉樹的二叉鏈表存儲表示，并寫出該二叉樹的后序序列。 做一做一、二叉鏈表的建立1基本思想 基于先序遍歷建立二叉鏈表，即以二叉樹的先序遍歷序列為輸入建立二叉鏈表。注：先序遍歷序列中須

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

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

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

26、數(shù)的和再加1就是該二叉樹的雙孩子結點的個數(shù)。算法步驟：如果二叉樹BT為空，返回0；如果左右子樹至少有一個為空，返回左子樹雙孩子結點數(shù)與右子樹雙孩子結點數(shù)之和；如果左右子樹都不空，返回左子樹雙孩子結點數(shù)與右子樹雙孩子結點數(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計算結點總數(shù)分析： 如果二叉樹BT為空，即BT=NULL，則BT無結點； 如果二叉樹BT不空，則左、右子樹結點的個數(shù)之和加1就是該二叉樹的結點的個數(shù)。算法步驟：如果二叉樹BT為空，返回0；如果二叉樹BT不空，返回左子樹結點數(shù)與右子樹結點數(shù)之和加1。遞歸算法： int NodeCount(BinTNode *BT)if (BT=NULL)return(0);elsereturn(NodeCount (BT-lchild)+ NodeCount (BT-rchild)+1); 【課堂實踐4-7】 用遞歸方法分別求二叉樹的葉子結點數(shù)

28、和單孩子結點個數(shù)。 做一做一、樹、森林到二叉樹的轉(zhuǎn)換1將樹轉(zhuǎn)換為二叉樹轉(zhuǎn)換方法：加線：在所有兄弟結點之間加一連線；去線：對每個結點，除了保留與其長子的連線外，去掉該結點與其它孩子的連線；調(diào)整：按樹的層次進行調(diào)整，將原來的右兄弟變成其右孩子，原來的無兄弟結點變成左孩子。 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)整ABCDEFGHI2將一個森林轉(zhuǎn)換為二叉樹轉(zhuǎn)換方法：樹轉(zhuǎn)換為二叉樹：將

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

30、(d) 第三步 調(diào)整IJKGHABCDEF3二叉樹到樹、森林的轉(zhuǎn)換轉(zhuǎn)換方法： 加線：在左孩子結點的雙親與左孩子結點的右孩子、右孩子的右孩子等等之間加一連線；去線：去掉所有雙親與右孩子之間的連線；調(diào)整：按樹的層次進行調(diào)整，將原來根結點的右孩子、右孩子的右孩子等等變成森林中樹的根，其它結點的右孩子、右孩子的右孩子等等變成兄弟。 【示例】將如圖4-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)整，如圖

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

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

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

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

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

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

37、長度。說明：在結點數(shù)目相同的二叉樹中，完全二叉樹的路徑長度最短。2樹的帶權路徑長度結點的權（Weight）：賦予樹中某結點的一個有某種意義的實數(shù)，稱為該結點的權。結點的帶權路徑長度：結點到樹根之間路徑長度與該結點上權的乘積，稱為結點的帶權路徑長度。樹的帶權路徑長度（Weighted Path Length of Tree）：樹中所有葉結點的帶權路徑長度之和，稱為樹的帶權路徑長度，亦稱為樹的代價。記為：4.7 哈夫曼樹及其應用 ，n表示葉子結點的數(shù)目，wi和li表示葉結點ki的權值和根到ki之間的路徑長度。3哈夫曼樹：在權為wl,w2,wn的n個葉子所構成的所有二叉樹中，帶權路徑長度最?。创鷥r

38、最?。┑亩鏄浞Q為哈夫曼樹或最優(yōu)二叉樹。說明： 葉子上的權值均相同時，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹；哈夫曼樹中，權越大的葉子離根越近；哈夫曼樹的形態(tài)不唯一，但WPL值相同且最小。 【示例】給定5個葉子結點a，b，c， d和e，分別帶權7，6，12，15和10?？蓸嬙斐鲈S多棵二叉樹，如圖4-24所示的是其中兩棵二叉樹。它們的帶權路徑長度分別為：(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最小的二叉樹，它就

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

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

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

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

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

44、和Tp2作為合并對象，這里0p1，p2i-1。將根為Tp1和Tp2的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結點Ti。具體操作：（i）將Tp1和Tp2的parent置為i;（ii）將Ti的lchild和rchild分別置為p1和p2;（iii）新結點Ti的權值置為Tp1和Tp2的權值之和。4哈夫曼樹T算法實現(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;輸入權值函數(shù)void InputWeight

45、(HuffmanTree T)/輸入權值float w;int i;for (i=0; in;i+)printf(n輸入第%d個權值:,i+1);scanf(%f,&w);Ti.weight=w; 選擇兩個權最小的根結點函數(shù)void SelectMin(HuffmanTree T, int i, int *p1,int *p2)/選擇兩個小的結點float min1=999999;/定義并初始化最小權值float min2=999999;/定義并初始化次小權值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ù)void CreateHuffmanTree(HuffmanTree T)/構造哈夫曼樹，Tm-1為其根結點int i,p1,p2;InitHuffmanTree(T); /將T初始化InputWeight(T); /輸入葉子權值至weight域for(i=n;im;i+)/共n-1次合并,新結點存于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ù)壓縮過程稱為編碼。即將文件中的每個字符均轉(zhuǎn)換為一個惟一的二進制位串。 數(shù)據(jù)解壓過程稱為解碼。即將二進制位串轉(zhuǎn)換為對應的字符。2等長、變長編碼方案 給定的字符集C，可能存在多種編碼方案。等長編碼方案 等長編碼方案將給定字符集C中每個字符的碼長定為lg|C|，|C|表示字符集的大小。變長編碼方案 變長編碼方案將頻度高的字符編碼設置較短，將頻度低的字符編碼設置較長。注意：變長編碼可能使解碼產(chǎn)生二義性。原因是某些字符的編碼可能與其他字符的編碼開始部分(稱為前綴)相同。 【示例】設待壓縮

48、的數(shù)據(jù)文件共有100000個字符，這些字符均取自字符集C=a，b，c，d，e，f，等長編碼需要三位二進制數(shù)字來表示六個字符，因此，整個文件的編碼長度為300000位?！臼纠吭O待壓縮的數(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變長編碼0100101

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

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

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

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

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

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

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

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

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

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

59、ffmanEncoding(HuffmanTree T,HuffmanCode H)讀文本文件統(tǒng)計實際不同字符及個數(shù)n1函數(shù)：void ReadFile()引例分析與實現(xiàn) void InitHuffmanTree(HuffmanTree T) /哈夫曼樹T初始化int i;for (i=0; im1; i+)Ti.weight=0;Ti.lchild=-1;Ti.rchild=-1;Ti.parent=-1; void WriteWeight(HuffmanTree T)/寫入權值函數(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)/選擇兩個權最小的根結點函數(shù)int min1=99