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

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

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

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

4、二叉樹是兩種特殊形態(tài)的二叉樹。 滿二叉樹是指深度為k，且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。 完全二叉樹是指深度為k，有n個(gè)結(jié)點(diǎn)，當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)。 圖7.2.4 非完全二叉樹 圖7.2.3 完全二叉樹 圖7.2.2 滿二叉樹§7.2.2 二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有 個(gè)結(jié)點(diǎn)（i1）。性質(zhì)2：深度為k的二叉樹至多有 個(gè)結(jié)點(diǎn)（k1）。性質(zhì)3：對(duì)任意一棵二叉樹，如果度為2的結(jié)點(diǎn)數(shù)為n2，則其葉子結(jié)點(diǎn)數(shù)為 。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（每層從左到右），則對(duì)任一結(jié)

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

6、2k-1 證明：深度為K的二叉樹的最大結(jié)點(diǎn)數(shù)為 n2+1證明：設(shè)葉子結(jié)點(diǎn)數(shù)為n0，度為1的結(jié)點(diǎn)數(shù)為n1，則該數(shù)結(jié)點(diǎn)的總數(shù)為： n n0 + n1 + n2 （1）樹中結(jié)點(diǎn)之間的連線稱為分支。樹中除根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，設(shè)B為二叉樹分支的總數(shù)，則有： B n 1 另一方面，這些分支是由度為1或2的結(jié)點(diǎn)射出的，所以： B n1 + 2n2 所以： n 1 n1 + 2n2 （2） 由式（1）和（2）得： n0 + n1 + n2 1 n1 + 2n2 即： n0 n2 + 1 證明：假設(shè)深度為K的完全二叉樹的結(jié)點(diǎn)數(shù)為n，則根據(jù)性質(zhì)2和完全二叉樹定義有： 或 于是 k是整數(shù) 證明略

7、§7.2.2 二叉樹的存儲(chǔ)結(jié)構(gòu)1順序存儲(chǔ)結(jié)構(gòu) 圖7.2.5 將二叉樹的所有結(jié)點(diǎn)按一定的次序，存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。這種結(jié)構(gòu)，較適用于滿二叉樹或近似滿二叉樹。 如圖7.2.5中完全二叉樹的存儲(chǔ)結(jié)構(gòu)如下：ABCDEFGHIJKLM123456789101112131415 圖7.2.6圖7.2.6中的二叉樹的存儲(chǔ)結(jié)構(gòu)如下：ABCDFGIM123456789101112131415可以看出，當(dāng)二叉樹較稀疏時(shí)，采用順序存儲(chǔ)將造成浪費(fèi)。練習(xí)1) 如果完全二叉樹最多有n層，那么存儲(chǔ)該樹的數(shù)組最少設(shè)_個(gè)單元；2) 某結(jié)點(diǎn)存儲(chǔ)于Si，則存在雙親結(jié)點(diǎn)的條件： if _其雙親結(jié)點(diǎn)位于S _ ，其左

8、孩子結(jié)點(diǎn)位于S _ ；2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可以構(gòu)成不同形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由二叉樹的定義可知，二叉樹的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左右子樹的兩個(gè)分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域和左、右指針域，如圖7.2.7。 有時(shí)為了便于找到結(jié)點(diǎn)的雙親，則還可以在結(jié)點(diǎn)的結(jié)構(gòu)中增加一個(gè)指向其雙親結(jié)點(diǎn)的指針域。用這兩種結(jié)點(diǎn)結(jié)構(gòu)所得的二叉樹的存儲(chǔ)結(jié)構(gòu)分別稱為二叉鏈表和三叉鏈表，如圖7.2.8。 Lchild Data Rchild圖7.2.7 ABCDEFG ABCDEFG(a) 二叉鏈表(b) 三叉鏈表圖7.2.8 在具體應(yīng)用中采用什么存儲(chǔ)結(jié)構(gòu)，除根據(jù)二叉樹的形態(tài)之外，還

9、應(yīng)考慮需進(jìn)行何種操作。如找結(jié)點(diǎn)的雙親，在三叉鏈表中容易實(shí)現(xiàn)，而在二叉鏈表中則需從根中指針出發(fā)巡查。§7.3 遍歷二叉樹遍歷二叉樹（traversing binary tree）是指按某種搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，且僅訪問一次。根據(jù)二叉樹的定義知，二叉樹由三個(gè)基本單元組成：根結(jié)點(diǎn)、左子樹和右子樹。因此，若能依次遍歷這三個(gè)部分，則遍歷了整棵二叉樹。假設(shè)以D、L、R分別表示訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹，則可有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。前三種分別稱為先（根）序、中（根）序、后（根）序，后三種稱為逆先序、逆中序、逆后序。通常只使

