1、§7 樹§7.1 樹的概念【定義】 樹（Tree）是n（n>0）個結(jié)點的有限集合T，它滿足如下兩個條件：(1) 有且僅有一個特定的稱為根（Root）的結(jié)點；(2) 其余的結(jié)點可分為m（m0）個互不相交的有限集合，其中每一個集合又都是一顆樹，并稱為根的子樹（Sub Tree）。 圖【基本術(shù)語】k1. 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。 結(jié)點擁有的子樹數(shù)稱為結(jié)點的度（degree）。如圖7.1，A的度為3，C的度為1，F(xiàn)的度為0。2. 度為0的結(jié)點稱為葉子（leaf）或終端結(jié)點。例如K、L、F、G、M、I、J。度不為0的結(jié)點稱為分支結(jié)點或非終端結(jié)點。除根結(jié)點

2、外，分支結(jié)點也稱為內(nèi)部結(jié)點。3. 樹的度是樹內(nèi)各結(jié)點的度的最大值，如圖7.1中樹的度為3。4. 結(jié)點的子樹的根稱為該結(jié)點的孩子（Child），該結(jié)點稱為孩子的雙親（parent）。如圖，B為A的子樹的根，則B是A的孩子，而A則是B的雙親。同一個雙親的孩子之間互稱為兄弟（sibling），例如B、C、D互為兄弟。將這些關(guān)系進一步推廣，可認(rèn)為D是M的祖父。結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。例如，M的祖先為A、D、H。反之，結(jié)點的子樹中的任一結(jié)點都稱為該結(jié)點的子孫，如B的為E、F、K、L。5. 結(jié)點的層次（level）是從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點在第x層，則其

3、子樹的根就在x+1層。樹中結(jié)點的最大層次稱為樹的高度或深度（depth）。如圖7.1的樹的深度為4。 圖 兩棵不同的有序樹6. 如果將樹中的結(jié)點的各子樹看成從左到右是有次序的（即不能互換），則稱該樹為有序樹,否則稱為無序樹。如圖。 7.森林（forest）是m（m0）棵互不相交的樹的集合。§7.2 二叉樹 圖§ 二叉樹的定義二叉樹（binary tree）是一種樹型結(jié)構(gòu)，它的每個結(jié)點至多只有二棵子樹（即二叉樹中不存在度大于2結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。（如圖） 滿二叉樹和完全二叉樹是兩種特殊形態(tài)的二叉樹。 滿二叉樹是指深度為k，且有2k-1個結(jié)

4、點的二叉樹。 完全二叉樹是指深度為k，有n個結(jié)點，當(dāng)且僅當(dāng)每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)時。 圖 非完全二叉樹 圖 完全二叉樹 圖 滿二叉樹§ 二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有 個結(jié)點（i1）。性質(zhì)2：深度為k的二叉樹至多有 個結(jié)點（k1）。性質(zhì)3：對任意一棵二叉樹，如果度為2的結(jié)點數(shù)為n2，則其葉子結(jié)點數(shù)為 。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號（每層從左到右），則對任一結(jié)點i （1in），有： 如果i=1，則結(jié)點i是二叉樹的根；如果i>1，則其雙親結(jié)點是i div 2 如果

5、2*i>n，則結(jié)點i無左孩子（結(jié)點i為葉子結(jié)點）；否則其左孩子為2*i 如果2*i+1>n，則結(jié)點i無右孩子，否則其右孩子為2*i+1 參考答案及證明： 2i-1證明：利用歸納法 當(dāng)i=1時，只有一個根結(jié)點，顯然，2i-1=20=1 正確； 假設(shè)對所有的j，1j<i，命題成立，即第j層上至多有2j-1個結(jié)點； 由假設(shè)，第i-1層上至多有2i-1個結(jié)點，由于二叉樹中的每個結(jié)點的度至多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層上最大結(jié)點數(shù)的2倍，即2*2i-2=2i-1 2k-1 證明：深度為K的二叉樹的最大結(jié)點數(shù)為 n2+1證明：設(shè)葉子結(jié)點數(shù)為n0，度為1的結(jié)點數(shù)為n1，則該數(shù)

