數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)課件章節(jié)5

第5章樹(shù)與二叉樹(shù)5.1樹(shù)5.1.1樹(shù)的定義樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n≥0)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合?？占弦彩菢?shù)，稱為空樹(shù)。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)；沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；每一個(gè)非根結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)。樹(shù)是由根結(jié)點(diǎn)和若干顆子樹(shù)構(gòu)成的。樹(shù)是由一個(gè)集合以及在該集合上定義的一種關(guān)系構(gòu)成的。集合中的元素稱為樹(shù)的結(jié)點(diǎn)，所定義的關(guān)系稱為父子關(guān)系。父子關(guān)系在樹(shù)的結(jié)點(diǎn)之間建立了一個(gè)層次結(jié)構(gòu)。在這種層次結(jié)構(gòu)中有一個(gè)結(jié)點(diǎn)具有特殊的地位，這個(gè)結(jié)點(diǎn)稱為該樹(shù)的根結(jié)點(diǎn)，或稱為樹(shù)根。5.1.2樹(shù)的基本術(shù)語(yǔ)下面根據(jù)下圖來(lái)介紹關(guān)于樹(shù)的基本術(shù)語(yǔ)和概念。孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)。兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)。樹(shù)的度：一棵樹(shù)中，最大的結(jié)點(diǎn)的度稱為樹(shù)的度。結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子結(jié)點(diǎn)為第2層，以此類推。樹(shù)的高度或深度：樹(shù)中結(jié)點(diǎn)的最大層次。堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄弟。結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。子孫：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。有序樹(shù)：如果樹(shù)中各棵子樹(shù)的次序是有先后次序，則稱該樹(shù)為有序樹(shù)。無(wú)序樹(shù)：如果樹(shù)中各棵子樹(shù)的次序沒(méi)有先后次序，則稱該樹(shù)為無(wú)序樹(shù)。森林：由各棵互不相交的樹(shù)的集合稱為森林。路徑和路徑長(zhǎng)度：樹(shù)中兩個(gè)結(jié)點(diǎn)之間的路徑是由這兩個(gè)結(jié)點(diǎn)之間所經(jīng)過(guò)的結(jié)點(diǎn)序列構(gòu)成的，而路徑長(zhǎng)度是路徑上所經(jīng)過(guò)邊的個(gè)數(shù)。5.1.3樹(shù)的種類無(wú)序樹(shù)：樹(shù)中任意結(jié)點(diǎn)的子結(jié)點(diǎn)之間沒(méi)有順序關(guān)系，這種樹(shù)稱為無(wú)序樹(shù),也稱為自由樹(shù)。有序樹(shù)：樹(shù)中任意結(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹(shù)稱為有序樹(shù)。二叉樹(shù)：每個(gè)結(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱為二叉樹(shù)。滿二叉樹(shù)：葉結(jié)點(diǎn)除外的所有結(jié)點(diǎn)均含有兩個(gè)子樹(shù)的樹(shù)被稱為滿二叉樹(shù)。完全二叉樹(shù)：除最后一層外，所有層都是滿結(jié)點(diǎn)，且最后一層缺右邊連續(xù)結(jié)點(diǎn)的二叉樹(shù)稱為完全二叉樹(shù)。哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）：帶權(quán)路徑最短的二叉樹(shù)稱為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)。5.1.4樹(shù)的性質(zhì)樹(shù)具有如下最基本的性質(zhì)：1）樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加上1。2）度為m的樹(shù)中第i層上至多有mi-1個(gè)結(jié)點(diǎn)（i≥1）。3）高度為h的m叉樹(shù)至多有(mh-1)/(m-1)個(gè)結(jié)點(diǎn)。4）具有n個(gè)結(jié)點(diǎn)的m叉樹(shù)的最小高度為?logm(n(m-1)+1)?。5.2二叉樹(shù)5.2.1二叉樹(shù)的定義及特性1．二叉樹(shù)的定義二叉樹(shù)（Binarytree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。二叉樹(shù)特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分，如圖所示。二叉樹(shù)是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根（root）的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，是有序樹(shù)。當(dāng)集合為空時(shí)，稱該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。不能把二叉樹(shù)與度為2的有序樹(shù)等同起來(lái)。它們之間有如下幾個(gè)區(qū)別：①度為2的有序樹(shù)至少有3個(gè)結(jié)點(diǎn)，而二叉樹(shù)可以為空。②度為2的有序樹(shù)的左右次序是相對(duì)另一個(gè)孩子而言的，若某個(gè)結(jié)點(diǎn)只有一個(gè)孩子，則這個(gè)孩子就不需要區(qū)分左右次序；而二叉樹(shù)無(wú)論其孩子數(shù)是否為2，都需要確認(rèn)其左右次序，二叉樹(shù)的結(jié)點(diǎn)次序是確定的。2．幾種特殊二叉樹(shù)二叉樹(shù)還有以下幾種特殊類型：1）滿二叉樹(shù)：如果一棵二叉樹(shù)只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層上，則這棵二叉樹(shù)為滿二叉樹(shù)。一顆高度為h的滿二叉樹(shù)含有2h–1個(gè)結(jié)點(diǎn)，即樹(shù)中的每一層都含有最多的結(jié)點(diǎn)，如圖(a)所示。2）完全二叉樹(shù)：高度為h，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與高度為h的滿二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)，如圖(b)所示。3）二叉排序樹(shù)：左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字；左子樹(shù)和右子樹(shù)又各是一棵二叉排序樹(shù)，如圖所示。4）平衡二叉樹(shù)：根上任一結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度之差不超過(guò)1，如圖所示。3．二叉樹(shù)性質(zhì)性質(zhì)1：二叉樹(shù)的第i層上至多有2i-1（i≥1）個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為h（h≥1）的二叉樹(shù)中至多含有2h-1個(gè)結(jié)點(diǎn)。性質(zhì)3：若在任意一棵二叉樹(shù)中，有n0個(gè)葉子結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則必有n0=n2+1。證明：設(shè)度為0，1和2的結(jié)點(diǎn)個(gè)數(shù)分別為n0，n1和n2，結(jié)點(diǎn)總數(shù)n=n0+n1+n2。在二叉樹(shù)的分支數(shù)中，除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，設(shè)A為分支總數(shù)，則n=A+1。由于這些分支都是由度為1或2的結(jié)點(diǎn)射出的，所有A=n1+2n2。于是可得n0+n1+n2=n1+2n2+1，化簡(jiǎn)后得n0=n2+1。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)高度為?log2(n+1)?或?log2n?+1。性質(zhì)5：若對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)進(jìn)行順序編號(hào)（0≤i＜n），那么，對(duì)于編號(hào)為i（i≥0）的結(jié)點(diǎn)：當(dāng)i=0時(shí)，該結(jié)點(diǎn)為根，它無(wú)雙親結(jié)點(diǎn)。當(dāng)i>0時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為?(i–1)/2?。若2i+1＜n，則有編號(hào)為2i+1的左結(jié)點(diǎn)，否則沒(méi)有左結(jié)點(diǎn)。若2i+2＜n，則有編號(hào)為2i+2的右結(jié)點(diǎn)，否則沒(méi)有右結(jié)點(diǎn)。5.2.2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)一般都采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用鏈表結(jié)點(diǎn)來(lái)存儲(chǔ)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)。在二叉樹(shù)中，結(jié)點(diǎn)結(jié)構(gòu)通常包括若干數(shù)據(jù)域和若干指針域，二叉鏈表至少包含3個(gè)域：數(shù)據(jù)域data，左指針域lchild和右指針域rchild，如圖所示。二叉樹(shù)結(jié)點(diǎn)類的存儲(chǔ)結(jié)構(gòu)描述如下：二叉樹(shù)類的存儲(chǔ)結(jié)構(gòu)描述如下：5.2.3二叉樹(shù)的遍歷遍歷是對(duì)樹(shù)的一種最基本的運(yùn)算，所謂遍歷二叉樹(shù)，就是按一定的規(guī)則和順序走遍二叉樹(shù)的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問(wèn)一次，而且只被訪問(wèn)一次。由于二叉樹(shù)是非線性結(jié)構(gòu)，因此，樹(shù)的遍歷實(shí)質(zhì)上是將二叉樹(shù)的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來(lái)表示。1．先序遍歷先序遍歷（PreOrder）的操作過(guò)程如下：若二叉樹(shù)為空，則什么也不做，否則，