10、用前三種。先序遍歷二叉樹的操作定義為： 圖7.3.1【例7.3_1】DLR（先序）：ABDICFMGLDR（中序）：DIBAFMCGLRD（后序）：IDBMFGCA（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹；中序遍歷二叉樹的操作定義為： （1）中序遍歷左子樹； （2）訪問根結(jié)點(diǎn)； （3）中序遍歷右子樹；后序遍歷二叉樹的操作定義為： （1）后序遍歷左子樹； （2）后序遍歷右子樹； （3）訪問根結(jié)點(diǎn)；遍歷算法的描述形式隨存儲(chǔ)結(jié)構(gòu)的不同而不同，若定義二叉樹的存儲(chǔ)結(jié)構(gòu)如下： TYPE Pointer = node； node RECORD data ：char； lchild ，rc

11、hild ：pointer； END；先序遍歷二叉樹的遞歸算法如下： procedure preorder（p ：pointer）； beginif p<>nil then beginwrite (p.data)；preorder（p . lchild）；preorder（p . rchild）； end； end； 請(qǐng)完成中序遍歷二叉樹的遞歸算法： procedure inorder（p ：pointer）； begin end； 請(qǐng)完成后序遍歷二叉樹的遞歸算法： procedure postorder（p ：pointer）； begin end； 二叉樹的三種遍歷遞歸算法寫得

12、非常精妙，只要對(duì)它稍加修改（主要在process語句處），就可的各種不同功能、用途的算法。如建立二叉樹、查找結(jié)點(diǎn)、求每個(gè)結(jié)點(diǎn)所處的層次、求二叉樹的高度、結(jié)點(diǎn)個(gè)數(shù)、復(fù)制二叉樹等。§7.4 二叉樹的建立 圖7.4.1二叉樹的建立可分先序、中序、后序三種方法。先序建立二叉樹即輸入結(jié)點(diǎn)數(shù)據(jù)的順序按先序遍歷所得的序列輸入，輸入“*”，表示該子樹為空，如輸入a b c * * d * * e * * ，得到的二叉樹如圖7.4.1。中序、后序類推?！揪毩?xí)】：請(qǐng)將前面遍歷二叉樹的算法稍加改動(dòng)，分別寫出先序、中序、后序建立二叉樹的算法。§7.5 樹的存儲(chǔ)結(jié)構(gòu)【思考】 請(qǐng)先不要看下面內(nèi)容，如果

13、對(duì)一棵樹（不定支數(shù)），你如何設(shè)計(jì)它的存儲(chǔ)結(jié)構(gòu)？一、 多重鏈表表示法每個(gè)結(jié)點(diǎn)的設(shè)m個(gè)指針域指向該結(jié)點(diǎn)的子數(shù)，m為樹的度，結(jié)點(diǎn)結(jié)構(gòu)如下： Data child1 child2 childm 很容易看出，多重鏈表的缺點(diǎn)是，當(dāng)樹中結(jié)點(diǎn)的子樹數(shù)相差較大，許多結(jié)點(diǎn)的度小于m時(shí)，鏈表中有很多空指針域，空間較浪費(fèi)。二、 雙親表示法這種存儲(chǔ)結(jié)構(gòu)利用每個(gè)結(jié)點(diǎn)（除根外）只有唯一的雙親的性質(zhì)，以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在鏈表中的位置。 dataABCDEFGHIparent011223555123456789其存儲(chǔ)結(jié)構(gòu)說明如下：TYPE tnode=recordData：

14、char；Parent：integer； end；VAR tree：array 1.maxnode of tnode； 三、 孩子表示法將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表鏈接起來，樹中n個(gè)結(jié)點(diǎn)就有n條孩子鏈（葉子的孩子鏈為空），而將這n條鏈的頭結(jié)點(diǎn)按順序排列起來，組成一個(gè)線性表。ABCDEFGHI23456789123456789（a）孩子鏈表24785369123456789ABCDEFGHI011223555（b）帶雙親的孩子鏈表圖7.5.1如圖7.5.1（a）孩子鏈表的存儲(chǔ)結(jié)構(gòu)說明如下： TYPE tlink=tnode; Tnode=RECORD Data : char; Next : tl