6、結(jié)點的總數(shù)為： n n0 + n1 + n2 （1）樹中結(jié)點之間的連線稱為分支。樹中除根結(jié)點外，其余每個結(jié)點都有一個分支進入，設(shè)B為二叉樹分支的總數(shù)，則有： B n 1 另一方面，這些分支是由度為1或2的結(jié)點射出的，所以： B n1 + 2n2 所以： n 1 n1 + 2n2 （2） 由式（1）和（2）得： n0 + n1 + n2 1 n1 + 2n2 即： n0 n2 + 1 證明：假設(shè)深度為K的完全二叉樹的結(jié)點數(shù)為n，則根據(jù)性質(zhì)2和完全二叉樹定義有： 或 于是 k是整數(shù) 證明略§ 二叉樹的存儲結(jié)構(gòu)1順序存儲結(jié)構(gòu) 圖 將二叉樹的所有結(jié)點按一定的次序，存儲到一片連續(xù)的存儲單元中。

7、這種結(jié)構(gòu)，較適用于滿二叉樹或近似滿二叉樹。 如圖中完全二叉樹的存儲結(jié)構(gòu)如下：ABCDEFGHIJKLM123456789101112131415 圖圖中的二叉樹的存儲結(jié)構(gòu)如下：ABCDFGIM123456789101112131415可以看出，當(dāng)二叉樹較稀疏時，采用順序存儲將造成浪費。練習(xí)1) 如果完全二叉樹最多有n層，那么存儲該樹的數(shù)組最少設(shè)_個單元；2) 某結(jié)點存儲于Si，則存在雙親結(jié)點的條件： if _其雙親結(jié)點位于S _ ，其左孩子結(jié)點位于S _ ；2鏈?zhǔn)酱鎯Y(jié)構(gòu) 設(shè)計不同的結(jié)點結(jié)構(gòu)可以構(gòu)成不同形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。由二叉樹的定義可知，二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左右子樹的兩個

8、分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點至少包含三個域：數(shù)據(jù)域和左、右指針域，如圖。 有時為了便于找到結(jié)點的雙親，則還可以在結(jié)點的結(jié)構(gòu)中增加一個指向其雙親結(jié)點的指針域。用這兩種結(jié)點結(jié)構(gòu)所得的二叉樹的存儲結(jié)構(gòu)分別稱為二叉鏈表和三叉鏈表，如圖7.2.8。 Lchild Data Rchild圖 ABCDEFG ABCDEFG(a) 二叉鏈表(b) 三叉鏈表圖 在具體應(yīng)用中采用什么存儲結(jié)構(gòu)，除根據(jù)二叉樹的形態(tài)之外，還應(yīng)考慮需進行何種操作。如找結(jié)點的雙親，在三叉鏈表中容易實現(xiàn)，而在二叉鏈表中則需從根中指針出發(fā)巡查。§7.3 遍歷二叉樹遍歷二叉樹（traversing binary tree）是指

9、按某種搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，且僅訪問一次。根據(jù)二叉樹的定義知，二叉樹由三個基本單元組成：根結(jié)點、左子樹和右子樹。因此，若能依次遍歷這三個部分，則遍歷了整棵二叉樹。假設(shè)以D、L、R分別表示訪問根結(jié)點、遍歷左子樹、遍歷右子樹，則可有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。前三種分別稱為先（根）序、中（根）序、后（根）序，后三種稱為逆先序、逆中序、逆后序。通常只使用前三種。先序遍歷二叉樹的操作定義為： 圖【例7.3_1】DLR（先序）：ABDICFMGLDR（中序）：DIBAFMCGLRD（后序）：IDBMFGCA（1）訪問根結(jié)點；（2）先序遍歷左子

10、樹；（3）先序遍歷右子樹；中序遍歷二叉樹的操作定義為： （1）中序遍歷左子樹； （2）訪問根結(jié)點； （3）中序遍歷右子樹；后序遍歷二叉樹的操作定義為： （1）后序遍歷左子樹； （2）后序遍歷右子樹； （3）訪問根結(jié)點；遍歷算法的描述形式隨存儲結(jié)構(gòu)的不同而不同，若定義二叉樹的存儲結(jié)構(gòu)如下： TYPE Pointer = node； node RECORD data ：char； lchild ，rchild ：pointer； END；先序遍歷二叉樹的遞歸算法如下： procedure preorder（p ：pointer）； beginif p<>nil then beginwr

