莊朝暉-數(shù)據(jù)結(jié)構(gòu)參考講義

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

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

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

4、d 指向該結(jié)點(diǎn)的“第一個(gè)”子樹根結(jié)點(diǎn)，其二，nextsibling 指向它的下一個(gè)兄弟結(jié)點(diǎn)。這里的第一個(gè)和下一個(gè)都沒有邏輯上的含義，只是在構(gòu)造存儲(chǔ)結(jié)構(gòu)時(shí)自然形成的次序。樹和森林的孩子兄弟表示法樹和森林的孩子兄弟表示法對(duì)森林來說，可認(rèn)為各棵樹的根結(jié)點(diǎn)之間是一個(gè) “兄弟”關(guān)系右圖是上例中的數(shù)去掉根之后的森林對(duì)應(yīng)的二叉鏈表樹和森林的孩子兄弟表示法typedef struct CSNodeElemType data;struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;2、森林和二叉樹的轉(zhuǎn)換由于二叉樹和樹都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，以二叉鏈表

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

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

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

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

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

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

11、集合的并：將一子樹的根指向另一子樹的根即可是否屬于集合：從該節(jié)點(diǎn)出發(fā)，逐級(jí)查找父節(jié)點(diǎn)到根節(jié)點(diǎn)為止。6.5 樹與等價(jià)問題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 樹與等價(jià)問題上述實(shí)現(xiàn)對(duì)于這樣的例子：假設(shè)n個(gè)集合S1,S2,Sn, 每個(gè)子集只有一個(gè)元素Si=i，用n棵只有一個(gè)根節(jié)點(diǎn)的樹表示，做n-1次并操作后，最后得到的集合的深度為n，加上每次進(jìn)行查找成員“1”所在子集的操作，全部操作時(shí)間是O(n2)。123n12123123n6.5 樹與等價(jià)問題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改進(jìn)“并”操作的算法，令成員少的子集樹根節(jié)點(diǎn)指向成員多的子集的根；修改存儲(chǔ)結(jié)構(gòu)令根節(jié)點(diǎn)的parent與存儲(chǔ)子集中所含成員數(shù)目的負(fù)值。深度不超過 log2n+1 6.5 樹與等價(jià)問題一個(gè)實(shí)例假設(shè)集合S=x|1x n是正整數(shù)，R是S上的一個(gè)等價(jià)關(guān)系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),求S的等價(jià)類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 樹與等價(jià)問題一個(gè)實(shí)例假設(shè)集合S=x|1x n是正整數(shù)，R是S上的一個(gè)等價(jià)關(guān)系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),求S的等價(jià)類12345678n-4113-4557-1處理(1,3),(5,7)之后12345678n-21-23-25-27-16.5 樹與等價(jià)問題一個(gè)實(shí)例假設(shè)集合S=x|1x n是正整數(shù)，R是S上的一個(gè)等價(jià)關(guān)系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7

15、),(1,5),求S的等價(jià)類12345678n-81131557-1處理(1,5)之后12345678n-4113-4557-16.5 樹與等價(jià)問題改進(jìn)查找子集算法，增加“壓縮路徑”功能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經(jīng)過這些改進(jìn)后，劃分等價(jià)類的時(shí)間復(fù)雜度為O(n(n)，其中(n)46.6 赫夫曼

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

17、稱為“最優(yōu)樹”。對(duì)于二叉樹而言，稱為最優(yōu)二叉樹。1、最優(yōu)二叉樹右圖中的四棵二叉樹，都有5個(gè)葉子結(jié)點(diǎn)且?guī)嗤瑱?quán)值2、5、6、7、9，它們的帶權(quán)路徑長度分別為：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 (右下圖)其中以左下圖中二叉樹的帶權(quán)路徑長度為最小?？梢则?yàn)證，它恰為最優(yōu)二叉樹，即在所有葉子結(jié)點(diǎn)帶權(quán)為5、6、2、9、7的二叉樹中，帶權(quán)路徑長度的最小值為65。1、最優(yōu)二叉樹一個(gè)應(yīng)用例子：將成績的百

18、分制(a: 0-100)轉(zhuǎn)換為五級(jí)分制(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)二叉樹一個(gè)應(yīng)用例子（續(xù)一）：如果成績的分布是這樣的：則平均需要的比較次數(shù)為：0.05*1+0.15*2+0.40*3+0.30*4+0.10*4= 3.15次分?jǐn)?shù)0-5960-6970-7980-8990-100比例.05.15.40.30.101、最優(yōu)二叉樹一個(gè)應(yīng)用例子（續(xù)二）：如果程序改一下：if( a80) if( a70)if

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

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

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

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

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

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

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

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