15、ink; End; Var tree: array 1.n of tlink;這種方法較適用于涉及孩子的操作，但不適用于涉及雙親的操作。我們可以采取改進(jìn)的存儲(chǔ)方法，在每一個(gè)孩子鏈的頭結(jié)點(diǎn)中加一個(gè)域，存儲(chǔ)其雙親結(jié)點(diǎn)的位置，如圖7.5.1(b)。四、 孩子兄弟表示法又稱二叉鏈表表示法，鏈表中結(jié)點(diǎn)的兩個(gè)鏈接域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。237896145結(jié)點(diǎn)結(jié)構(gòu)說明如下：TYPE tlink=tnode; Tnode=RECORD Data : char; fch , nsib :tlink; END§7.6 森林與二叉樹的轉(zhuǎn)換 從上面樹的孩子兄弟表示法可以看出，二叉樹

16、和樹都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個(gè)對(duì)應(yīng)關(guān)系。也就是說，給定一棵樹，可以找出唯一的一棵二叉樹與之對(duì)應(yīng)。將一般樹或森林轉(zhuǎn)換成二叉樹表示，其目的是為了節(jié)省存儲(chǔ)空間。§7.6.1 樹或森林轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹的步驟如下： 將結(jié)點(diǎn)的所有兄弟連接在一起； 將所有不是連到最左子結(jié)點(diǎn)的子結(jié)點(diǎn)鏈表刪除； 將結(jié)點(diǎn)的右子樹向順時(shí)針方向旋轉(zhuǎn)45°。 （a） - （b）【圖7.6.1】 （c）（d） （e）樹轉(zhuǎn)換成二叉樹的步驟如下： 將森林中的各棵樹分別轉(zhuǎn)換成二叉樹； 將所有轉(zhuǎn)換而成的二叉樹的樹根相連；第二棵樹作為第一棵樹的右子樹，第三棵樹作為第二棵

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

18、連接； 斷開連接后的結(jié)點(diǎn)與左子樹為兄弟，將其與雙親相連。如果Broot , LB , RB是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林FT1 , T2 , , Tm。（1）若B為空，則F為空；（2）若B非空，則F中第一棵樹T1的根 root(T1) 即為二叉樹B的根root； T1中根結(jié)點(diǎn)的子樹森林是由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 樹和森林的遍歷一、 先序遍歷森林若森林非空

19、，可按以下規(guī)則遍歷： （1）訪問第一棵樹的根； （2）先序遍歷第一棵樹的子樹；對(duì)上圖森林進(jìn)行遍歷先序遍歷序列：A B C D E F G H I J中序遍歷序列：B C D A F E H J I G （3）先序遍歷余下的其它樹；二、 中序遍歷森林若森林非空，可按以下規(guī)則遍歷： （1）中序遍歷森林中第一棵樹的根結(jié)點(diǎn) （2）訪問第一棵樹的根結(jié)點(diǎn)； （3）中序遍歷余下的其它樹；§7.8 哈夫曼樹及其應(yīng)用§7.8.1 擴(kuò)充二叉樹· 幾個(gè)基本概念 從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑；路徑上的分支數(shù)目稱為路徑長(zhǎng)度；樹的路徑長(zhǎng)度是從樹根到每一結(jié)點(diǎn)的路

20、徑長(zhǎng)度之和；· 擴(kuò)充二叉樹是指將原二叉樹中每個(gè)凡缺少左、右孩子的結(jié)點(diǎn)，均擴(kuò)充為帶左、右兩個(gè)孩子。例如圖7.8.1（a）中的二叉樹變?yōu)閿U(kuò)充二叉樹后如圖7.8.1（b）所示，圖中圓形結(jié)點(diǎn)是原來的，稱為內(nèi)部結(jié)點(diǎn)；方形結(jié)點(diǎn)是擴(kuò)充結(jié)點(diǎn)，又稱外部結(jié)點(diǎn)。（a）二叉樹（b） 擴(kuò)充二叉樹【圖7.8.1】?jī)?nèi)路徑長(zhǎng)度 I (從根到每一內(nèi)結(jié)點(diǎn)的路徑長(zhǎng)度之和): I = 1 + 2 + 1 + 2 + 3 + 2 = 11 外路徑長(zhǎng)度 E (從根到每一外結(jié)點(diǎn)的路徑長(zhǎng)度之和): E = 3 + 3 + 2 + 3 + 4 + 4 + 3 + 3 = 25 · 一些規(guī)律：(1) 若擴(kuò)充二叉樹有n個(gè)內(nèi)部結(jié)