11、ite (p.data)；preorder（p . lchild）；preorder（p . rchild）； end； end； 請完成中序遍歷二叉樹的遞歸算法： procedure inorder（p ：pointer）； begin end； 請完成后序遍歷二叉樹的遞歸算法： procedure postorder（p ：pointer）； begin end； 二叉樹的三種遍歷遞歸算法寫得非常精妙，只要對它稍加修改（主要在process語句處），就可的各種不同功能、用途的算法。如建立二叉樹、查找結(jié)點、求每個結(jié)點所處的層次、求二叉樹的高度、結(jié)點個數(shù)、復(fù)制二叉樹等。§7.4 二叉

12、樹的建立 圖二叉樹的建立可分先序、中序、后序三種方法。先序建立二叉樹即輸入結(jié)點數(shù)據(jù)的順序按先序遍歷所得的序列輸入，輸入“*”，表示該子樹為空，如輸入a b c * * d * * e * * ，得到的二叉樹如圖。中序、后序類推。【練習(xí)】：請將前面遍歷二叉樹的算法稍加改動，分別寫出先序、中序、后序建立二叉樹的算法。§7.5 樹的存儲結(jié)構(gòu)【思考】 請先不要看下面內(nèi)容，如果對一棵樹（不定支數(shù)），你如何設(shè)計它的存儲結(jié)構(gòu)？一、 多重鏈表表示法每個結(jié)點的設(shè)m個指針域指向該結(jié)點的子數(shù)，m為樹的度，結(jié)點結(jié)構(gòu)如下： Data child1 child2 childm 很容易看出，多重鏈表的缺點是，當(dāng)樹

13、中結(jié)點的子樹數(shù)相差較大，許多結(jié)點的度小于m時，鏈表中有很多空指針域，空間較浪費。二、 雙親表示法這種存儲結(jié)構(gòu)利用每個結(jié)點（除根外）只有唯一的雙親的性質(zhì)，以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在鏈表中的位置。 dataABCDEFGHIparent011223555123456789其存儲結(jié)構(gòu)說明如下：TYPE tnode=recordData：char；Parent：integer； end；VAR tree：array 1.maxnode of tnode； 三、 孩子表示法將每個結(jié)點的孩子結(jié)點用單鏈表鏈接起來，樹中n個結(jié)點就有n條孩子鏈（葉子的孩子鏈為空）

14、，而將這n條鏈的頭結(jié)點按順序排列起來，組成一個線性表。ABCDEFGHI23456789123456789（a）孩子鏈表24785369123456789ABCDEFGHI011223555（b）帶雙親的孩子鏈表圖如圖（a）孩子鏈表的存儲結(jié)構(gòu)說明如下： TYPE tlink=tnode; Tnode=RECORD Data : char; Next : tlink; End; Var tree: array 1.n of tlink;這種方法較適用于涉及孩子的操作，但不適用于涉及雙親的操作。我們可以采取改進的存儲方法，在每一個孩子鏈的頭結(jié)點中加一個域，存儲其雙親結(jié)點的位置，如圖(b)。四、 孩

15、子兄弟表示法又稱二叉鏈表表示法，鏈表中結(jié)點的兩個鏈接域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。237896145結(jié)點結(jié)構(gòu)說明如下：TYPE tlink=tnode; Tnode=RECORD Data : char; fch , nsib :tlink; END§7.6 森林與二叉樹的轉(zhuǎn)換 從上面樹的孩子兄弟表示法可以看出，二叉樹和樹都可用二叉鏈表作為存儲結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。也就是說，給定一棵樹，可以找出唯一的一棵二叉樹與之對應(yīng)。將一般樹或森林轉(zhuǎn)換成二叉樹表示，其目的是為了節(jié)省存儲空間。§ 樹或森林轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹

16、的步驟如下： 將結(jié)點的所有兄弟連接在一起； 將所有不是連到最左子結(jié)點的子結(jié)點鏈表刪除； 將結(jié)點的右子樹向順時針方向旋轉(zhuǎn)45°。 （a） - （b）【圖】 （c）（d） （e）樹轉(zhuǎn)換成二叉樹的步驟如下： 將森林中的各棵樹分別轉(zhuǎn)換成二叉樹； 將所有轉(zhuǎn)換而成的二叉樹的樹根相連；第二棵樹作為第一棵樹的右子樹，第三棵樹作為第二棵樹的右子樹，以第一棵樹的樹根為根。算法描述如下:如果 FT1 , T2 , , Tm 是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹 Broot , LB , RB。（1）若F為空，即m0，則B為空樹；（2）若F非空，即m0，則B的根root即為森林中第一棵樹的根root(T1

17、)； B的左子樹LB是第一棵樹轉(zhuǎn)換而成的二叉樹；B的右子樹RB是從森林FT2 , T3 , , Tm轉(zhuǎn)換而成的二叉樹。 轉(zhuǎn)換所得的二叉樹，左支是孩子，右支是兄弟。§ 二叉樹轉(zhuǎn)換成森林或樹二叉樹轉(zhuǎn)換成樹其實是樹轉(zhuǎn)二叉樹的逆過程，步驟如下： 將每個結(jié)點的右子樹向逆時針方向旋轉(zhuǎn)45°。 刪除與左子樹的橫向連接； 斷開連接后的結(jié)點與左子樹為兄弟，將其與雙親相連。如果Broot , LB , RB是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林FT1 , T2 , , Tm。（1）若B為空，則F為空；（2）若B非空，則F中第一棵樹T1的根 root(T1) 即為二叉樹B的根root； T1中根

18、結(jié)點的子樹森林是由B的左子樹LB轉(zhuǎn)換而成的森林； F中其余的樹FT2 , T3 , , Tm 是由B的右子樹RB轉(zhuǎn)換而成的森林。【練習(xí)】將下列的樹或森林轉(zhuǎn)換成二叉樹 （1） （2）【練習(xí)】將下列的二叉樹轉(zhuǎn)換成樹或森林 （1） （3） （2） （4） （5） §7.7 樹和森林的遍歷一、 先序遍歷森林若森林非空，可按以下規(guī)則遍歷： （1）訪問第一棵樹的根； （2）先序遍歷第一棵樹的子樹；對上圖森林進行遍歷先序遍歷序列：A B C D E F G H I J中序遍歷序列：B C D A F E H J I G （3）先序遍歷余下的其它樹；二、 中序遍歷森林若森林非空，可按以下規(guī)則遍歷：

19、（1）中序遍歷森林中第一棵樹的根結(jié)點 （2）訪問第一棵樹的根結(jié)點； （3）中序遍歷余下的其它樹；§7.8 哈夫曼樹及其應(yīng)用§ 擴充二叉樹· 幾個基本概念 從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑；路徑上的分支數(shù)目稱為路徑長度；樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和；· 擴充二叉樹是指將原二叉樹中每個凡缺少左、右孩子的結(jié)點，均擴充為帶左、右兩個孩子。例如圖（a）中的二叉樹變?yōu)閿U充二叉樹后如圖7.8.1（b）所示，圖中圓形結(jié)點是原來的，稱為內(nèi)部結(jié)點；方形結(jié)點是擴充結(jié)點，又稱外部結(jié)點。（a）二叉樹（b） 擴充二叉樹【圖】內(nèi)路徑長度 I

20、 (從根到每一內(nèi)結(jié)點的路徑長度之和): I = 1 + 2 + 1 + 2 + 3 + 2 = 11 外路徑長度 E (從根到每一外結(jié)點的路徑長度之和): E = 3 + 3 + 2 + 3 + 4 + 4 + 3 + 3 = 25 · 一些規(guī)律：(1) 若擴充二叉樹有n個內(nèi)部結(jié)點，則有 個外部結(jié)點； (2) 擴充二叉樹的內(nèi)、外路徑長度I、E的關(guān)系是 E 。答案： （1）n+1 (2) E=I+2n證明：(1). n + 1 證明： 根據(jù)二叉樹性質(zhì)3（對任意一棵二叉樹，如果度為2的結(jié)點數(shù)為n2，則其葉子結(jié)點數(shù)為n2+1）擴充二叉樹的內(nèi)部結(jié)點的度都是2，有n個內(nèi)部結(jié)點，則外部結(jié)點（即葉

