莊朝暉-數據結構參考講義

1、數據結構第6章 樹和二叉樹 - 2第6章 樹和二叉樹 6.1 樹的定義和基本術語 6.2 二叉樹 6.3 遍歷二叉樹和線索二叉樹 6.4 樹和森林 6.5 樹與等價問題 6.6 赫夫曼樹及其應用 6.7 回溯法與樹的遍歷 6.8 樹的計數6.4 樹和森林樹的存儲結構森林和二叉樹的轉換樹和森林的遍歷1、樹的存儲結構樹的雙親表示法樹的孩子表示法樹和森林的孩子兄弟表示法樹的雙親表示法和二叉樹的雙親鏈表相類似，結點中只設一個指向雙親的指針，并對無序樹不需要設子樹位置的標志。所有結點存儲在一個地址連續(xù)的存儲空間中。樹的雙親表示法indexdataParent0A-11B02E13H24I25J26C07

2、D08F79G710K911樹的雙親表示法#define MAX_TREE_SIZE 100typedef struct / 結點結構ElemType data;int parent;/ 雙親位置域 PTNode;typedef struct / 樹結構PTNode nodesMAX_TREE_SIZE;int r, n;/ 根的位置和結點數 PTree;樹的孩子表示法讓每個結點的“子樹根”構成一個線性表，以鏈表作它的存儲結構，令其頭指針和結點的數據元素構成一個結點，并將所有這樣的結點存放在一個地址連續(xù)的存儲空間里，所構成的樹的存儲結構稱為樹的孩子鏈表。當然，在需要的情況下，也可以如同雙親鏈表

3、，在結點結構中加上雙親的地址號。樹的孩子表示法J樹的孩子表示法typedef struct CTNode / 孩子結點int child;struct CTNode *next; *ChildPtr;typedef struct ElemType data; / 結點的數據元素ChildPtr firstchild; / 孩子鏈表頭指針 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n, r;/ 結點數和根結點的位置 CTree;樹和森林的孩子兄弟表示法又稱二叉樹表示法，或二叉鏈表表示法。樹中每個結點都設有兩個指針，其一，firstchil

4、d 指向該結點的“第一個”子樹根結點，其二，nextsibling 指向它的下一個兄弟結點。這里的第一個和下一個都沒有邏輯上的含義，只是在構造存儲結構時自然形成的次序。樹和森林的孩子兄弟表示法樹和森林的孩子兄弟表示法對森林來說，可認為各棵樹的根結點之間是一個 “兄弟”關系右圖是上例中的數去掉根之后的森林對應的二叉鏈表樹和森林的孩子兄弟表示法typedef struct CSNodeElemType data;struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;2、森林和二叉樹的轉換由于二叉樹和樹都可用二叉鏈表作為存儲結構，以二叉鏈表

5、作為媒介可導出樹與二叉樹之間的一個對應關系。給定一棵樹（森林），可以找到唯一的一棵二叉樹與之對應，反之亦然。2、森林和二叉樹的轉換設森林* F= T1, T2, , Tn ;其中第一棵樹T1由根結點 ROOT(T1)和子樹森林 t11, t12, , t1m 構成。則可按如下規(guī)則轉換成一棵二叉樹B =( LBT, Node(root), RBT )：若森林 F 為空集，則二叉樹 B 為空樹；否則，由森林中第一棵樹的根結點 ROOT(T1) 復制得二叉樹的根 Node(root)，由森林中第一棵樹的子樹森林 t11, t12, , t1m轉換得到二叉樹中的左子樹LBT，由森林中刪去第一棵樹之后由

6、其余樹構成的森林 T2, , Tn 轉換得到二叉樹中的右子樹RBT。2、森林和二叉樹的轉換反之，對于任意一棵二叉樹B =( LBT, Node(root), RBT )，可按如下規(guī)則轉換得到由 n 棵樹構成的森林 F= T1, T2, , Tn ;其中第一棵樹T1由根結點 ROOT(T1) 和子樹森林 t11, t12, , t1m構成：若二叉樹 B 為空樹, 則與其對應的森林 F 為空集；否則，由二叉樹的根結點 Node(root) 復制得森林中第一棵樹的根結點 ROOT (T1)，由二叉樹中的左子樹 LBT 轉換構造森林中第一棵樹的子樹森林t11, t12, , t1m ，由二叉樹中的右子