21、點(diǎn)，則有 個(gè)外部結(jié)點(diǎn)； (2) 擴(kuò)充二叉樹的內(nèi)、外路徑長(zhǎng)度I、E的關(guān)系是 E 。答案： （1）n+1 (2) E=I+2n證明：(1). n + 1 證明： 根據(jù)二叉樹性質(zhì)3（對(duì)任意一棵二叉樹，如果度為2的結(jié)點(diǎn)數(shù)為n2，則其葉子結(jié)點(diǎn)數(shù)為n2+1）擴(kuò)充二叉樹的內(nèi)部結(jié)點(diǎn)的度都是2，有n個(gè)內(nèi)部結(jié)點(diǎn)，則外部結(jié)點(diǎn)（即葉子）有n+1個(gè)。證畢。(2). E = I + 2n 證明： （數(shù)學(xué)歸納法） 當(dāng)n=1時(shí)，由于只有一個(gè)內(nèi)部結(jié)點(diǎn)， I0，E2， 所以 EI2n 假設(shè)對(duì)于所有的k，都有 E k = I k + 2 k當(dāng) k+1時(shí)，即添加一個(gè)內(nèi)部結(jié)點(diǎn)，設(shè)其路徑長(zhǎng)度為L(zhǎng)， 則 I k+1 I k + L E k

22、+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)二叉樹（哈夫曼樹）對(duì)擴(kuò)充二叉樹的外部結(jié)點(diǎn)均賦于一個(gè)權(quán)值，則稱帶權(quán)二叉樹。其帶權(quán)路徑長(zhǎng)度是每個(gè)外部結(jié)點(diǎn)到根的路徑長(zhǎng)度Lj 乘以權(quán)值Wj 的積之和。（a） （b） （c）圖7. 8. 2115424521111542W1L1W2L2WmLm 如圖7.8.2中的幾種擴(kuò)充二叉樹的帶權(quán)路徑長(zhǎng)度分別為： WEa 11×25×24×22×2 44 WE

23、b 4×25×311×32×1 58WEc 11×15×24×32×3 39規(guī)律：權(quán)值越大的外部結(jié)點(diǎn)離根結(jié)點(diǎn)越近，其帶權(quán)路徑長(zhǎng)度最短，如（c）中的樹。假設(shè)有n個(gè)權(quán)值W1 ,W2 , Wn， 試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)（外部結(jié)點(diǎn)）帶權(quán)Wi ，則其中帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹?！纠繉W(xué)生百分制成績(jī)用A、B、C、D、E等級(jí)表示，成績(jī)分別規(guī)律如下：分?jǐn)?shù)05960697079808990100等級(jí)EDCBA比例數(shù)0.050.150.400.300.10a<60a<70a

