數(shù)據(jù)結構（Java版）課件 第5章 樹形結構

第5章樹形結構目錄2樹二叉樹哈夫曼樹及哈夫曼編碼樹和森林第一節(jié)第二節(jié)第三節(jié)第四節(jié)第一節(jié)樹樹的基本概念4提出語義網(wǎng)絡是奎廉（J.R.Quillian）1968年在研究人類聯(lián)想記憶時提出的一種心理學模型。他認為記憶是由概念間的聯(lián)系實現(xiàn)的。隨后在他設計的可教式語言理解器（TeachableLanguageComprehendent）中又把它用作為知識表示方法。1972年，西蒙（Simon）在他的自然語言理解系統(tǒng)中也采用了語義網(wǎng)絡知識表示法。1975年,亨德里克（GGHendrix）又對全稱量詞的表示提出了語義網(wǎng)絡分區(qū)技術。目前，語義網(wǎng)絡已經(jīng)成為人工智能中應用較多的一種知識表示方法，尤其是在自然語言處理方面的應用。1.1樹的基本概念5子樹根節(jié)點互不相交樹是數(shù)據(jù)元素之間具有層次關系的非線性結構，是由n個結點構成的有限集合，結點數(shù)為0的樹叫空樹。樹必須滿足以下條件。(1)有且僅有一個被稱為根的結點。(2)其余結點可分為m個互不相交的有限集合，每個集合又構成一棵樹，叫根結點的子樹。與線性結構不同，樹中的數(shù)據(jù)元素具有一對多的邏輯關系，除根結點以外，每個數(shù)據(jù)元素可以有多個后繼但有且僅有一個前驅，反映了數(shù)據(jù)元素之間的層次關系。樹是遞歸定義的。結點是樹的基本單位，若干個結點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。遞歸1.1樹的基本概念6樹的表示方法有多種，如樹形表示法、文氏圖表示法、凹入圖表示法和廣義表表示法，如左圖。人們在生活中所見的家譜、Windows的文件系統(tǒng)等，雖然表現(xiàn)形式各異，在本質(zhì)上是樹結構。右圖給出了樹的邏輯結構示意圖。1.2樹的術語1.結點

樹的結點就是構成樹的數(shù)據(jù)元素，就是其他數(shù)據(jù)結構中存儲的數(shù)據(jù)項，在樹形表示法中用圓圈表示。2.結點的路徑

結點的路徑是指從根結點到該結點所經(jīng)過結點的順序排列。3.路徑的長度

路徑的長度指的是路徑中包含的分支數(shù)。4.結點的度

結點的度指的是結點擁有的子樹的數(shù)目。5.樹的度

樹的度指的是樹中所有結點的度的最大值。6.葉結點

葉結點是樹中度為0的結點，也叫終端結點。01020304GOAL1.2樹的術語7.分支結點

分支結點是樹中度不為0的結點，也叫非終端結點。8.子結點

子結點是指結點的子樹的根結點，也叫孩子結點。9.父結點

具有子結點的結點叫該子結點的父結點，也叫雙親結點。10.子孫結點

子孫結點是指結點的子樹中的任意結點。11.祖先結點

祖先結點是指結點的路徑中除自身之外的所有結點。12.兄弟結點兄弟結點是指和結點具有同一父結點的結點。01020304GOAL1.2樹的術語13.結點的層次

樹中根結點的層次為0，其他結點的層次是父結點的層次加1。14.樹的深度

樹的深度是指樹中所有結點的層次數(shù)的最大值加1。15.有序樹

有序樹是指樹的各結點的所有子樹具有次序關系，不可以改變位置。16.無序樹

無序樹是指樹的各結點的所有子樹之間無次序關系，可以改變位置。17.森林

森林是由多個互不相交的樹構成的集合。給森林加上一個根結點就變成一棵樹，將樹的根結點刪除就變成森林。01020304GOAL第二節(jié)二叉樹2.1二叉樹的基本概念111.普通二叉樹