7、樹 RBT 轉換構造森林中其余樹構成的森林 T2, , Tn 。3、樹和森林的遍歷兩個樹的遍歷方法：一、先根(次序)遍歷樹 若樹不空，則先訪問根結點，然后依次從左到右先根遍歷根的各棵子樹；二、后根(次序)遍歷樹若樹不空，則先依次從左到右后根遍歷根的各棵子樹，然后訪問根結點；按層次遍歷:若樹不空，則自上而下自左至右訪問樹中每個結點。3、樹和森林的遍歷森林是樹的集合，由此可以對森林中的每一棵樹依次從左到右進行先根遍歷或者后根遍歷。又森林中的（第一棵樹的根）、（第一棵樹的子樹森林）及（其余樹構成的森林），分別對應為（二叉樹的根）、（二叉樹的左子樹）和（二叉樹的右子樹）。由此可如下定義森林的這兩種遍歷

8、。一、先序遍歷森林 -若森林不空，則可依下列次序進行遍歷(1) 訪問森林中第一棵樹的根結點；(2) 先序遍歷第一棵樹中的子樹森林；(3) 先序遍歷除去第一棵樹之后剩余的樹構成的森林。二、中序遍歷森林 -若森林不空，則可依下列次序進行遍歷：(1) 中序遍歷第一棵樹中的子樹森林；(2) 訪問森林中第一棵樹的根結點；(3) 中序遍歷除去第一棵樹之后剩余的樹構成的森林。3、樹和森林的遍歷容易看出，樹的先根遍歷即森林的先序遍歷可對應到二叉樹的先序遍歷，樹的后根遍歷即森林的中序遍歷可對應到二叉樹的中序遍歷。換句話說，若以孩子-兄弟鏈表作樹（或森林）的存儲結構，則樹的先根遍歷（或森林的先序遍歷）的算法和二叉

9、樹的先序遍歷算法類似，而樹的后根遍歷（或森林的中序遍歷）的算法和二叉樹的中序遍歷算法類似。6.5 樹與等價問題離散數學中的概念：集合S上的關系R定義為SxS的一個子集。等價關系是具有自反、傳遞、對稱的關系。若R是S上的等價關系，由R可以產生這個集合S的一個唯一的劃分S1,S2,這些集合互不相交，其并為S，分別屬于不同的等價類。6.5 樹與等價問題確定等價類的問題假設集合S有n個元素，已知m個形如(x,y) (x,y S)的等價偶對確定了等價關系R，求S的劃分。6.5 樹與等價問題確定等價類的算法：令S中每個元素各自形成一個只含單個成員的子集，記作S1,S2,Sn重復讀入m個關系（偶對），對每個

10、讀入的偶對(x,y)，判定x和y所屬的子集，若這兩個子集不相等，則合并它們并取代這兩個子集當所有的m個關系處理完后，剩下的這些非空子集即為S的R等價類。6.5 樹與等價問題劃分等價類需對集合進行的三個基本操作：構造只含一個元素的集合判定某個元素所在的子集合并兩個互不相交的集合約定：利用樹型結構表示集合，每個節(jié)點表示集合的元素根節(jié)點的成員兼作子集的名稱6.5 樹與等價問題集合的表示用樹Ti表示每個子集Si，森林F表示集合S，每個節(jié)點代表每個元素，每棵樹的根節(jié)點同時用來表示子集Si兩種關鍵的基本操作：查找某個元素是否屬于某個集合，合并兩個集合。采用何種樹、森林的存儲方式可以有效地實現這些基本操作？

11、集合的并：將一子樹的根指向另一子樹的根即可是否屬于集合：從該節(jié)點出發(fā)，逐級查找父節(jié)點到根節(jié)點為止。6.5 樹與等價問題typedef PTree MFSet;int find_mfset( MFSet S, int i) /查找i所屬子集if( iS.n) return -1;for( j=i; S.nodesj.parent0; j=S.nodesj.parent);return j;/ find_mfsetStatus merge_mfset( MFSet &s, int i, int j) /集合的并if( iS.n|jS.n) return ERROR;S.nodesi.parent=

12、j;return OK;/ merge_mfsetO( d) d樹的深度O( 1)6.5 樹與等價問題上述實現對于這樣的例子：假設n個集合S1,S2,Sn, 每個子集只有一個元素Si=i，用n棵只有一個根節(jié)點的樹表示，做n-1次并操作后，最后得到的集合的深度為n，加上每次進行查找成員“1”所在子集的操作，全部操作時間是O(n2)。123n12123123n6.5 樹與等價問題Status mix_mfset( MFSet &S, int i, int j)if(iS.n|jS.n) return ERROR;if( S.nodesi.parentS.nodesj.parent)S.nodesj

13、.parent+=S.nodesi.parent;S.nodesi.parent=j;elseS.nodesi.parent+=S.nodesj.parent;S.nodesj.parent=i;return OK;/ mix_mfset改進“并”操作的算法，令成員少的子集樹根節(jié)點指向成員多的子集的根；修改存儲結構令根節(jié)點的parent與存儲子集中所含成員數目的負值。深度不超過 log2n+1 6.5 樹與等價問題一個實例假設集合S=x|1x n是正整數，R是S上的一個等價關系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),求S的等價類12345678