24、<80a<90ABCDEyyyynnnna<80a<70a<90a<60ABCDEyyyynnnn(a)(b)若有10000個(gè)數(shù)據(jù)，按圖(a)的判定過程進(jìn)行轉(zhuǎn)換，則有80%的數(shù)據(jù)至少要進(jìn)行三次比較，完成10000個(gè)數(shù)據(jù)轉(zhuǎn)換的比較次數(shù)為：10000×(1×5% + 2×15% + 3×40% + 4×(30%+10%) = 31500 次按圖(b)的判定過程，完成10000個(gè)數(shù)據(jù)轉(zhuǎn)換的比較次數(shù)為：10000×( 2×(10% + 30% + 40%) + 3×(5% + 15%)

25、= 22000 次顯然，后者的判定過程效率比前者高。圖(b)所示的判定過程是最優(yōu)的，該二叉樹稱為最優(yōu)二叉樹，又稱哈夫曼樹。§7.8.3 哈夫曼樹的構(gòu)造如何構(gòu)造哈夫曼樹呢？哈夫曼（Huffman）最早給出一個(gè)帶有一般規(guī)律的算法（哈夫曼算法）：(1) 根據(jù)給定的n個(gè)權(quán)值 W1 ,W2 , Wn 構(gòu)成 n 棵二叉樹的集合 FT1 ,T2 ,Tn，其中每棵二叉樹Ti 中只有一個(gè)帶權(quán)為Wi 的根結(jié)點(diǎn)，其左右子樹均空。(2) 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)的權(quán)值之和。(3) 在F中刪除這兩棵樹，同時(shí)將新樹加入F中。(4)

26、 重復(fù)(2)和(3)，直到F中只含一棵樹為止。哈夫曼樹的構(gòu)建過程如圖7.8.3所示。【圖7.8.3】8534（a）653476（b）68（c）347656118834715（d）5611561183471526（d）§7.8.4 哈夫曼樹的應(yīng)用1 用于判斷過程利用哈夫曼樹可以構(gòu)成最佳判斷過程。例如，要對(duì)一批正整數(shù)按下表要求分類：數(shù)a出現(xiàn)概率屬第幾類a202/18120<a504/18250<a1005/183100<a7/184a20a50a100a屬第三類a屬第四類a屬第二類a屬第一類a20a50a100a屬第四類a屬第三類a屬第二類a屬第一類（a）（b）【圖7.

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

28、為：0、00、1、01，則上述電文可改為：“000011010”，長(zhǎng)度僅為9。但這樣的電文無法翻譯，例如前四個(gè)字符“0000”就可有多種譯法，或是“AAAA”，或是“ABA”，也可以是“BB”。因此，要設(shè)計(jì)長(zhǎng)短不等的編碼，則要求任一字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼稱為前綴編碼?？梢岳枚鏄鋪碓O(shè)計(jì)二進(jìn)制的前綴編碼。約定二叉樹的左分支表示字符0，右分支表示字符1，樹葉代表給定的字符，則可以從樹根到葉子的路徑上分支字符組成的字符串作為該葉子字符的編碼。如圖7.8.5所示。而哈夫曼樹可使電文總長(zhǎng)最短。以字符出現(xiàn)的頻率為權(quán)，設(shè)計(jì)一棵哈夫曼樹，由此得到的二進(jìn)制前綴編碼稱為哈夫曼編碼。下面討

29、論具體的做法：設(shè)需要編碼的字符集Dd1,d2,dn，設(shè)Wi 為di 在文本中出現(xiàn)的次數(shù)，則權(quán)值WW1,W2,Wn。將權(quán)值作為外部結(jié)點(diǎn)構(gòu)造成哈夫曼樹，取左支為0，右支為1，從根至葉路徑上0、1組成的二進(jìn)制串作為該葉結(jié)點(diǎn)字符的編碼。將編碼存入D對(duì)應(yīng)的編碼表。發(fā)送：根據(jù)字符從編碼表中找到相應(yīng)的編碼發(fā)送出去，如發(fā)送abcbc字符串，發(fā)出的二進(jìn)制串是111101100110。接收譯碼：對(duì)收到的二進(jìn)制串，按順序從哈夫曼樹根走到葉結(jié)點(diǎn)，0走左支，1走右支，一直走到葉結(jié)點(diǎn)，就可譯出一個(gè)字符。下次再?gòu)母_始對(duì)后續(xù)二進(jìn)制位串進(jìn)行譯碼，譯出下一個(gè)字符，如此下去，直至譯完為止?！揪毩?xí)】已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)

30、八種字符 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è)計(jì)哈夫曼編碼，進(jìn)行報(bào)文編碼和譯碼。 輸入格式： 輸入文件名：hfm.in 第1行為字母B或Y，B代表進(jìn)行報(bào)文編碼，Y代表進(jìn)行譯碼。第2行為整數(shù)n，代表報(bào)文/電文行數(shù)第3到n3行為報(bào)文/電文內(nèi)容 輸出格式：輸出文件名：hfm.out 第1行為報(bào)文/電文行數(shù)n 第2到n+2行為報(bào)文/電文內(nèi)容 （若非報(bào)文字符則該行輸出error） 輸入輸出舉例：輸入：B2debbdhd輸出：21111110101011110101111輸入：Y1000101111輸出：1fhd