二叉樹是特殊的有序樹，它也是由n個結點構成的有限集合。當n=0時稱為空二叉樹。二叉樹的每個結點最多只有兩棵子樹，子樹也為二叉樹，互不相交且有左右之分，分別稱為左二叉樹和右二叉樹。

二叉樹也是遞歸定義的，在樹中定義的度、層次等術語同樣也適用于二叉樹。2.滿二叉樹

滿二叉樹是特殊的二叉樹，它要求除葉結點外的其他結點都具有兩棵子樹，并且所有的葉結點都在同一層上。3.完全二叉樹

完全二叉樹是特殊的二叉樹，若完全二叉樹具有n個結點，它要求n個結點與滿二叉樹的前n個結點具有完全相同的邏輯結構。2.2二叉樹的性質(zhì)性質(zhì)1：二叉樹中第i層的結點數(shù)最多為2i。證明：當i=0時只有一個根結點，成立；假設對所有的k(0≤k<i)成立，即第i-1層上最多有2i-1個結點，那么由于每個結點最多有兩棵子樹，在第i層上結點數(shù)最多為2i-1×2=2i個，得證。性質(zhì)2：深度為h的二叉樹最多有2h-1個結點。證明：由性質(zhì)1得，深度為h的二叉樹的結點個數(shù)最多為20+21+…+2h-1=2h-1，得證。性質(zhì)3：若二叉樹的葉結點的個數(shù)為n，度為2的結點個數(shù)為m，有n=m+1。證明：設二叉樹中度為1的結點個數(shù)為k，二叉樹的結點總數(shù)為s，有s=k+n+m。又因為除根結點外每個結點都有一個進入它的分支，所以s-1=k+2*m。整理后得到n=m+1，得證。0102032.2二叉樹的性質(zhì)0405

2.2二叉樹的性質(zhì)

2.2二叉樹的性質(zhì)2.3二叉樹的存儲結構1）二叉樹的順序存儲結構二叉樹的順序存儲結構是指將二叉樹的各個結點存放在一組地址連續(xù)的存儲單元中，所有結點按結點序號進行順序存儲。因為二叉樹為非線性結構，所以必須先將二叉樹的結點排成線性序列再進行存儲，實際上是對二叉樹先進行一次層次遍歷。二叉樹的各結點間的邏輯關系由結點在線性序列中的相對位置確定?？梢岳?.2節(jié)中的性質(zhì)5將二叉樹的結點排成線性序列，將結點存放在下標為對應編號的數(shù)組元素中。為了存儲非完全二叉樹，需要在樹中添加虛結點使其成為完全二叉樹后再進行存儲，這樣會造成存儲空間的浪費。2.3二叉樹的存儲結構2）二叉樹的鏈式存儲結構

二叉樹的鏈式存儲結構是指將二叉樹的各個結點隨機存放在存儲空間中，二叉樹的各結點間的邏輯關系由指針確定。每個結點至少要有兩條鏈分別連接左、右孩子結點才能表達二叉樹的層次關系。根據(jù)指針域個數(shù)的不同，二叉樹的鏈式存儲結構又分為以下兩種：a.二叉鏈式存儲結構b.三叉鏈式存儲結構2.3二叉樹的存儲結構a.二叉鏈式存儲結構

二叉樹的每個結點設置兩個指針域和一個數(shù)據(jù)域。數(shù)據(jù)域中存放結點的值，指針域中存放左、右孩子結點的存儲地址。

采用二叉鏈表存儲二叉樹，每個結點只存儲了到其孩子結點的單向關系，沒有存儲到其父結點的關系，因此要獲得父結點將花費較多的時間，需要從根結點開始在二叉樹中進行查找，所花費的時間是遍歷部分二叉樹的時間，且與查找結點所處的位置有關。b.三叉鏈式存儲結構

二叉樹的每個結點設置3個指針域和一個數(shù)據(jù)域。數(shù)據(jù)域中存放結點的值，指針域中存放左、右孩子結點和父結點的存儲地址。2.3二叉樹的存儲結構2）二叉樹的鏈式存儲結構下圖所示為二叉鏈式存儲和三叉鏈式存儲的結點結構。

