高中信息技術(shù)-競賽班數(shù)據(jù)結(jié)構(gòu)專項培訓(xùn)教程-07樹教案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)7 樹7.1 樹的概念【定義】 樹（Tree）是n（n0）個結(jié)點的有限集合T，它滿足如下兩個條件：(1) 有且僅有一個特定的稱為根（Root）的結(jié)點；(2) 其余的結(jié)點可分為m（m0）個互不相交的有限集合，其中每一個集合又都是一顆樹，并稱為根的子樹（Sub Tree）。 eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq

2、 oac(,J) eq oac(,K) eq oac(,L) eq oac(,M)圖7.1.1【基本術(shù)語】k樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。 結(jié)點擁有的子樹數(shù)稱為結(jié)點的度（degree）。如圖7.1，A的度為3，C的度為1，F(xiàn)的度為0。度為0的結(jié)點稱為葉子（leaf）或終端結(jié)點。例如K、L、F、G、M、I、J。度不為0的結(jié)點稱為分支結(jié)點或非終端結(jié)點。除根結(jié)點外，分支結(jié)點也稱為內(nèi)部結(jié)點。樹的度是樹內(nèi)各結(jié)點的度的最大值，如圖7.1中樹的度為3。結(jié)點的子樹的根稱為該結(jié)點的孩子（Child），該結(jié)點稱為孩子的雙親（parent）。如圖7.1.1，B為A的子樹的根，則B是A的孩子，而A則