31、【綜合練習(xí)】1、 中序遍歷問題描述按先序輸入一棵二叉樹，請(qǐng)輸出其中序遍歷。（樹結(jié)點(diǎn)用不同的小寫字母表示，“*”表示子樹為空）。abcde樣例輸入：abc*d*c*輸出：cbdae2、 求先序排列(NOIP2001普及組)問題描述給出一棵二叉樹的中序和后序排列，求出它的先序排列。（約定樹結(jié)點(diǎn)用不同的大寫字母表示，長(zhǎng)度8）。樣例輸入：BADC BDCA輸出：ABCD3、有根樹的同構(gòu)（GDOI2003 day2-4）4、二叉樹（GDKOI2005 day1-1）§7.9 樹與并查集§7.8.1 引例【例】親戚若某個(gè)家族人員過于龐大，要判斷兩個(gè)是否是親戚，確實(shí)還很不容易，現(xiàn)在給出某

32、個(gè)親戚關(guān)系圖，求任意給出的兩個(gè)人是否具有親戚關(guān)系。規(guī)定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。數(shù)據(jù)輸入：第一行：三個(gè)整數(shù)n,m,p，（n<=5000,m<=5000,p<=5000），分別表示有n個(gè)人，m個(gè)親戚關(guān)系，詢問p對(duì)親戚關(guān)系。以下m行：每行兩個(gè)數(shù)Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有親戚關(guān)系。接下來p行：每行兩個(gè)數(shù)Pi，Pj，詢問Pi和Pj是否具有親戚關(guān)系。數(shù)據(jù)輸出：P行，每行一個(gè)Yes或No。表示第i個(gè)詢問的答案為“具有”或“不具有”親戚關(guān)系。樣例：input.

33、txt6 5 31 21 53 45 21 31 42 35 6output.txtYesYesNo§7.8.2 并查集并查集是一種樹形數(shù)據(jù)結(jié)構(gòu)，用于集合的合并和查找。并查集的主要操作有： 1）判斷兩個(gè)元素是否屬于同一個(gè)集合2）合并兩個(gè)不相交集合3）路徑壓縮7.9.1判斷兩個(gè)元素是否屬于同一個(gè)集合；合并兩個(gè)不相交集用Si.father表示元素i的父親結(jié)點(diǎn)S1.father=1S2.father=1S3.father=1S4.father=3S5.father=3S6.father=5123456由此用某個(gè)元素所在樹的根結(jié)點(diǎn)表示該元素所在的集合。判斷兩個(gè)元素時(shí)候?qū)儆谕粋€(gè)集合的時(shí)候，只

34、需要判斷他們所在樹的根結(jié)點(diǎn)是否一樣即可；也就是說，當(dāng)我們合并兩個(gè)集合的時(shí)候，只需要在兩個(gè)根結(jié)點(diǎn)之間連邊即可7.9.2路徑壓縮如果我們每次判斷兩個(gè)元素是否屬于同一個(gè)集合，都采用尋根判斷的話，當(dāng)樹是鏈的時(shí)候，需要O(N)的時(shí)間，于是可以采用“路徑壓縮”的方法，提高效率。123456123456路徑壓縮是在找完根結(jié)點(diǎn)之后，在遞歸回來的時(shí)候順便把路徑上元素的父親指針都指向根結(jié)點(diǎn)。之后，對(duì)任意兩個(gè)元素是否屬于同一個(gè)集合的判斷，復(fù)雜度則降為O(1)。 參考程序：function getfather(v:integer):integer;beginif (fatherv=0) then getfather:

35、=velse beginfatherv:=getfather(fatherv);getfather:=fatherv;end;end;function judge(x,y:integer):boolean;var fx,fy : integer;beginfx := getfaher(x);fy := gefather(y);If fx=fy then judge := exit(true)else judge := false;fatherfx := fy;合并兩個(gè)集合end;嚴(yán)歌苓說，人之間的關(guān)系不一定從陌生進(jìn)展為熟識(shí)，從熟識(shí)走向陌生，同樣是正常進(jìn)展。人與人之間的緣分，遠(yuǎn)沒有想像中的那么牢固，也許前一秒鐘還牽手一起經(jīng)歷風(fēng)雨，后一秒就說散就散，所以，你要懂得善待和珍惜。人與人相處，講究個(gè)真心，你對(duì)我好，我就對(duì)你好，你給予真情，我還你真意，人心是相互的。兩個(gè)人在一起，總會(huì)有人主動(dòng)，但主動(dòng)久了，就會(huì)累，會(huì)傷心，心傷了就暖不回來了，凡事多站在對(duì)方的角度想一想，多一份忍耐和謙就，就不會(huì)有那么多的怨氣和誤解，也少了一