兩種鏈式存儲結構各有優(yōu)缺點，二叉鏈式存儲結構空間利用率高，而三叉鏈式存儲結構既便于查找孩子結點，又便于查找父結點。在實際應用中，二叉鏈式存儲結構更加常用，因此本書中二叉樹的相關算法都是基于二叉鏈式存儲結構設計的。2.3二叉樹的存儲結構3）二叉鏈式存儲結構的結點類的描述2.3二叉樹的存儲結構4）二叉樹類的描述2.4二叉樹的遍歷1）二叉樹的遍歷方法

二叉樹通?？蓜澐譃?個部分，即根結點、左子樹和右子樹。根據(jù)3個部分的訪問順序不同，可將二叉樹的遍歷方法分為以下幾種。a.層次遍歷

自上而下、從左到右依次訪問每層的結點。b.先序遍歷

先訪問根結點，再先序遍歷左子樹，最后先序遍歷右子樹。c.中序遍歷

先中序遍歷左子樹，再訪問根結點，最后中序遍歷右子樹。d.后序遍歷

先后序遍歷左子樹，再后序遍歷右子樹，最后訪問根結點。2.3二叉樹的遍歷2）二叉樹遍歷操作實現(xiàn)的遞歸算法前序遍歷中序遍歷后序遍歷2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法

二叉樹遍歷操作的遞歸算法結構簡潔，易于實現(xiàn)，但是在時間上開銷較大，運行效率較低，為了解決這一問題，可以將遞歸算法轉換為非遞歸算法，轉換方式有以下兩種： a.使用臨時遍歷保存中間結果，用循環(huán)結構代替遞歸過程； b.利用棧保存中間結果。

二叉樹遍歷操作實現(xiàn)的非遞歸算法利用棧結構通過回溯訪問二叉樹的每個結點。2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法A.先序遍歷

先序遍歷從二叉樹的根結點出發(fā)，沿著該結點的左子樹向下搜索，每遇到一個結點先訪問該結點，并將該結點的右子樹入棧。先序遍歷左子樹完成后再從棧頂彈出右子樹的根結點，然后采用相同的方法先序遍歷右子樹，直到二叉樹的所有結點都被訪問。其主要步驟如下:

(1)將二叉樹的根結點入棧。(2)若棧非空，將結點從棧中彈出并訪問。(3)依次訪問當前訪問結點的左孩子結點，并將當前結點的右孩子結點入棧。(4)重復步驟(2)和(3)，直到棧為空。2.3二叉樹的存儲結構3）二叉樹遍歷操作實現(xiàn)的非遞歸算法A.先序遍歷2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法B.中序遍歷

中序遍歷從二叉樹的根結點出發(fā)，沿著該結點的左子樹向下搜索，每遇到一個結點就使其入棧，直到結點的左孩子結點為空。再從棧頂彈出結點并訪問，然后采用相同的方法中序遍歷結點的右子樹，直到二叉樹的所有結點都被訪問。其主要步驟如下:

(1)將二叉樹的根結點入棧。(2)若棧非空，將棧頂結點的左孩子結點依次入棧，直到棧頂結點的左孩子結點為空。(3)將棧頂結點彈出并訪問，并使棧頂結點的右孩子結點入棧。(4)重復步驟(2)和(3)，直到棧為空。2.3二叉樹的存儲結構3）二叉樹遍歷操作實現(xiàn)的非遞歸算法B.中序遍歷2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法C.后序遍歷

后序遍歷從二叉樹的根結點出發(fā)，沿著該結點的左子樹向下搜索，每遇到一個結點需要判斷其是否為第一次經(jīng)過，若是則使結點入棧，后序遍歷該結點的左子樹，完成后再遍歷該結點的右子樹，最后從棧頂彈出該結點并訪問。后序遍歷算法的實現(xiàn)需要引入兩個變量，一個為訪問標記變量flag，用于標記棧頂結點是否被訪問，若flag=true，證明該結點已被訪問，其左子樹和右子樹已經(jīng)遍歷完畢，可繼續(xù)彈出棧頂結點，否則需要先遍歷棧頂結點的右子樹；一個為結點指針t,指向最后一個被訪問的結點，查看棧頂結點的右孩子結點，證明此結點的右子樹已經(jīng)遍歷完畢，棧頂結點可出棧并訪問。其主要步驟如下:

(1)將二叉樹的根結點入棧，t賦值為空。(2)若棧非空，將棧頂結點的左孩子結點依次入棧，直到棧頂結點的左孩子結點為空。(3)若棧非空，查看棧頂結點的右孩子結點，若右孩子結點為空或者與p相等，則彈出棧頂結點并訪問，同時使t指向該結點，并置flag為true；否則將棧頂結點的右孩子結點入棧，并置flag為false。(4)若flag為true，重復步驟(3)；否則重復步驟(2)和(3)，直到棧為空。2.3二叉樹的存儲結構3）二叉樹遍歷操作實現(xiàn)的非遞歸算法C.后序遍歷2.5二叉樹遍歷算法的應用1）二叉樹上的查找算法二叉樹上的查找是在二叉樹中查找值為x的結點，若找到返回該結點，否則返回空值，可以在二叉樹的先序遍歷過程中進行查找，主要步驟如下：

(1)若二叉樹為空，則不存在值為x的結點，返回空值；否則將根結點的值與x進行比較，若相等，返回該結點。(2)若根結點的值與x的值不等，則在左子樹中進行查找，若找到，則返回該結點。(3)若沒有找到，則在根結點的右子樹中進行查找，若找到，返回該結點，否則返回空值。2.5二叉樹遍歷算法的應用1）二叉樹上的查找算法2.5二叉樹遍歷算法的應用2）統(tǒng)計二叉樹的結點個數(shù)的算法二叉樹的結點個數(shù)等于根結點加上左、右子樹的結點的個數(shù)，可以利用二叉樹的先序遍歷序列，引入一個計數(shù)變量count，count的初值為0，每訪問根結點一次就將count的值加1，其主要操作步驟如下： (1)count值初始化為0。 (2)若二叉樹為空，返回count值。 (3)若二叉樹非空，則count值加1，

統(tǒng)計根結點的左子樹的結點個數(shù)，

并將其加到count中；

統(tǒng)計根結點的右子樹的結點個數(shù)，

并將其加到count中。。2.5二叉樹遍歷算法的應用3）求二叉樹的深度二叉樹的深度是所有結點的層次數(shù)的最大值加1，也就是左子樹和右子樹的深度的最大值加1，可以采用后序遍歷的遞歸算法解決此問題，其主要步驟如下： (1)若二叉樹為空，返回0。 (2)若二叉樹非空，

求左子樹的深度、求右子樹的深度。 (3)比較左、右子樹的深度，