3、是B的雙親。同一個雙親的孩子之間互稱為兄弟（sibling），例如B、C、D互為兄弟。將這些關(guā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層，則其子樹的根就在x+1層。樹中結(jié)點的最大層次稱為樹的高度或深度（depth）。如圖7.1的樹的深度為4。 eq oac(,A) eq oac(,A) eq oac(,A) eq oac(,B) eq oac(,C) eq oac(

4、,C) eq oac(,B)圖7.1.2 兩棵不同的有序樹 7.森林（forest）是m（m0）棵互不相交的樹的集合。7.2 二叉樹 eq oac(, eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J)圖7.2.1二叉樹（binary tree）是一種樹型結(jié)構(gòu)，它的每個結(jié)點至多只有二棵子樹（即二叉樹中不存在度大于2結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。（如圖7.2.1） 滿二叉樹和完全二叉樹是兩種特殊形態(tài)的二

5、叉樹。 滿二叉樹是指深度為k，且有2k-1個結(jié)點的二叉樹。 完全二叉樹是指深度為k，有n個結(jié)點，當(dāng)且僅當(dāng)每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)時。 eq oac( eq oac(,1) eq oac(,2) eq oac(,3) eq oac(,4) eq oac(,5) eq oac(,6) eq oac(,7) eq oac(,8) eq oac(,9) eq oac(,10) eq oac(,11) eq oac(,12) 圖7.2.4 非完全二叉樹 eq oac(,1) eq oac(,2) eq oac(,3) eq oac(,4) eq oac(,5) eq

6、oac(,6) eq oac(,7) eq oac(,8) eq oac(,9) eq oac(,10) eq oac(,11) eq oac(,12) 圖7.2.3 完全二叉樹 eq oac(,1) eq oac(,2) eq oac(,3) eq oac(,4) eq oac(,5) eq oac(,6) eq oac(,7) eq oac(,8) eq oac(,9) eq oac(,10) eq oac(,11) eq oac(,12) eq oac(,13) eq oac(,14) eq oac(,15)圖7.2.2 滿二叉樹7.2.2 二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有

7、個結(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是二叉樹的根；如果i1，則其雙親結(jié)點是i div 2 如果2*in，則結(jié)點i無左孩子（結(jié)點i為葉子結(jié)點）；否則其左孩子為2*i 如果2*i+1n，則結(jié)點i無右孩子，否則其右孩子為2*i+1 參考答案及證明： 2i-1證明：利用歸納法 當(dāng)i=1時，只有一個根結(jié)點，顯然，2i-1=20=1 正確；

8、假設(shè)對所有的j，1ji，命題成立，即第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ù)結(jié)點的總數(shù)為： n n0 + n1 + n2 （1）樹中結(jié)點之間的連線稱為分支。樹中除根結(jié)點外，其余每個結(jié)點都有一個分支進入，設(shè)B為二叉樹分支的總數(shù)，則有： B n 1 另一方面，這些分支是由度為1或2的結(jié)點射出的，所以： B n1 + 2n2 所以： n 1

9、n1 + 2n2 （2） 由式（1）和（2）得： n0 + n1 + n2 1 n1 + 2n2 即： n0 n2 + 1 證明：假設(shè)深度為K的完全二叉樹的結(jié)點數(shù)為n，則根據(jù)性質(zhì)2和完全二叉樹定義有： 或 于是 k是整數(shù) 證明略7.2.2 二叉樹的存儲結(jié)構(gòu)1順序存儲結(jié)構(gòu) eq oac( eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J) eq oac(,K) eq oac(,L) eq oac(,M)圖7.2.5 如圖7.2.5

10、中完全二叉樹的存儲結(jié)構(gòu)如下：ABCDEFGHIJKLM123456789101112131415 eq oac(, eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,F) eq oac(,G) eq oac(,I) eq oac(,M)圖7.2.6ABCDFGIM123456789101112131415可以看出，當(dāng)二叉樹較稀疏時，采用順序存儲將造成浪費。練習(xí)如果完全二叉樹最多有n層，那么存儲該樹的數(shù)組最少設(shè)_個單元；某結(jié)點存儲于Si，則存在雙親結(jié)點的條件： if _其雙親結(jié)點位于S _ ，其左孩子結(jié)點位于S _ ；2鏈式存儲結(jié)構(gòu) 設(shè)計不同

11、的結(jié)點結(jié)構(gòu)可以構(gòu)成不同形式的鏈式存儲結(jié)構(gòu)。由二叉樹的定義可知，二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左右子樹的兩個分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點至少包含三個域：數(shù)據(jù)域和左、右指針域，如圖7.2.7。 有時為了便于找到結(jié)點的雙親，則還可以在結(jié)點的結(jié)構(gòu)中增加一個指向其雙親結(jié)點的指針域。用這兩種結(jié)點結(jié)構(gòu)所得的二叉樹的存儲結(jié)構(gòu)分別稱為二叉鏈表和三叉鏈表，如圖7.2.8。 Lchild Data Rchild Lchild Data Rchild圖7.2.7 AABCDEFG eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac

12、(,F) eq oac(,G)ABCDEFG(a) 二叉鏈表(b) 三叉鏈表圖7.2.8 在具體應(yīng)用中采用什么存儲結(jié)構(gòu)，除根據(jù)二叉樹的形態(tài)之外，還應(yīng)考慮需進行何種操作。如找結(jié)點的雙親，在三叉鏈表中容易實現(xiàn)，而在二叉鏈表中則需從根中指針出發(fā)巡查。7.3 遍歷二叉樹遍歷二叉樹（traversing binary tree）是指按某種搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，且僅訪問一次。根據(jù)二叉樹的定義知，二叉樹由三個基本單元組成：根結(jié)點、左子樹和右子樹。因此，若能依次遍歷這三個部分，則遍歷了整棵二叉樹。假設(shè)以D、L、R分別表示訪問根結(jié)點、遍歷左子樹、遍歷右子樹，則可有DLR、LDR、L

13、RD、DRL、RDL、RLD六種遍歷方案。前三種分別稱為先（根）序、中（根）序、后（根）序，后三種稱為逆先序、逆中序、逆后序。通常只使用前三種。先序遍歷二叉樹的操作定義為： eq oac( eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,F) eq oac(,G) eq oac(,I) eq oac(,M)圖7.3.1【例7.3_1】DLR（先序）：ABDICFMGLDR（中序）：DIBAFMCGLRD（后序）：IDBMFGCA（2）先序遍歷左子樹；（3）先序遍歷右子樹；中序遍歷二叉樹的操作定義為： （1）中序遍歷左子樹； （2）訪問根結(jié)

14、點； （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 pnil then beginwrite (p.data)；preorder（p . lchild）；preorder（p . rchild）；

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

16、ac(,e) eq oac(,c) eq oac(,d)圖7.4.1中序、后序類推。【練習(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 Data child1 child2 childm 很容易看出，多重鏈表的缺點是，當(dāng)樹中結(jié)點的子樹數(shù)相差較大，許多結(jié)點的度小于m時，鏈表中有很多空指針域，空間較浪費。雙親表示法這種存儲結(jié)構(gòu)利用每個結(jié)點（除根外）

17、只有唯一的雙親的性質(zhì)，以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在鏈表中的位置。 eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I)dataABCDEFGHIparent011223555123456789其存儲結(jié)構(gòu)說明如下：TYPE tnode=recordData：char；Parent：integer； end；VAR tree：array 1.maxnode of tnode； 孩子表示法將每個結(jié)點的孩子結(jié)點用單

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

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

20、省存儲空間。7.6.1 樹或森林轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹的步驟如下： 將結(jié)點的所有兄弟連接在一起； 將所有不是連到最左子結(jié)點的子結(jié)點鏈表刪除； 將結(jié)點的右子樹向順時針方向旋轉(zhuǎn)45。 eq oac( eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J) （a） eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H

21、)- eq oac(,I)- eq oac(,J) （b）【圖7.6.1】 eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J) eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J) （c）（d） eq oac(,A) eq oac(,B) eq oac(,E) eq