21、子）有n+1個。證畢。(2). E = I + 2n 證明： （數(shù)學(xué)歸納法） 當(dāng)n=1時，由于只有一個內(nèi)部結(jié)點， I0，E2， 所以 EI2n 假設(shè)對于所有的k，都有 E k = I k + 2 k當(dāng) k+1時，即添加一個內(nèi)部結(jié)點，設(shè)其路徑長度為L， 則 I k+1 I k + L E k+1 E k L + 2 ( L + 1 ) E k + L + 2 ( I k + 2 k ) + L + 2 I k + L + 2 k + 2 I k+1 + 2 ( k+ 1) 證畢。§7.8.2 最優(yōu)二叉樹（哈夫曼樹）對擴充二叉樹的外部結(jié)點均賦于一個權(quán)值，則稱帶權(quán)二叉樹。其帶權(quán)路徑長度是每

22、個外部結(jié)點到根的路徑長度Lj 乘以權(quán)值Wj 的積之和。（a） （b） （c）圖7. 8. 2115424521111542W1L1W2L2WmLm 如圖中的幾種擴充二叉樹的帶權(quán)路徑長度分別為： WEa 11×25×24×22×2 44 WEb 4×25×311×32×1 58WEc 11×15×24×32×3 39規(guī)律：權(quán)值越大的外部結(jié)點離根結(jié)點越近，其帶權(quán)路徑長度最短，如（c）中的樹。假設(shè)有n個權(quán)值W1 ,W2 , Wn， 試構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子結(jié)點（外

