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

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

樹的結(jié)點(diǎn)就是構(gòu)成樹的數(shù)據(jù)元素，就是其他數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的數(shù)據(jù)項(xiàng)，在樹形表示法中用圓圈表示。2.結(jié)點(diǎn)的路徑

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

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

結(jié)點(diǎn)的度指的是結(jié)點(diǎn)擁有的子樹的數(shù)目。5.樹的度

樹的度指的是樹中所有結(jié)點(diǎn)的度的最大值。6.葉結(jié)點(diǎn)

葉結(jié)點(diǎn)是樹中度為0的結(jié)點(diǎn)，也叫終端結(jié)點(diǎn)。01020304GOAL1.2樹的術(shù)語7.分支結(jié)點(diǎn)

分支結(jié)點(diǎn)是樹中度不為0的結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)。8.子結(jié)點(diǎn)

子結(jié)點(diǎn)是指結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)，也叫孩子結(jié)點(diǎn)。9.父結(jié)點(diǎn)

具有子結(jié)點(diǎn)的結(jié)點(diǎn)叫該子結(jié)點(diǎn)的父結(jié)點(diǎn)，也叫雙親結(jié)點(diǎn)。10.子孫結(jié)點(diǎn)

子孫結(jié)點(diǎn)是指結(jié)點(diǎn)的子樹中的任意結(jié)點(diǎn)。11.祖先結(jié)點(diǎn)

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

樹中根結(jié)點(diǎn)的層次為0，其他結(jié)點(diǎn)的層次是父結(jié)點(diǎn)的層次加1。14.樹的深度

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

有序樹是指樹的各結(jié)點(diǎn)的所有子樹具有次序關(guān)系，不可以改變位置。16.無序樹

無序樹是指樹的各結(jié)點(diǎn)的所有子樹之間無次序關(guān)系，可以改變位置。17.森林

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

二叉樹是特殊的有序樹，它也是由n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合。當(dāng)n=0時(shí)稱為空二叉樹。二叉樹的每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，子樹也為二叉樹，互不相交且有左右之分，分別稱為左二叉樹和右二叉樹。

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

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

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

2.2二叉樹的性質(zhì)

2.2二叉樹的性質(zhì)2.3二叉樹的存儲(chǔ)結(jié)構(gòu)1）二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)是指將二叉樹的各個(gè)結(jié)點(diǎn)存放在一組地址連續(xù)的存儲(chǔ)單元中，所有結(jié)點(diǎn)按結(jié)點(diǎn)序號(hào)進(jìn)行順序存儲(chǔ)。因?yàn)槎鏄錇榉蔷€性結(jié)構(gòu)，所以必須先將二叉樹的結(jié)點(diǎn)排成線性序列再進(jìn)行存儲(chǔ)，實(shí)際上是對(duì)二叉樹先進(jìn)行一次層次遍歷。二叉樹的各結(jié)點(diǎn)間的邏輯關(guān)系由結(jié)點(diǎn)在線性序列中的相對(duì)位置確定?？梢岳?.2節(jié)中的性質(zhì)5將二叉樹的結(jié)點(diǎn)排成線性序列，將結(jié)點(diǎn)存放在下標(biāo)為對(duì)應(yīng)編號(hào)的數(shù)組元素中。為了存儲(chǔ)非完全二叉樹，需要在樹中添加虛結(jié)點(diǎn)使其成為完全二叉樹后再進(jìn)行存儲(chǔ)，這樣會(huì)造成存儲(chǔ)空間的浪費(fèi)。2.3二叉樹的存儲(chǔ)結(jié)構(gòu)2）二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指將二叉樹的各個(gè)結(jié)點(diǎn)隨機(jī)存放在存儲(chǔ)空間中，二叉樹的各結(jié)點(diǎn)間的邏輯關(guān)系由指針確定。每個(gè)結(jié)點(diǎn)至少要有兩條鏈分別連接左、右孩子結(jié)點(diǎn)才能表達(dá)二叉樹的層次關(guān)系。根據(jù)指針域個(gè)數(shù)的不同，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又分為以下兩種：a.二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)b.三叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3二叉樹的存儲(chǔ)結(jié)構(gòu)a.二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

采用二叉鏈表存儲(chǔ)二叉樹，每個(gè)結(jié)點(diǎn)只存儲(chǔ)了到其孩子結(jié)點(diǎn)的單向關(guān)系，沒有存儲(chǔ)到其父結(jié)點(diǎn)的關(guān)系，因此要獲得父結(jié)點(diǎn)將花費(fèi)較多的時(shí)間，需要從根結(jié)點(diǎn)開始在二叉樹中進(jìn)行查找，所花費(fèi)的時(shí)間是遍歷部分二叉樹的時(shí)間，且與查找結(jié)點(diǎn)所處的位置有關(guān)。b.三叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹的每個(gè)結(jié)點(diǎn)設(shè)置3個(gè)指針域和一個(gè)數(shù)據(jù)域。數(shù)據(jù)域中存放結(jié)點(diǎn)的值，指針域中存放左、右孩子結(jié)點(diǎn)和父結(jié)點(diǎn)的存儲(chǔ)地址。2.3二叉樹的存儲(chǔ)結(jié)構(gòu)2）二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下圖所示為二叉鏈?zhǔn)酱鎯?chǔ)和三叉鏈?zhǔn)酱鎯?chǔ)的結(jié)點(diǎn)結(jié)構(gòu)。

兩種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)空間利用率高，而三叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找父結(jié)點(diǎn)。在實(shí)際應(yīng)用中，二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更加常用，因此本書中二叉樹的相關(guān)算法都是基于二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)的。2.3二叉樹的存儲(chǔ)結(jié)構(gòu)3）二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的結(jié)點(diǎn)類的描述2.3二叉樹的存儲(chǔ)結(jié)構(gòu)4）二叉樹類的描述2.4二叉樹的遍歷1）二叉樹的遍歷方法

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

自上而下、從左到右依次訪問每層的結(jié)點(diǎn)。b.先序遍歷

先訪問根結(jié)點(diǎn)，再先序遍歷左子樹，最后先序遍歷右子樹。c.中序遍歷

先中序遍歷左子樹，再訪問根結(jié)點(diǎn)，最后中序遍歷右子樹。d.后序遍歷

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

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

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

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

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

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

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

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

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

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

統(tǒng)計(jì)根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)，

并將其加到count中；

統(tǒng)計(jì)根結(jié)點(diǎn)的右子樹的結(jié)點(diǎn)個(gè)數(shù)，

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

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

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

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

有一條路徑。2.結(jié)點(diǎn)的路徑長度

結(jié)點(diǎn)的路徑長度是指從根結(jié)點(diǎn)到結(jié)點(diǎn)的路徑上的邊數(shù)。3.結(jié)點(diǎn)的權(quán)

結(jié)點(diǎn)的權(quán)是指人給結(jié)點(diǎn)賦予的一個(gè)具有某種實(shí)際意義的數(shù)值。4.結(jié)點(diǎn)的帶權(quán)路徑長度

結(jié)點(diǎn)的帶權(quán)路徑長度是指結(jié)點(diǎn)的權(quán)值和結(jié)點(diǎn)的路徑長度的乘積。5.樹的帶權(quán)路徑長度

樹的帶權(quán)路徑長度是指樹的葉結(jié)點(diǎn)的帶權(quán)路徑長度之和。6.最優(yōu)二叉樹

最優(yōu)二叉樹是指給定n個(gè)帶有權(quán)值的結(jié)點(diǎn)作為葉結(jié)點(diǎn)構(gòu)造出的具有最小帶權(quán)路徑長度的

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

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

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