22、 oac(,C) eq oac(,F) eq oac(,G) eq oac(,D) eq oac(,H) eq oac(,I) eq oac(,J)（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)； B的左子樹LB是第一棵樹

23、轉(zhuǎn)換而成的二叉樹；B的右子樹RB是從森林FT2 , T3 , , Tm轉(zhuǎn)換而成的二叉樹。 轉(zhuǎn)換所得的二叉樹，左支是孩子，右支是兄弟。7.6.2 二叉樹轉(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中根結(jié)點的子樹森林是由B的左子樹LB轉(zhuǎn)換而成的森

24、林； F中其余的樹FT2 , T3 , , Tm 是由B的右子樹RB轉(zhuǎn)換而成的森林?！揪毩?xí)】將下列的樹或森林轉(zhuǎn)換成二叉樹 eq oac( eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac( eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,H) eq oac(,F) eq oac(,G) eq oac(,I) eq oac(,J) eq oac(,K) eq

25、oac(,L) eq oac(,M)【練習(xí)】將下列的二叉樹轉(zhuǎn)換成樹或森林 eq oac(, eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac( eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac( eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(

26、,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J) eq oac(,K) eq oac(,L) eq oac(,M) eq oac(,N) eq oac(,O) eq oac(,G) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J) eq oac(,A) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F)先序遍歷森林若森林非空，可按以下規(guī)則遍歷： （1）訪問第一棵樹的根； （2）先序遍歷第一棵樹的子樹；對上圖森林進行遍歷先序遍歷序列：

27、對上圖森林進行遍歷先序遍歷序列：A B C D E F G H I J中序遍歷序列：B C D A F E H J I G中序遍歷森林若森林非空，可按以下規(guī)則遍歷： （1）中序遍歷森林中第一棵樹的根結(jié)點 （2）訪問第一棵樹的根結(jié)點； （3）中序遍歷余下的其它樹；7.8 哈夫曼樹及其應(yīng)用7.8.1 擴充二叉樹 幾個基本概念 從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑；路徑上的分支數(shù)目稱為路徑長度；樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和； 擴充二叉樹是指將原二叉樹中每個凡缺少左、右孩子的結(jié)點，均擴充為帶左、右兩個孩子。例如圖7.8.1（a）中的二叉樹變?yōu)閿U充二叉樹后如圖7.

28、8.1（b）所示，圖中圓形結(jié)點是原來的，稱為內(nèi)部結(jié)點；方形結(jié)點是擴充結(jié)點，又稱外部結(jié)點。（a）二叉樹（a）二叉樹（b） 擴充二叉樹【圖7.8.1】內(nèi)路徑長度 I (從根到每一內(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ù)二

29、叉樹性質(zhì)3（對任意一棵二叉樹，如果度為2的結(jié)點數(shù)為n2，則其葉子結(jié)點數(shù)為n2+1）擴充二叉樹的內(nèi)部結(jié)點的度都是2，有n個內(nèi)部結(jié)點，則外部結(jié)點（即葉子）有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 +

30、 2 ( k+ 1) 證畢。7.8.2對擴充二叉樹的外部結(jié)點均賦于一個權(quán)值，則稱帶權(quán)二叉樹。其帶權(quán)路徑長度是每個外部結(jié)點到根的路徑長度Lj 乘以權(quán)值Wj 的積之和。（a） （b） （c）圖7. 8. 2115424521111542W1（a） （b） （c）圖7. 8. 2115424521111542如圖7.8.2中的幾種擴充二叉樹的帶權(quán)路徑長度分別為： WEa 112524222 44 WEb 425311321 58WEc 111524323 39規(guī)律：權(quán)值越大的外部結(jié)點離根結(jié)點越近，其帶權(quán)路徑長度最短，如（c）中的樹。假設(shè)有n個權(quán)值W1 ,W2 , Wn， 試構(gòu)造一棵有n個葉子結(jié)點的二

31、叉樹，每個葉子結(jié)點（外部結(jié)點）帶權(quán)Wi ，則其中帶權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹?！纠繉W(xué)生百分制成績用A、B、C、D、E等級表示，成績分別規(guī)律如下：分數(shù)05960697079808990100等級EDCBA比例數(shù)0.050.150.400.300.10a60a60a70a80a90ABCDEyyyynnnna80a70a90a60ABCDEyyyynnnn(a)(b)若有10000個數(shù)據(jù)，按圖(a)的判定過程進行轉(zhuǎn)換，則有80%的數(shù)據(jù)至少要進行三次比較，完成10000個數(shù)據(jù)轉(zhuǎn)換的比較次數(shù)為：10000(15% + 215% + 340% + 4(30%+10%) = 315

32、00 次按圖(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)造哈夫曼樹呢？哈夫曼（Huffman）最早給出一個帶有一般規(guī)律的算法（哈夫曼算法）：(1) 根據(jù)給定的n個權(quán)值 W1 ,W2 , Wn 構(gòu)成 n 棵二叉樹的集合 FT1 ,T2 ,Tn，其中每棵二叉樹Ti 中只有一個帶權(quán)為Wi 的根結(jié)點，其左右子樹均空。(2) 在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一

33、棵新的二叉樹，且置新樹的根結(jié)點的權(quán)值為其左右子樹根結(jié)點的權(quán)值之和。(3) 在F中刪除這兩棵樹，同時將新樹加入F中。(4) 重復(fù)(2)和(3)，直到F中只含一棵樹為止。哈夫曼樹的構(gòu)建過程如圖7.8.3所示。【圖7.8.3】858534（a）653476（b）68（c）3（c）347656118834715（d）56115561183471526（d）7.8.4 哈夫曼樹的應(yīng)用 用于判斷過程利用哈夫曼樹可以構(gòu)成最佳判斷過程。例如，要對一批正整數(shù)按下表要求分類：數(shù)a出現(xiàn)概率屬第幾類a202/18120a504/18250a1005/183100a7/184aa20a50a100a屬第三類a屬第四類a

34、屬第二類a屬第一類a20a50a100a屬第四類a屬第三類a屬第二類a屬第一類（a）（b）【圖7.8.4】其最佳判斷過程如圖7.8.4（b）所示，這是按哈夫曼樹的原則來組織的判斷過程，其平均執(zhí)行時間最短。而圖7.8.4（a）的判斷平均時間最長。 2 哈夫曼編碼一般通信中傳送字符采用等長的ASCII碼。例如，假設(shè)需要傳送的報文內(nèi)容為“ABACCDA”，它只有四種字符，只需兩個字符的串就可分辯。設(shè)A、B、C、D的編碼分別為：00、01、10、11，則上述報文的電文為“100”，總長14位，對方接收時，可按2位一分進行譯碼。DECAB圖7.8.500001111如果對字符設(shè)計不等長的編碼，且出現(xiàn)頻率

35、高的采用盡可能短的編碼，則可以提高通信速度。例如設(shè)計A、B、C、D的編碼分別為：0、00、1、01，則上述電文可改為：“”，長度僅為9。但這樣的電文無法翻譯，例如前四個字符“DECAB圖7.8.500001111可以利用二叉樹來設(shè)計二進制的前綴編碼。約定二叉樹的左分支表示字符0，右分支表示字符1，樹葉代表給定的字符，則可以從樹根到葉子的路徑上分支字符組成的字符串作為該葉子字符的編碼。如圖7.8.5所示。而哈夫曼樹可使電文總長最短。以字符出現(xiàn)的頻率為權(quán)，設(shè)計一棵哈夫曼樹，由此得到的二進制前綴編碼稱為哈夫曼編碼。下面討論具體的做法：設(shè)需要編碼的字符集Dd1,d2,dn，設(shè)Wi 為di 在文本中出現(xiàn)

36、的次數(shù)，則權(quán)值WW1,W2,Wn。將權(quán)值作為外部結(jié)點構(gòu)造成哈夫曼樹，取左支為0，右支為1，從根至葉路徑上0、1組成的二進制串作為該葉結(jié)點字符的編碼。將編碼存入D對應(yīng)的編碼表。發(fā)送：根據(jù)字符從編碼表中找到相應(yīng)的編碼發(fā)送出去，如發(fā)送abcbc字符串，發(fā)出的二進制串是0。接收譯碼：對收到的二進制串，按順序從哈夫曼樹根走到葉結(jié)點，0走左支，1走右支，一直走到葉結(jié)點，就可譯出一個字符。下次再從根開始對后續(xù)二進制位串進行譯碼，譯出下一個字符，如此下去，直至譯完為止?！揪毩?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.1

37、4，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輸出：211輸入：Y1輸出：1fhd【綜合練習(xí)】中序遍歷問題描述按先序輸入一棵二叉樹，請輸出其中序遍歷。（樹結(jié)點用不同的小寫字母表示，“*”表示子樹為空）。ababcde輸入：abc*d*c*輸出：cbdae求先序排列(NOIP2001普及組)問題描述給出一棵二叉樹的中序和后序排列，求出它的先序排列。（約定樹結(jié)點用不同的大寫字母表示，長度8）。樣例輸入