1）訪問(wèn)根結(jié)點(diǎn)；

2）先序遍歷左子樹(shù)；

3）先序遍歷右子樹(shù)。先序遍歷的遞歸算法如下：在圖中所表示的二叉樹(shù)中，先序遍歷所得到的結(jié)點(diǎn)序列為124563。2．中序遍歷中序遍歷（InOrder）的操作過(guò)程如下：若二叉樹(shù)為空，則什么也不做，否則，

1）中序遍歷左子樹(shù)；

2）訪問(wèn)根結(jié)點(diǎn)；3）中序遍歷右子樹(shù)。中序遍歷的遞歸算法如下：在圖中所表示的二叉樹(shù)中，中序遍歷所得到的結(jié)點(diǎn)序列為426513。3．后序遍歷后序遍歷（PostOrder）的操作過(guò)程如下：若二叉樹(shù)為空，則什么也不做，否則，

1）后序遍歷左子樹(shù)；

2）后序遍歷右子樹(shù)；

3）訪問(wèn)根結(jié)點(diǎn)。后序遍歷的遞歸算法如下：在圖中所表示的二叉樹(shù)中，后序遍歷所得到的結(jié)點(diǎn)序列為465231。4．層次遍歷二叉樹(shù)的層次遍歷，按照層次順序?qū)Χ鏄?shù)的各個(gè)結(jié)點(diǎn)進(jìn)行訪問(wèn)，如圖。用一個(gè)隊(duì)列保存被訪問(wèn)的當(dāng)前結(jié)點(diǎn)的左右孩子以實(shí)現(xiàn)層序遍歷。在進(jìn)行層次遍歷的時(shí)候，設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始，首先將根結(jié)點(diǎn)指針入隊(duì)列，然后從隊(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作：1、訪問(wèn)該元素所指向的結(jié)點(diǎn)2、若該元素所指結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)非空，則將該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。此過(guò)程不斷進(jìn)行，當(dāng)隊(duì)列為空時(shí)，二叉樹(shù)的層次遍歷結(jié)束。二叉樹(shù)的層次遍歷算法如下：5．由遍歷序列構(gòu)造二叉樹(shù)由二叉樹(shù)的先序序列和中序序列可以唯一地確定一棵二叉樹(shù)。由二叉樹(shù)的后序序列和中序序列可以唯一地確定一棵二叉樹(shù)。只知道二叉樹(shù)的先序序列和后序序列無(wú)法唯一確定一棵二叉樹(shù)。5.2.4二叉排序樹(shù)（BST）1．二叉排序樹(shù)的定義二叉排序樹(shù)（BinarySortTree），又稱二叉查找樹(shù)（BinarySearchTree），亦稱二叉搜索樹(shù)。是數(shù)據(jù)結(jié)構(gòu)中的一類。在一般情況下，查詢效率比鏈表結(jié)構(gòu)要高。二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；3）左、右子樹(shù)也分別為二叉排序樹(shù)；4）沒(méi)有鍵值相等的結(jié)點(diǎn)。根據(jù)二叉排序樹(shù)的定義，左子樹(shù)結(jié)點(diǎn)值＜根結(jié)點(diǎn)值＜右子樹(shù)結(jié)點(diǎn)值，所以對(duì)二叉排序樹(shù)進(jìn)行中序遍歷會(huì)得到一個(gè)遞增的有序序列。如圖所示，該二叉排序樹(shù)的中序遍歷序列為135679。2．二叉排序樹(shù)的查找二叉排序樹(shù)的查找從根結(jié)點(diǎn)開(kāi)始，沿某個(gè)分支逐層向下比較的過(guò)程。若二叉排序樹(shù)非空，先將給定值與根結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功；若不相等，如果小于根結(jié)點(diǎn)的關(guān)鍵字，則在根結(jié)點(diǎn)的左子樹(shù)上查找，否則在根結(jié)點(diǎn)的右子樹(shù)上查找。二叉排序樹(shù)的查找算法如下：二叉樹(shù)排序樹(shù)的查找效率主要取決于樹(shù)的高度。若二叉排序樹(shù)的左、右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1，則這樣的二叉排序樹(shù)成為平衡二叉樹(shù)，它的平均查找長(zhǎng)度為O(log2n)。若二叉排序樹(shù)是一個(gè)只有右（左）孩子的單支樹(shù)，則其平均查找長(zhǎng)度為O(n)。3．二叉排序樹(shù)的插入二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表。其特點(diǎn)是：樹(shù)的結(jié)構(gòu)通常不是一次生成的，而是在查找過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。插入結(jié)點(diǎn)的過(guò)程如下：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)；判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子；將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空，則首先單獨(dú)生成根結(jié)點(diǎn)。二叉排序樹(shù)的插入操作算法如下：4．二叉排序樹(shù)的構(gòu)造從一棵空數(shù)開(kāi)始，依次輸入元素，把它們插入到二叉排序樹(shù)的合適位置。構(gòu)造二叉排序樹(shù)的算法如下：5.2.5平衡二叉樹(shù)平衡二叉樹(shù)（BalanceBinaryTree），由前蘇聯(lián)的數(shù)學(xué)家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉樹(shù)，根據(jù)科學(xué)家的英文名也稱為AVL樹(shù)。它具有如下幾個(gè)性質(zhì)：1）可以是空樹(shù)。2）假如不是空樹(shù)，任何一個(gè)結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)都是平衡二叉樹(shù)，并且高度之差的絕對(duì)值不超過(guò)1。定義結(jié)點(diǎn)左子樹(shù)和右子樹(shù)的高度差為該結(jié)點(diǎn)的平衡因子，則平衡二叉樹(shù)結(jié)點(diǎn)的平衡因子值只可能為-1、0或1，如圖所示。5.2.6哈夫曼樹(shù)1．哈夫曼樹(shù)的定義給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若該樹(shù)的帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱為哈夫曼樹(shù)(HuffmanTree)。哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近。哈夫曼樹(shù)是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。所謂樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和，記為WPL（WeightedPathLengthofTree）=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個(gè)權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i（i=1,2,...n）。例如右圖的哈夫曼樹(shù)中，該樹(shù)的WPL=8*1+5*2+2*3+3*3=33。同時(shí)該樹(shù)的WPL在所有帶這4個(gè)結(jié)點(diǎn)的二叉樹(shù)中里為最小值。2.哈夫曼樹(shù)的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1、w2、…、wn，則哈夫曼樹(shù)的構(gòu)造規(guī)則為：1）將w1、w2、…、wn看成是有n棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；2）在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；3）從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；4）重復(fù)（2）、（3）步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)，如圖所示。構(gòu)造哈夫曼樹(shù)的算法如下：3．哈夫曼編碼在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進(jìn)制的字符串，用0，1碼的不同排列來(lái)表示字符。例如，需傳送的報(bào)文為“AFTERDATAEARAREARTAREA”，這里用到的字符集為“A，E，R，T，F(xiàn)，D”，各字母出現(xiàn)的次數(shù)為{8，4，5，3，1，1}。現(xiàn)要求為這些字母設(shè)計(jì)編碼。要區(qū)別6個(gè)字母，最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼，固定采用3位二進(jìn)制，可分別用000、001、010、011、100、101對(duì)“A，E，R，T，F(xiàn)，D”進(jìn)行編碼發(fā)送，當(dāng)對(duì)方接收?qǐng)?bào)文時(shí)再按照三位一分進(jìn)行譯碼。顯然編碼的長(zhǎng)度取決報(bào)文中不同字符的個(gè)數(shù)。若報(bào)文中可能出現(xiàn)26個(gè)不同字符，則固定編碼長(zhǎng)度為5。然而，傳送報(bào)文時(shí)總是希望總長(zhǎng)度盡可能短。在實(shí)際應(yīng)用中，各個(gè)字符的出現(xiàn)頻度或使用次數(shù)是不相同的，如A、B、C的使用頻率遠(yuǎn)遠(yuǎn)高于X、Y、Z，自然會(huì)想到設(shè)計(jì)編碼時(shí)，讓使用頻率高的用短碼，使用頻率低的用長(zhǎng)碼，以優(yōu)化整個(gè)報(bào)文編碼。為使不等長(zhǎng)編碼為前綴編碼（即要求一個(gè)字符的編碼不能是另一個(gè)字符編碼的前綴），可用字符集中的每個(gè)字符作為葉子結(jié)點(diǎn)生成一棵編碼二叉樹(shù)，為了獲得傳送報(bào)文的最短長(zhǎng)度，可將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予該結(jié)點(diǎn)上，顯然字使用頻率越小權(quán)值越小，權(quán)值越小葉子就越靠下，于是頻率小編碼長(zhǎng)，頻率高編碼短，這樣就保證了此樹(shù)的最小帶權(quán)路徑長(zhǎng)度效果上就是傳送報(bào)文的最短長(zhǎng)度。因此，求傳送報(bào)文的最短長(zhǎng)度問(wèn)題轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點(diǎn)，由字符出現(xiàn)頻率作為其權(quán)值所產(chǎn)生的哈夫曼樹(shù)的問(wèn)題。利用哈夫曼樹(shù)來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼，既滿足前綴編碼的條件，又保證報(bào)文編碼總長(zhǎng)最短，如圖。5.3樹(shù)與森林5.3.1樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)方式有多種，既能采用順序存儲(chǔ)結(jié)構(gòu)，也能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但無(wú)論采用哪種存儲(chǔ)方式，都必須要滿足能夠唯一地反映樹(shù)中各結(jié)點(diǎn)之間的邏輯關(guān)系，下面介紹3種常用的存儲(chǔ)結(jié)構(gòu)。1．雙親表示法雙親表示法采用順序存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，采用一組連續(xù)空間才存儲(chǔ)每個(gè)結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)變量，該變量值為其雙親結(jié)點(diǎn)在列表中的索引位置，如圖所示。該存儲(chǔ)結(jié)構(gòu)利用了每個(gè)結(jié)點(diǎn)（除根節(jié)點(diǎn)外）只有唯一一個(gè)雙親的性質(zhì)，可以很快得到每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，但求結(jié)點(diǎn)的孩子時(shí)則需要遍歷整個(gè)順序表。2．孩子表示法孩子表示法是將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)都用單鏈表鏈接起來(lái)形成一個(gè)線性結(jié)構(gòu)，此時(shí)n個(gè)結(jié)點(diǎn)就有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表）。使用孩子表示法來(lái)表示圖(a)中的樹(shù)，如圖所示。孩子表示法尋找子女的操作非常直接，但尋找雙親的操作需要遍歷n個(gè)結(jié)點(diǎn)中的孩子鏈表指針域所指向的n個(gè)孩子鏈表。3．孩子兄弟表示法 孩子兄弟表示法又稱二叉樹(shù)表示法，即以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)。孩子兄弟表示法中，每個(gè)結(jié)點(diǎn)包括三個(gè)部分內(nèi)容：結(jié)點(diǎn)值、指向結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)的指針和指向結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)的指針。用孩子兄弟表示法來(lái)表示圖