14、n-1-1-1-1-1-1-1-1-112345678n-21-23-25-27-1處理(1,2),(3,4),(5,6),(7,8)之后6.5 樹與等價問題一個實例假設集合S=x|1x n是正整數，R是S上的一個等價關系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),求S的等價類12345678n-4113-4557-1處理(1,3),(5,7)之后12345678n-21-23-25-27-16.5 樹與等價問題一個實例假設集合S=x|1x n是正整數，R是S上的一個等價關系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7

15、),(1,5),求S的等價類12345678n-81131557-1處理(1,5)之后12345678n-4113-4557-16.5 樹與等價問題改進查找子集算法，增加“壓縮路徑”功能int fix_mfset( MFSet &S, int i)if(iS.n) return -1;for(j=i;S.nodesj.parent0;j=S.nodesj.parent);for(k=i;k!=j;k=t)t=S.nodesk.parent;S.nodesk.parent=j;return j;/ fix_mfset經過這些改進后，劃分等價類的時間復雜度為O(n(n)，其中(n)46.6 赫夫曼

16、樹及其應用Huffman（霍夫曼、哈夫曼）樹，又稱最優(yōu)樹，是一類帶權路徑長度最短的樹，有著廣泛的應用。最優(yōu)二叉樹Huffman編碼1、最優(yōu)二叉樹概念結點的路徑長度定義為從根結點到該結點的路徑上分支的數目。樹的路徑長度定義為樹中每個結點的路徑長度之和。結點的帶權路徑長度定義為從樹根到該結點之間的路徑長度與該結點上所帶權值的乘積。樹的帶權路徑長度定義為樹中所有葉子結點的帶權路徑長度之和* WPL(T)= wklk (對所有葉子結點)其中l(wèi)k為帶權wk的葉子結點的帶權路徑長度1、最優(yōu)二叉樹概念在所有含 n 個葉子結點、并帶相同權值(n個確定的數)的 m 叉樹中，必存在一棵其帶權路徑長度取最小值的樹，

17、稱為“最優(yōu)樹”。對于二叉樹而言，稱為最優(yōu)二叉樹。1、最優(yōu)二叉樹右圖中的四棵二叉樹，都有5個葉子結點且?guī)嗤瑱嘀?、5、6、7、9，它們的帶權路徑長度分別為：WPL=7*3+9*3+5*2+6*2+2*2=74 (左上圖)WPL=2*1+6*3+7*4+9*4+5*2=94 (右上圖)WPL=6*2+7*2+5*3+2*3+9*2=65 (左下圖)WPL=2*1+5*3+7*3+9*3+6*3=83 (右下圖)其中以左下圖中二叉樹的帶權路徑長度為最小?？梢则炞C，它恰為最優(yōu)二叉樹，即在所有葉子結點帶權為5、6、2、9、7的二叉樹中，帶權路徑長度的最小值為65。1、最優(yōu)二叉樹一個應用例子：將成績的百

18、分制(a: 0-100)轉換為五級分制(b: ABCDE)。一般算法if( a60)b = E;else if( a70)b = D;else if( a80)b = C;else if( a90)b = B;elseb = A;60E70D80C90BA1、最優(yōu)二叉樹一個應用例子（續(xù)一）：如果成績的分布是這樣的：則平均需要的比較次數為：0.05*1+0.15*2+0.40*3+0.30*4+0.10*4= 3.15次分數0-5960-6970-7980-8990-100比例.05.15.40.30.101、最優(yōu)二叉樹一個應用例子（續(xù)二）：如果程序改一下：if( a80) if( a70)if

19、( a60) b = E;else b = D; else b = C;elseif( a90) b = B;else b = A;則平均需要的比較次數為：0.05*3+0.15*3+0.40*2+0.30*2+0.10*2= 2.2次分數0-5960-6970-7980-8990-100比例.05.15.40.30.1060EDC807090BA1、最優(yōu)二叉樹Huffman樹的構造方法（最優(yōu)二叉樹）：根據給定的 n 個權值 w1, w2, , wn，構造 n 棵二叉樹的集合F = T1, T2, , Tn，其中每棵二叉樹中均只含一個帶權值為 wi 的根結點,其左、右子樹為空樹;在 F 中選取

20、兩棵根結點的權值最小的樹作為左右子樹，構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和；在 F中刪除這兩棵樹，同時將新得到的二叉樹加入 F 中。重復(2)和(3)，直到 F 只含一棵樹為止。這棵樹便是所求的赫夫曼樹。1、最優(yōu)二叉樹Huffman樹的構造實例：權值2、5、6、7、9256725672567131、最優(yōu)二叉樹Huffman樹的構造實例：權值2、5、6、7、92567132567131625671316292、Huffman編碼表示一個消息文本，通常有兩類二進制編碼：一類為等長編碼，這類編碼的二進制串的長度取決于電文中不同的字符個數，假設需傳送的電文中