取最大值加1即為二叉樹的深度。。2.6二叉樹的建立二叉樹遍歷操作可使非線性結構的樹轉換成線性序列。先序遍歷序列和后序遍歷序列反映父結點和孩子結點間的層次關系，中序遍歷序列反映兄弟結點間的左右次序關系。因為二叉樹是具有層次關系的結點構成的非線性結構，并且每個結點的孩子結點具有左右次序，所以已知一種遍歷序列無法唯一確定一棵二叉樹，只有同時知道中序和先序遍歷序列，或者同時知道中序和后序遍歷序列，才能同時確定結點的層次關系和結點的左右次序，才能唯一確定一棵二叉樹。2.6二叉樹的建立1）由中序和先序遍歷序列建立二叉樹其主要步驟為如下： (1)取先序遍歷序列的第一個結點作為根結點，序列的結點個數(shù)為n。 (2)在中序遍歷序列中尋找根結點，其位置為i，可確定在中序遍歷序列中根結點之前的i個結點構成的序列為根結點的左子樹中序遍歷序列，根結點之后的n-i-1個結點構成的序列為根結點的右子樹中序遍歷序列。 (3)在先序遍歷序列中根結點之后的i個結點構成的序列為根結點的左子樹先序遍歷序列，先序遍歷序列之后的n-i-1個結點構成的序列為根結點的右子樹先序遍歷序列。 (4)對左、右子樹重復步驟(1)、(2)、(3)，確定左、右子樹的根結點和子樹的左右、子樹。 (5)算法遞歸進行即可建立一棵二叉樹。2.6二叉樹的建立1）由中序和先序遍歷序列建立二叉樹假設二叉樹的先序遍歷序列為ABECFG、中序遍歷序列為BEAFCG,由中序和先序遍歷序列建立二叉樹的過程如圖所示：2.6二叉樹的建立1）由中序和先序遍歷序列建立二叉樹2.6二叉樹的建立3901從先序遍歷序列中依次讀取字符2）由標明空子樹的先序遍歷序列創(chuàng)建二叉樹02若字符為#，建立空子樹03建立左子樹04建立右子樹2.6二叉樹的建立2）由標明空子樹的先序遍歷序列創(chuàng)建二叉樹2.6二叉樹的建立41【例5.3】已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構造該二叉樹。解：二叉樹的構造過程如下圖所示。圖(c)即為構造出的二叉樹。第三節(jié)哈夫曼樹及哈夫曼編碼3.哈夫曼樹及哈夫曼編碼目前常用的圖像、音頻、視頻等多媒體信息由于數(shù)據(jù)量大，必須對它們采用數(shù)據(jù)壓縮技術來存儲和傳輸。數(shù)據(jù)壓縮技術通過對數(shù)據(jù)進行重新編碼來壓縮存儲，以便減少數(shù)據(jù)占用的存儲空間，在使用時再進行解壓縮，恢復數(shù)據(jù)的原有特性。其壓縮方法主要有有損壓縮和無損壓縮兩種。有損壓縮是指壓縮過程中可能會丟失數(shù)據(jù)信息，如將BMP位圖壓縮成JPEG格式的圖像，會有精度損失；無損壓縮是指壓縮存儲數(shù)據(jù)的全部信息，確保解壓后的數(shù)據(jù)不丟失。哈夫曼編碼是數(shù)據(jù)壓縮技術中的無損壓縮技術。01020304GOAL3.哈夫曼樹及哈夫曼編碼3.1哈夫曼樹的基本概念3.2哈夫曼樹的構造3.3哈夫曼編碼3.4構造哈夫曼樹和哈夫曼編碼的類的描述3.1哈夫曼樹的基本概念1.結點間的路徑

結點間的路徑是指從一個結點到另一個結點所經(jīng)過的結點序列。從根結點到X結點有且僅

有一條路徑。2.結點的路徑長度

結點的路徑長度是指從根結點到結點的路徑上的邊數(shù)。3.結點的權

結點的權是指人給結點賦予的一個具有某種實際意義的數(shù)值。4.結點的帶權路徑長度

結點的帶權路徑長度是指結點的權值和結點的路徑長度的乘積。5.樹的帶權路徑長度

樹的帶權路徑長度是指樹的葉結點的帶權路徑長度之和。6.最優(yōu)二叉樹

最優(yōu)二叉樹是指給定n個帶有權值的結點作為葉結點構造出的具有最小帶權路徑長度的

二叉樹。最優(yōu)二叉樹也叫哈夫曼樹。3.2哈夫曼樹的構造給定n個葉結點，它們的權值分別是{w1,w2,…,wn}，構造相應的哈夫曼樹的主要步驟如下：

(1)構造由n棵二叉樹組成的森林，每棵二叉樹只有一個根結點，根結點的權值分別為{w1,w2,…,wn}。(2)在森林中選取根結點權值最小和次小的兩棵二叉樹分別作為左子樹和右子樹去構造一棵新的二叉樹，新二叉樹的根結點權值為兩棵子樹的根結點權值之和。(3)將兩棵二叉樹從森林中刪除，并將新的二叉樹添加到森林中。(4)重復步驟(2)和(3)，直到森林中只有一棵二叉樹，此二叉樹即為哈夫曼樹。假設給定的權值為{1，2，3，4，5}，右圖展示了哈夫曼樹的構造過程。3.2哈夫曼樹的構造【例5.4】對于給定的一組權值W＝(5，2，9，11，8，3，7)，試構造相應的哈夫曼樹，并計算它的帶權路徑長度。解：構造的哈夫曼樹如下圖所示：