23、部結(jié)點）帶權(quán)Wi ，則其中帶權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。【例】將學(xué)生百分制成績用A、B、C、D、E等級表示，成績分別規(guī)律如下：分?jǐn)?shù)05960697079808990100等級EDCBA比例數(shù)0.050.150.400.300.10a<60a<70a<80a<90ABCDEyyyynnnna<80a<70a<90a<60ABCDEyyyynnnn(a)(b)若有10000個數(shù)據(jù)，按圖(a)的判定過程進行轉(zhuǎn)換，則有80%的數(shù)據(jù)至少要進行三次比較，完成10000個數(shù)據(jù)轉(zhuǎn)換的比較次數(shù)為：10000×(1×5% +

24、2×15% + 3×40% + 4×(30%+10%) = 31500 次按圖(b)的判定過程，完成10000個數(shù)據(jù)轉(zhuǎn)換的比較次數(shù)為：10000×( 2×(10% + 30% + 40%) + 3×(5% + 15%) = 22000 次顯然，后者的判定過程效率比前者高。圖(b)所示的判定過程是最優(yōu)的，該二叉樹稱為最優(yōu)二叉樹，又稱哈夫曼樹。§7.8.3 哈夫曼樹的構(gòu)造如何構(gòu)造哈夫曼樹呢？哈夫曼（Huffman）最早給出一個帶有一般規(guī)律的算法（哈夫曼算法）：(1) 根據(jù)給定的n個權(quán)值 W1 ,W2 , Wn 構(gòu)成 n 棵二叉樹

25、的集合 FT1 ,T2 ,Tn，其中每棵二叉樹Ti 中只有一個帶權(quán)為Wi 的根結(jié)點，其左右子樹均空。(2) 在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新樹的根結(jié)點的權(quán)值為其左右子樹根結(jié)點的權(quán)值之和。(3) 在F中刪除這兩棵樹，同時將新樹加入F中。(4) 重復(fù)(2)和(3)，直到F中只含一棵樹為止。哈夫曼樹的構(gòu)建過程如圖所示。【圖】8534（a）653476（b）68（c）347656118834715（d）5611561183471526（d）§ 哈夫曼樹的應(yīng)用1 用于判斷過程利用哈夫曼樹可以構(gòu)成最佳判斷過程。例如，要對一批正整數(shù)按下表要求分類：數(shù)a出現(xiàn)概

26、率屬第幾類a202/18120<a504/18250<a1005/183100<a7/184a20a50a100a屬第三類a屬第四類a屬第二類a屬第一類a20a50a100a屬第四類a屬第三類a屬第二類a屬第一類（a）（b）【圖】其最佳判斷過程如圖（b）所示，這是按哈夫曼樹的原則來組織的判斷過程，其平均執(zhí)行時間最短。而圖7.8.4（a）的判斷平均時間最長。 2 哈夫曼編碼一般通信中傳送字符采用等長的ASCII碼。例如，假設(shè)需要傳送的報文內(nèi)容為“ABACCDA”，它只有四種字符，只需兩個字符的串就可分辯。設(shè)A、B、C、D的編碼分別為：00、01、10、11，則上述報文的電文為“

27、”，總長14位，對方接收時，可按2位一分進行譯碼。DECAB圖00001111如果對字符設(shè)計不等長的編碼，且出現(xiàn)頻率高的采用盡可能短的編碼，則可以提高通信速度。例如設(shè)計A、B、C、D的編碼分別為：0、00、1、01，則上述電文可改為：“000011010”，長度僅為9。但這樣的電文無法翻譯，例如前四個字符“0000”就可有多種譯法，或是“AAAA”，或是“ABA”，也可以是“BB”。因此，要設(shè)計長短不等的編碼，則要求任一字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為前綴編碼。可以利用二叉樹來設(shè)計二進制的前綴編碼。約定二叉樹的左分支表示字符0，右分支表示字符1，樹葉代表給定的字符，則可以從樹

28、根到葉子的路徑上分支字符組成的字符串作為該葉子字符的編碼。如圖所示。而哈夫曼樹可使電文總長最短。以字符出現(xiàn)的頻率為權(quán)，設(shè)計一棵哈夫曼樹，由此得到的二進制前綴編碼稱為哈夫曼編碼。下面討論具體的做法：設(shè)需要編碼的字符集Dd1,d2,dn，設(shè)Wi 為di 在文本中出現(xiàn)的次數(shù)，則權(quán)值WW1,W2,Wn。將權(quán)值作為外部結(jié)點構(gòu)造成哈夫曼樹，取左支為0，右支為1，從根至葉路徑上0、1組成的二進制串作為該葉結(jié)點字符的編碼。將編碼存入D對應(yīng)的編碼表。接收譯碼：對收到的二進制串，按順序從哈夫曼樹根走到葉結(jié)點，0走左支，1走右支，一直走到葉結(jié)點，就可譯出一個字符。下次再從根開始對后續(xù)二進制位串進行譯碼，譯出下一個字

29、符，如此下去，直至譯完為止。【練習(xí)】已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符 a,b,c,d,e,f,g,h，其頻率分別為：0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計哈夫曼編碼，進行報文編碼和譯碼。 輸入格式： 輸入文件名：hfm.in 第1行為字母B或Y，B代表進行報文編碼，Y代表進行譯碼。第2行為整數(shù)n，代表報文/電文行數(shù)第3到n3行為報文/電文內(nèi)容 輸出格式：輸出文件名：hfm.out 第1行為報文/電文行數(shù)n 第2到n+2行為報文/電文內(nèi)容 （若非報文字符則該行輸出error） 輸入輸出舉例：輸入：B2debbdhd輸出：2111111010

30、輸入：Y1000101111輸出：1fhd【綜合練習(xí)】1、 中序遍歷問題描述按先序輸入一棵二叉樹，請輸出其中序遍歷。（樹結(jié)點用不同的小寫字母表示，“*”表示子樹為空）。abcde樣例輸入：abc*d*c*輸出：cbdae2、 求先序排列(NOIP2001普及組)問題描述給出一棵二叉樹的中序和后序排列，求出它的先序排列。（約定樹結(jié)點用不同的大寫字母表示，長度8）。樣例輸入：BADC BDCA輸出：ABCD3、有根樹的同構(gòu)（GDOI2003 day2-4）4、二叉樹（GDKOI2005 day1-1）§7.9 樹與并查集§ 引例【例】親戚若某個家族人員過于龐大，要判斷兩個是否是親戚，確實還很不容易，現(xiàn)在給出某個親戚關(guān)系圖，求任意給出的兩個人是否具有親戚關(guān)系。規(guī)定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。數(shù)據(jù)輸入：第一行：三個整數(shù)n,m,p，（n<=5