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

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

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

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

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

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

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

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

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

10、樹；（3）先序遍歷右子樹；中序遍歷二叉樹的操作定義為： （1）中序遍歷左子樹； （2）訪問根結點； （3）中序遍歷右子樹；后序遍歷二叉樹的操作定義為： （1）后序遍歷左子樹； （2）后序遍歷右子樹； （3）訪問根結點；遍歷算法的描述形式隨存儲結構的不同而不同，若定義二叉樹的存儲結構如下： 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語句處），就可的各種不同功能、用途的算法。如建立二叉樹、查找結點、求每個結點所處的層次、求二叉樹的高度、結點個數、復制二叉樹等。§7.4 二叉

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

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

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

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

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

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

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

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

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

21、子）有n+1個。證畢。(2). E = I + 2n 證明： （數學歸納法） 當n=1時，由于只有一個內部結點， I0，E2， 所以 EI2n 假設對于所有的k，都有 E k = I k + 2 k當 k+1時，即添加一個內部結點，設其路徑長度為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 最優二叉樹（哈夫曼樹）對擴充二叉樹的外部結點均賦于一個權值，則稱帶權二叉樹。其帶權路徑長度是每

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

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

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

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

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

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

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

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

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