樹的帶權路徑長度如下：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1203.3哈夫曼編碼01020304GOAL在傳送信息時需要將信息符號轉化成二進制組成的符號串，一般每個字符由一個字節(jié)或兩個字節(jié)表示，即8或16個位數(shù)。為了提高存儲和傳輸效率，需要設計對字符集進行二進制編碼的規(guī)則，使得利用這種規(guī)則對信息進行編碼時編碼位數(shù)最小，即需要傳輸?shù)男畔⒘孔钚?。哈夫曼編碼是一種變長的編碼方案，數(shù)據(jù)的編碼因其使用頻率的不同而長短不一，使用頻率高的數(shù)據(jù)其編碼較短，使用頻率低的數(shù)據(jù)其編碼較長，從而使所有數(shù)據(jù)的編碼總長度最短。各數(shù)據(jù)的使用頻率通過在全部數(shù)據(jù)中統(tǒng)計重復數(shù)據(jù)的出現(xiàn)次數(shù)獲得。又因為在編碼序列中若使用前綴相同的編碼來表示不同的字符會造成二義性，額外的分隔符號會造成傳輸信息量的增加，為了省去不必要的分隔符號，要求每一個字符的編碼都不是另一個字符的前綴，即每個字符的編碼都是前綴編碼。3.3哈夫曼編碼利用哈夫曼樹構造出的哈夫曼編碼是一種最優(yōu)前綴編碼，構造的主要步驟如下：對于具有n個字符的字符集，將字符的頻度作為葉結點的權值，產(chǎn)生n個帶權葉結點。根據(jù)上面章節(jié)中介紹的構造哈夫曼樹的方法利用n個葉結點構造哈夫曼樹。根據(jù)哈夫曼編碼規(guī)則將哈夫曼樹中的每一條左分支標記為0、每一條右分支標記為1，則可得到每個葉結點的哈夫曼編碼。哈夫曼編碼的譯碼過程是構造過程的逆過程，從哈夫曼樹的根結點開始對編碼的每一位進行判別，如果為0進入左子樹，如果為1進入右子樹，直到到達葉結點，即譯出了一個字符。3.4構造哈夫曼樹和哈夫曼編碼的類的描述構造哈夫曼樹需要從子結點到父結點的操作，譯碼時需要從父結點到子結點的操作，所以為了提高算法的效率將哈夫曼樹的結點設計為三叉鏈式存儲結構。一個數(shù)據(jù)域存儲結點的權值，一個標記域flag標記結點是否已經(jīng)加入到哈夫曼樹中，3個指針域分別存儲著指向父結點、孩子結點的地址。結點類的描述如右：3.4構造哈夫曼樹和哈夫曼編碼的類的描述構造哈夫曼樹算法，如下：3.4構造哈夫曼樹和哈夫曼編碼的類的描述【算法】若字符與出現(xiàn)頻率對應關系如：[('a',5),('b',2),('c',9),('d',11),('e',8),('f',3),('g',7)]求哈夫曼編碼。3.4構造哈夫曼樹和哈夫曼編碼的類的描述【算法】若字符與出現(xiàn)頻率對應關系如：[('a',5),('b',2),('c',9),('d',11),('e',8),('f',3),('g',7)]求哈夫曼編碼。輸出如下：第四節(jié)樹和森林4.1樹的存儲結構4.樹和森林4.2樹的遍歷規(guī)則4.1樹的存儲結構一棵樹包含各結點間的層次關系和兄弟關系，兩種關系的存儲結構不同。樹的層次關系必須采用鏈式存儲結構存儲，通過鏈連接父結點和孩子結點。一個結點的多個孩子結點(互稱兄弟結點)之間是線性關系，可以采用順序存儲結構或者鏈