21、只有四種字符，只需兩位字符的串便可分辨，但如果電文中可能出現26種不同字符，則等長編碼串的長度為5。另一類是不等長編碼，即各個字符的編碼長度不等。2、Huffman編碼不等長編碼的好處是，可以使傳送電文的字符串的總長度盡可能地短。因為通常各個字符在電文中出現的次數是不相同的，若對出現次數較多的字符采用盡可能短的編碼，則傳送電文的總長便可減少。但在實用的不等長編碼中，任意一個字符的編碼都不能是另一個字符的編碼的前綴，這種編碼稱為前綴編碼。2、Huffman編碼可以利用二叉樹來設計二進制的前綴編碼。假設有一棵如右圖所示的二叉樹，其四個葉子結點分別表示A、B、C和D四個字符，且約定左分支表示字符0，

22、右分支表示字符1，則以由從根到葉子的路徑上的分支表示的字符組成的字符串作為該葉子結點字符的編碼。如右圖中A、B、C和D的二進制前綴編碼分別為0、10、110和111。容易證明，如此得到的必為二進制前綴編碼。并且，若以字符出現的次數為權，構造一棵赫夫曼樹，由此得到的二進制前綴編碼便為最優(yōu)前綴編碼(赫夫曼編碼)。即以這組編碼傳送電文可使電文總長最短(對所有其它前綴編碼而言)。A01B01DC01DAABABCBCA編碼 0譯碼DAABABCBCA2、Huffman編碼假設電文總只有5個字符，且在電文中出現的頻率分別為：5/29，6/29，2/29，9/29，7/29。則所構造的最優(yōu)前綴編碼如右圖所

23、示。于是對應的編碼分別為：100, 00, 101, 11, 01The Huffman tree after two passesThe Huffman Algorithm exampleSymbolCountA15B7C6D6E5The final Huffman treeHuffman Code TableA0B100C101D110E111Total number of bits = 87基于Huffman編碼的文件壓縮一般的文件有一個個的字節(jié)組成，每個字節(jié)（8bit，最多有256種，稱為原始符號）可以用Huffman編碼表示（不等長），基于Huffman編碼的文件壓縮可以將每個原始符

24、號賦予不同的Huffman編碼，將原始文件變換到一個新的文件，由于每個Huffman編碼是一段（不等長的）01串，所以新的文件是由01組成的二進制序列，如果將它們8位一組構成字節(jié)重新寫入一個文件，就得到所謂的壓縮文件。還原（譯碼、解壓縮）的過程正好相反基于Huffman編碼的文件壓縮基本的思路和考慮為了建立Huffman樹、得到Huffman編碼，首先需要有原始符號的權值，可以事先統計文件中各原始符號的頻率作為權值。（權值越大，將會給與越短的編碼）有了Huffman樹，就可以得到編碼表，即每個原始字符所對應的編碼（01序列），壓縮的過程就是一次讀入文件中的每個字節(jié)，輸出它對應的編碼即可。解壓縮

25、可以從Huffman樹根開始，依次讀入01序列，一直到葉節(jié)點為止，得到每個對應的原始符號。為了使解壓縮程序得到相同的Huffman樹，無需傳遞（在壓縮文件中保留）整個Huffman樹，只需傳遞各原始符號的頻率（或者只是頻數），然后采用與壓縮算法同樣的建樹函數即可?；贖uffman編碼的文件壓縮Huffman樹的建立節(jié)點表示：typedef struct tree_node unsigned int count; unsigned int saved_count; int child_0; int child_1; NODE;基于Huffman編碼的文件壓縮Huffman樹的建立節(jié)點表示：ty

26、pedef struct tree_node unsigned int count;/ 權值 unsigned int saved_count;/ int child_0;/ 左子節(jié)點 int child_1;/ 右子節(jié)點 NODE;整個Huffman樹可以存放在一個數組 nodes 中，其中前面部分分別代表各個原始符號（最終Huffman樹的葉結點），在統計頻率時建立（壓縮）或從文件中讀?。ń鈮嚎s）。基于Huffman編碼的文件壓縮Huffman樹的建立nodes 513 .count = 0 xffff;for ( next_free = END_OF_STREAM + 1 ; ; next_free+ ) 查找兩個權重最小的自由節(jié)點（如果沒有，結束） 將這兩權重最小的自由節(jié)點合并得到一新的自由節(jié)點next_free-;nodes next_free .saved_count = nodes next_free .count;最后，next_free 為