數(shù)據(jù)結(jié)構(gòu)第六章

1、第六章 二叉樹教學(xué)內(nèi)容：教學(xué)內(nèi)容： 6.1 定義與性質(zhì)定義與性質(zhì) 6.2 存儲(chǔ)實(shí)現(xiàn)基本操作的實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)基本操作的實(shí)現(xiàn) 6.3 二叉樹的遍歷二叉樹的遍歷 6.4 線索二叉樹線索二叉樹 6.5 二叉樹的應(yīng)用二叉樹的應(yīng)用 教學(xué)目的：教學(xué)目的： 深刻理解二叉樹的定義、性質(zhì)及其存儲(chǔ)深刻理解二叉樹的定義、性質(zhì)及其存儲(chǔ)方法；方法； 熟練掌握二叉樹的二叉鏈表存儲(chǔ)方式、熟練掌握二叉樹的二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義；結(jié)點(diǎn)結(jié)構(gòu)和類型定義； 理解并掌握二叉樹的三種遍歷算法；理解并掌握二叉樹的三種遍歷算法； 掌握二叉樹的線索化方法；掌握二叉樹的線索化方法； 靈活運(yùn)用二叉樹的遍歷方法解決相關(guān)的靈活運(yùn)用二叉樹的遍

2、歷方法解決相關(guān)的應(yīng)用問題；應(yīng)用問題； 教學(xué)重點(diǎn)：教學(xué)重點(diǎn)：二叉樹的定義、邏輯特點(diǎn)及性質(zhì)，在二叉樹二叉樹的定義、邏輯特點(diǎn)及性質(zhì)，在二叉樹上定義的基本運(yùn)算；上定義的基本運(yùn)算； 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其類型說明，二叉二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其類型說明，二叉樹的順序存儲(chǔ)結(jié)構(gòu)及其樹的順序存儲(chǔ)結(jié)構(gòu)及其 類型說明；類型說明； 二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式；二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式； 二叉樹的三種遍歷方法及其算法；二叉樹的三種遍歷方法及其算法； 以遍歷為基礎(chǔ)在二叉樹上實(shí)現(xiàn)的幾種運(yùn)算；以遍歷為基礎(chǔ)在二叉樹上實(shí)現(xiàn)的幾種運(yùn)算； 哈夫曼樹和哈夫曼算法；哈夫曼樹和哈夫曼算法；教學(xué)難點(diǎn)：教學(xué)難點(diǎn)：二叉樹的遞歸定義；二叉

3、樹的遞歸定義； 二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式；二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式； 三種遍歷的主要區(qū)別；三種遍歷的主要區(qū)別； 二叉樹上的復(fù)雜運(yùn)算；二叉樹上的復(fù)雜運(yùn)算； 哈夫曼算法及其應(yīng)用；哈夫曼算法及其應(yīng)用；學(xué)時(shí)安排：學(xué)時(shí)安排：10學(xué)時(shí)學(xué)時(shí)6.1 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語定義：定義：樹樹( (Tree)Tree)是是n(n=0)n(n=0)個(gè)結(jié)點(diǎn)的有限集個(gè)結(jié)點(diǎn)的有限集T T，T T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：（1 1）有且僅有一個(gè)特定的稱為根）有且僅有一個(gè)特定的稱為根( (Root)Root)的結(jié)點(diǎn)；的結(jié)點(diǎn)；（2 2）其余的結(jié)點(diǎn)

4、可分為）其余的結(jié)點(diǎn)可分為m(m=0)m(m=0)個(gè)互不相交的子集個(gè)互不相交的子集T T1 1,T,T2 2,T,T3 3T Tm m，其中每個(gè)子集又是一棵樹，并稱其其中每個(gè)子集又是一棵樹，并稱其為子樹為子樹( (Subtree)Subtree)?；拘g(shù)語基本術(shù)語結(jié)點(diǎn)結(jié)點(diǎn): :數(shù)據(jù)元素?cái)?shù)據(jù)元素 + + 若干指向子樹的分支若干指向子樹的分支結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :分支的個(gè)數(shù)分支的個(gè)數(shù)樹的度樹的度: :樹中所有結(jié)點(diǎn)的度的最大值樹中所有結(jié)點(diǎn)的度的最大值葉子葉子結(jié)點(diǎn)（結(jié)點(diǎn)（終端結(jié)點(diǎn)終端結(jié)點(diǎn)）: :度為零的結(jié)點(diǎn)度為零的結(jié)點(diǎn)分支分支結(jié)點(diǎn)結(jié)點(diǎn): :度大于零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)從根到結(jié)點(diǎn)的從根到結(jié)點(diǎn)的路徑路徑：孩

5、子孩子結(jié)點(diǎn)、結(jié)點(diǎn)、雙親雙親結(jié)點(diǎn)、結(jié)點(diǎn)、兄弟兄弟結(jié)點(diǎn)、結(jié)點(diǎn)、祖先祖先結(jié)點(diǎn)、結(jié)點(diǎn)、子孫子孫結(jié)點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :假設(shè)根結(jié)點(diǎn)的層次為假設(shè)根結(jié)點(diǎn)的層次為1,1, 第第l層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹的深度樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次：樹中葉子結(jié)點(diǎn)所在的最大層次森林森林：是：是m（m0）棵互不相交的樹的集合棵互不相交的樹的集合任何一棵非空樹是一個(gè)二元組任何一棵非空樹是一個(gè)二元組Tree = （root，F(xiàn)）其中：其中： root被稱為根結(jié)點(diǎn)，被稱為根結(jié)點(diǎn)，F(xiàn)被稱為子樹森林被稱為子樹森林課堂練習(xí)：課堂練習(xí)：1、假設(shè)在樹中，結(jié)點(diǎn)、假設(shè)在樹中，結(jié)點(diǎn)x是結(jié)點(diǎn)

6、是結(jié)點(diǎn)y的雙親時(shí)，用的雙親時(shí)，用（x,y）來表示邊。已知一棵樹邊的集合為：來表示邊。已知一棵樹邊的集合為：（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用樹形表示法畫出此樹，并回答下列問題：用樹形表示法畫出此樹，并回答下列問題：1) 哪個(gè)是根結(jié)點(diǎn)？哪個(gè)是根結(jié)點(diǎn)？a2) 哪些是葉結(jié)點(diǎn)？哪些是葉結(jié)點(diǎn)？d,m,n,f,j,k,l3) 哪個(gè)是哪個(gè)是g 的雙親？的雙親？c4) 哪些是哪些是g的祖先？的祖先？a,c5) 哪些是哪些是g 的孩子？的孩子？j,k6) 哪些是哪些是e 的子孫？的子孫？m,

7、n,i7) 哪些是哪些是e的兄弟？的兄弟？d哪些是哪些是f 的兄弟？的兄弟？g,h8) 結(jié)點(diǎn)結(jié)點(diǎn)b和和h的層次各是多少？的層次各是多少？2,39) 樹的深度是多少？樹的深度是多少？510)以結(jié)點(diǎn)以結(jié)點(diǎn)e為根的子樹的深度是多少？為根的子樹的深度是多少？311)樹的度數(shù)是多少？樹的度數(shù)是多少？36.2 6.2 二二 叉叉 樹樹二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉樹的許多操作算法簡單，而任何樹因?yàn)閷?duì)二叉樹的許多操作算法簡單，而任何樹都可以與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的都可以與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性存

8、儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。6.2.1 6.2.1 二叉樹的定義二叉樹的定義二叉樹是由二叉樹是由n(n=0)n(n=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，者為空集，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子左子樹樹和和右子樹右子樹的、的、互不相交互不相交的二叉樹組成。的二叉樹組成。二叉樹不是樹的特殊情況，它們是兩個(gè)概念。有關(guān)數(shù)二叉樹不是樹的特殊情況，它們是兩個(gè)概念。有關(guān)數(shù)的術(shù)語也都適用于二叉樹。的術(shù)語也都適用于二叉樹。特點(diǎn)：特點(diǎn)：每個(gè)結(jié)點(diǎn)至多只有二棵子樹每個(gè)結(jié)點(diǎn)至多只有二棵子樹子樹有左右之分，次序不能任意顛倒子樹有左右之分，次序不

9、能任意顛倒 二叉樹的主要基本操作二叉樹的主要基本操作：查找查找： Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();插入：插入： I

10、nitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);刪除： ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR); 二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài)：6.2.2 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)二叉樹具有下列重要性質(zhì)：二叉樹具有下列重要性質(zhì)：性質(zhì)性質(zhì)1 1 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有2i-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 (i1)性質(zhì)性質(zhì)

11、2 2 ： 深度為深度為 k 的二叉樹上至多含的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)（k1）。）。性質(zhì)性質(zhì) 3 3 ： 對(duì)任何一棵二叉樹，若它含有對(duì)任何一棵二叉樹，若它含有n0 個(gè)葉子結(jié)個(gè)葉子結(jié)點(diǎn)、點(diǎn)、n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式：的結(jié)點(diǎn)，則必存在關(guān)系式：n0 = n2+1。度：擁有結(jié)點(diǎn)的個(gè)數(shù)度：擁有結(jié)點(diǎn)的個(gè)數(shù)兩類兩類特殊特殊的二叉樹：的二叉樹：滿二叉樹滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為編號(hào)為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對(duì)應(yīng)。右結(jié)點(diǎn)缺123456789 10 11 12 13 14 15a

12、bcdefghij性質(zhì)性質(zhì) 4 4：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度深度為 log2n +1 。深度-層性質(zhì)性質(zhì) 5 5：若對(duì)含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號(hào)，則對(duì)完全二叉 樹 中 任 意 一 個(gè) 編 號(hào) 為 i 的 結(jié) 點(diǎn) ：(1) 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親， 否則，編號(hào)為 i/2 的結(jié)點(diǎn)為其雙親雙親結(jié)點(diǎn)；(2) 若 2in，則該結(jié)點(diǎn)無左孩子，否則，編號(hào)為 2 i 的 結(jié) 點(diǎn) 為 其 左 孩 子左 孩 子 結(jié) 點(diǎn) ；(3) 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。習(xí)題：習(xí)題：一個(gè)滿二叉樹有

13、一個(gè)滿二叉樹有n 個(gè)結(jié)點(diǎn)，其中個(gè)結(jié)點(diǎn)，其中m 個(gè)是葉結(jié)個(gè)是葉結(jié)點(diǎn)，樹的深度是點(diǎn)，樹的深度是 h，則表達(dá)式正確的是：則表達(dá)式正確的是： A、n = h+m B、h+m =2n C、 m= h-1 D、n=2 h -1一棵完全二叉樹上有一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是結(jié)點(diǎn)的個(gè)數(shù)是_ a. 250 b. 501c. 254 d. 5056.2.3 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)一.順序存儲(chǔ)結(jié)構(gòu) 它是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。它是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。因此，必須把二叉樹的所有結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)囊虼?，必須把二叉?/p>

14、的所有結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)男蛄?，結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之序列，結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系，用編號(hào)的方法間的邏輯關(guān)系，用編號(hào)的方法 #define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù) typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn) SqBiTree bt;從樹根起，自上層至下層，每層自左至右的給所有結(jié)點(diǎn)從樹根起，自上層至下層，每層自左至右的給所有結(jié)點(diǎn)編號(hào)，完全二叉樹上編號(hào)為編號(hào)，完全二叉樹上編號(hào)為i i的結(jié)點(diǎn)元素存儲(chǔ)在如上的結(jié)點(diǎn)元素存儲(chǔ)在如上定義的一維數(shù)組中下標(biāo)為定義的一

15、維數(shù)組中下標(biāo)為i-1i-1的分量中。的分量中。abcdefghijkl 編號(hào)：編號(hào)： 1 2 3 4 5 6 7 8 9 10 11 12完全二叉樹完全二叉樹abcdefghijkl 存儲(chǔ)單元：存儲(chǔ)單元： 0 1 2 3 4 5 6 7 8 9 10 11 ABCDEFG 表示該處沒有元素表示該處沒有元素存在僅僅為了好理解存在僅僅為了好理解ABCDEFG一般二叉樹一般二叉樹 最壞的情況：最壞的情況：是右單支樹，一棵深度為k的右單支樹，只有k個(gè)結(jié)點(diǎn)，卻需分配2k1個(gè)存儲(chǔ)單元。缺點(diǎn)：缺點(diǎn)：是有可能對(duì)存儲(chǔ)空間造成極大的浪費(fèi)，是有可能對(duì)存儲(chǔ)空間造成極大的浪費(fèi)，在最壞的情況下，一個(gè)深度為在最壞的情況下，

16、一個(gè)深度為H H且只有且只有H H個(gè)結(jié)個(gè)結(jié)點(diǎn)的右單支樹確需要點(diǎn)的右單支樹確需要2 2h h-1-1個(gè)結(jié)點(diǎn)存儲(chǔ)空間。因個(gè)結(jié)點(diǎn)存儲(chǔ)空間。因此僅適用于完全二叉樹，此僅適用于完全二叉樹，而且，若經(jīng)常需要插入與刪除樹中結(jié)點(diǎn)時(shí)，而且，若經(jīng)常需要插入與刪除樹中結(jié)點(diǎn)時(shí)，順序存儲(chǔ)方式不是很好！順序存儲(chǔ)方式不是很好！二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（重要）設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可以構(gòu)成不同形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可以構(gòu)成不同形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：1 1、二叉鏈、二叉鏈表表鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。結(jié)點(diǎn)的存儲(chǔ)的結(jié)構(gòu)為：ADEBCF ro

17、ot結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):lchild data rchild 下圖下圖( (a)a)給出一棵二叉樹的二叉鏈表示。二叉給出一棵二叉樹的二叉鏈表示。二叉鏈表也可以帶頭結(jié)點(diǎn)的方式存放，如圖鏈表也可以帶頭結(jié)點(diǎn)的方式存放，如圖( (b)b)所示所示。C 語言的類型描述如下語言的類型描述如下: :typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;（2 2）三叉鏈表存儲(chǔ)（）三叉鏈表存儲(chǔ)（不要求不要求） 每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：每個(gè)結(jié)點(diǎn)

18、由四個(gè)域組成，具體結(jié)構(gòu)為：其中，其中，datadata、lchildlchild以及以及rchildrchild三個(gè)域的意義同二三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；叉鏈表結(jié)構(gòu)；parentparent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查針。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)；但是，相對(duì)于二叉鏈表存儲(chǔ)結(jié)構(gòu)而言找雙親結(jié)點(diǎn)；但是，相對(duì)于二叉鏈表存儲(chǔ)結(jié)構(gòu)而言，它增加了空間開銷。，它增加了空間開銷。 下圖給出一棵二叉樹的三叉鏈表示。 6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹一、問題的提出一、問題的

19、提出順著某一條搜索路徑巡訪巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次均被訪問一次，而且僅被訪問一次。僅被訪問一次。 “訪問訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。 “遍歷遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)， 每個(gè)每個(gè)結(jié)點(diǎn)有兩個(gè)后繼結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷存在如何遍歷即按什么樣的搜搜索路徑索路徑遍歷的問題。假如以假如以L L、D D、R R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，遍歷整個(gè)二叉樹則有遍歷右子樹，遍歷整個(gè)二叉樹則有DLRDLR、LDRLDR、

20、LRDLRD、DRLDRL、RDLRDL、RLDRLD六種遍歷方案。若規(guī)定先左后右，則六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為：只有前三種情況，分別規(guī)定為： DLRDLR先（根）序遍歷， LDRLDR中（根）序遍歷， LRDLRD后（根）序遍歷。由二叉樹的遞歸定義，由二叉樹的遞歸定義，二叉樹的三個(gè)基本組成二叉樹的三個(gè)基本組成單元是：根結(jié)點(diǎn)、左子單元是：根結(jié)點(diǎn)、左子樹和右子樹。樹和右子樹。bca(根結(jié)點(diǎn))(右子樹)(左子樹)1、先序遍歷二叉樹先序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（2 2）先序遍歷

21、左子樹；）先序遍歷左子樹；（3 3）先序遍歷右子樹。）先序遍歷右子樹。2、中序遍歷二叉樹中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）中序遍歷左子樹；）中序遍歷左子樹；（2 2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（3 3）中序遍歷右子樹。）中序遍歷右子樹。3、后序遍歷二叉樹后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）后序遍歷左子樹；）后序遍歷左子樹；（2 2）后序遍歷右子樹；）后序遍歷右子樹；（3 3）訪問根結(jié)點(diǎn)。）訪問根結(jié)點(diǎn)。先根序列是：先根序列是： A B D C E G F H I ；中根序列是：中

22、根序列是： D B A E G C H F I 后根序列是：后根序列是： D B G E H I F C A ；可定義前驅(qū)及后繼結(jié)點(diǎn)：可定義前驅(qū)及后繼結(jié)點(diǎn)：如：二叉樹中的結(jié)點(diǎn)如：二叉樹中的結(jié)點(diǎn)C，它的先根前驅(qū)是它的先根前驅(qū)是D，先根后繼是先根后繼是E，中根前驅(qū)是中根前驅(qū)是G，對(duì)稱序后繼是對(duì)稱序后繼是H 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹由二叉樹的先序和中序序列建樹 如果同時(shí)已知二叉樹的中序序列“cbdaegf”，則會(huì)如何？ 二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹右子樹右子樹右子樹右子樹根根根根a b c d e f g

23、c b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列結(jié)論：由二叉樹的前序和中序序列或后序和結(jié)論：由二叉樹的前序和中序序列或后序和中序序列能惟一確定一棵二叉樹，但由前序中序序列能惟一確定一棵二叉樹，但由前序后序序列卻不一定能惟一確定一棵二叉樹。后序序列卻不一定能惟一確定一棵二叉樹。問：先序遍歷：問：先序遍歷：ABDGCEF 中序遍歷：中序遍歷：DGBAECF 后序遍歷：后序遍歷：GDBEFCA1.已知一棵樹的先根和中根遍歷次序如下：已知一棵樹的先根和中根遍歷次序如下： a b e f g c d h I e f g b c h I d a試畫出此樹

24、，并畫出轉(zhuǎn)化后的二叉樹，以及此試畫出此樹，并畫出轉(zhuǎn)化后的二叉樹，以及此二叉樹的后序線索二叉樹。二叉樹的后序線索二叉樹。 2.一棵完全二叉樹按層次遍歷的序列是一棵完全二叉樹按層次遍歷的序列是ABCDEFGHI，則在先序遍歷中結(jié)點(diǎn)則在先序遍歷中結(jié)點(diǎn)E的的直接前驅(qū)是直接前驅(qū)是 I ，后序遍歷中結(jié)點(diǎn)，后序遍歷中結(jié)點(diǎn)B的直接后繼是的直接后繼是 F 。3、試找出分別滿足下面條件的所有二叉樹、試找出分別滿足下面條件的所有二叉樹（1）前序序列和中序序列相同）前序序列和中序序列相同（2）中序序列和后序序列相同）中序序列和后序序列相同（3）前序序列和后序序列相同）前序序列和后序序列相同（4）前序、中序、后序序列均

25、相同）前序、中序、后序序列均相同4、試采用順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法分別畫出下、試采用順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法分別畫出下列各二叉樹的存儲(chǔ)結(jié)構(gòu)，并寫出前、中后序序列。列各二叉樹的存儲(chǔ)結(jié)構(gòu)，并寫出前、中后序序列。6.3.26.3.2 線索二叉樹線索二叉樹（重要）（重要）當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí), ,只能找到結(jié)點(diǎn)的左只能找到結(jié)點(diǎn)的左右孩子的信息右孩子的信息, ,而不能在結(jié)點(diǎn)的任一序列的前驅(qū)與而不能在結(jié)點(diǎn)的任一序列的前驅(qū)與后繼信息后繼信息, ,這種信息只有在遍歷的這種信息只有在遍歷的動(dòng)態(tài)動(dòng)態(tài)過程中才能過程中才能得到；并且為了能保存遍歷過程中得到的信息得到；并且為了能保存遍

26、歷過程中得到的信息, ,可可增加標(biāo)志域增加標(biāo)志域; ;任何包括任何包括n n個(gè)結(jié)點(diǎn)的二叉樹中，個(gè)結(jié)點(diǎn)的二叉樹中，2 2n n個(gè)指針中只有個(gè)指針中只有n n - 1- 1個(gè)用來指示結(jié)點(diǎn)的左、右子女，而另外個(gè)用來指示結(jié)點(diǎn)的左、右子女，而另外n + 1n + 1個(gè)為空個(gè)為空解決方法：用指向結(jié)點(diǎn)在對(duì)稱序下的前驅(qū)結(jié)點(diǎn)或解決方法：用指向結(jié)點(diǎn)在對(duì)稱序下的前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的指針來代替這些空的指針，這種附加后繼結(jié)點(diǎn)的指針來代替這些空的指針，這種附加的指針稱作的指針稱作“線索線索”infoltagrtag rlinkllinkltag 0:指針,指向結(jié)點(diǎn)的左子女1:線索,指向結(jié)點(diǎn)的前趨結(jié)點(diǎn)rtag 0:指針,指

27、向結(jié)點(diǎn)的右子女1:線索,指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)指向該線性序列中的“前驅(qū)”和 “后繼” 的指針指針，稱作“線索線索”與其相應(yīng)的二叉樹，稱作 “線索二叉樹線索二叉樹”包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “線索鏈表線索鏈表”A B C D E F G H K D C B E typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;線索鏈表的類型描述： typedef enum Link, Thre

28、ad PointerThr; / Link=0:指針，Thread=1:線索在中序線索二叉樹中找：在中序線索二叉樹中找： 葉子結(jié)點(diǎn)：右鏈域是線索，直接找到后繼葉子結(jié)點(diǎn)：右鏈域是線索，直接找到后繼后繼后繼 非終端結(jié)點(diǎn)：后繼是遍歷其右子樹時(shí)訪問的第一非終端結(jié)點(diǎn)：后繼是遍歷其右子樹時(shí)訪問的第一 個(gè)結(jié)點(diǎn)（右子樹中最左下的結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)（右子樹中最左下的結(jié)點(diǎn)） 左標(biāo)志位為左標(biāo)志位為1，則左鏈域?yàn)榫€索即為前驅(qū)，則左鏈域?yàn)榫€索即為前驅(qū)前驅(qū)前驅(qū) 遍歷左子樹時(shí)最后訪問的一個(gè)結(jié)點(diǎn)即左子樹中最右遍歷左子樹時(shí)最后訪問的一個(gè)結(jié)點(diǎn)即左子樹中最右 下的結(jié)點(diǎn)下的結(jié)點(diǎn) 試畫出如圖所示的二叉樹的前序、中序和后序相應(yīng)的試畫出如圖所示

29、的二叉樹的前序、中序和后序相應(yīng)的線索鏈表。線索鏈表。6.4 樹和森林樹和森林6.4.1樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)樹樹三種存儲(chǔ)結(jié)構(gòu)三種存儲(chǔ)結(jié)構(gòu)一、雙親表示法一、雙親表示法: #define MAX_TREE_SIZE 100結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): typedef struct PTNode Elem data; int parent; / 雙親位置域雙親位置域 PTNode;樹結(jié)構(gòu)樹結(jié)構(gòu): typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;優(yōu)點(diǎn)：優(yōu)點(diǎn)：便于找雙親結(jié)點(diǎn)便于找雙親結(jié)點(diǎn)及根結(jié)點(diǎn)

30、。及根結(jié)點(diǎn)。缺點(diǎn)：缺點(diǎn)：求孩子結(jié)點(diǎn)時(shí)需求孩子結(jié)點(diǎn)時(shí)需遍歷整個(gè)結(jié)構(gòu)。遍歷整個(gè)結(jié)構(gòu)。二、孩子鏈表表示法二、孩子鏈表表示法:孩子結(jié)點(diǎn)結(jié)構(gòu)孩子結(jié)點(diǎn)結(jié)構(gòu): typedef struct CTNode int child; struct CTNode *next; *ChildPtr;雙親結(jié)點(diǎn)結(jié)構(gòu)雙親結(jié)點(diǎn)結(jié)構(gòu) typedef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針孩子鏈的頭指針 CTBox;樹結(jié)構(gòu)樹結(jié)構(gòu): typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位

31、置 CTree;優(yōu)點(diǎn)：優(yōu)點(diǎn)：求孩子結(jié)點(diǎn)時(shí)很方便。求孩子結(jié)點(diǎn)時(shí)很方便。缺點(diǎn)：缺點(diǎn)：不適用于找雙親結(jié)點(diǎn)不適用于找雙親結(jié)點(diǎn)三、樹的二叉鏈表三、樹的二叉鏈表(孩子孩子-兄弟）存儲(chǔ)表示法兄弟）存儲(chǔ)表示法Typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, CSTree;優(yōu)點(diǎn)：便于實(shí)現(xiàn)樹的各種操作。優(yōu)點(diǎn)：便于實(shí)現(xiàn)樹的各種操作。習(xí)題：畫出如下各樹的三種存儲(chǔ)結(jié)構(gòu)。習(xí)題：畫出如下各樹的三種存儲(chǔ)結(jié)構(gòu)。6.4.2森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換1、則、則由森林轉(zhuǎn)換成二叉樹由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換

32、規(guī)則為的轉(zhuǎn)換規(guī)則為: 若若 F = ，則則 B = ;否則，否則， 由由 ROOT( T1 ) 對(duì)應(yīng)得到對(duì)應(yīng)得到 Node(root); 由由 (t11, t12, , t1m ) 對(duì)應(yīng)得到對(duì)應(yīng)得到 LBT; 由由 (T2, T3, Tn ) 對(duì)應(yīng)得到對(duì)應(yīng)得到 RBT.2、由由二叉樹轉(zhuǎn)換為森林二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為的轉(zhuǎn)換規(guī)則為: 若若 B = , 則則 F = ;否則，否則，由由 Node(root) 對(duì)應(yīng)得到對(duì)應(yīng)得到 ROOT( T1 );由由LBT 對(duì)應(yīng)得到對(duì)應(yīng)得到 ( t11, t12, ，t1m);由由RBT 對(duì)應(yīng)得到對(duì)應(yīng)得到 (T2, T3, , Tn)由此，樹的各種操作均可轉(zhuǎn)

33、化成二叉樹的操作由此，樹的各種操作均可轉(zhuǎn)化成二叉樹的操作來完成來完成換言之，和樹對(duì)應(yīng)的二叉樹，其左、右子樹的換言之，和樹對(duì)應(yīng)的二叉樹，其左、右子樹的概念改變成：概念改變成：左是孩子，右是兄弟左是孩子，右是兄弟6.4.3樹和森林的遍歷樹和森林的遍歷樹的遍歷可有三條搜索路徑樹的遍歷可有三條搜索路徑:先根先根(次序次序)遍歷遍歷: 若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。后根后根(次序次序)遍歷遍歷: 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。按層次遍歷按層次遍歷: 若樹不空

34、，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。森林的遍歷森林的遍歷 先序遍歷先序遍歷(對(duì)森林中的每一棵樹進(jìn)行先根遍歷對(duì)森林中的每一棵樹進(jìn)行先根遍歷)若森林不空，則若森林不空，則 訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn); 先序遍歷森林中第一棵樹的子樹森林先序遍歷森林中第一棵樹的子樹森林; 先序遍歷森林中先序遍歷森林中(除第一棵樹之外除第一棵樹之外)其余樹構(gòu)成的森林。其余樹構(gòu)成的森林。 中序遍歷中序遍歷(對(duì)森林中的每一棵樹進(jìn)行后根遍歷對(duì)森林中的每一棵樹進(jìn)行后根遍歷)若森林不空，則若森林不空，則 中序遍歷森林中第一棵樹的子樹森林中序遍歷森林中第一棵樹

35、的子樹森林; 訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn); 中序遍歷森林中中序遍歷森林中(除第一棵樹之外除第一棵樹之外)其余樹構(gòu)成的森林。其余樹構(gòu)成的森林。習(xí)題：對(duì)圖所示的森林：習(xí)題：對(duì)圖所示的森林：1) 求各樹的前序序列和后序序列；求各樹的前序序列和后序序列；2) 求森林的前序序列和后序序列；求森林的前序序列和后序序列；3) 將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；6.6 最優(yōu)二叉樹哈夫曼樹1哈夫曼樹的基本概念 最優(yōu)二叉樹，也稱哈夫曼（最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹，是指對(duì)于一樹，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長度組帶有確定權(quán)值

36、的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。的二叉樹。 二叉樹的路徑長度是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長二叉樹的路徑長度是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長度之和。如果二叉樹中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可度之和。如果二叉樹中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。設(shè)二叉樹具有將這一概念加以推廣。設(shè)二叉樹具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長度與相應(yīng)結(jié)點(diǎn)權(quán)值的那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度，記為：乘積之和叫做二叉樹的帶權(quán)路徑長度，記為： WPL WkL Lk 其中其中Wk為第為第k k個(gè)葉結(jié)點(diǎn)的權(quán)值

37、，個(gè)葉結(jié)點(diǎn)的權(quán)值，L Lk 為第為第k個(gè)葉結(jié)點(diǎn)的路個(gè)葉結(jié)點(diǎn)的路徑長度徑長度。 在給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同在給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的帶權(quán)二叉樹。例如，給出的帶權(quán)二叉樹。例如，給出4個(gè)葉結(jié)點(diǎn)，設(shè)其權(quán)值分別個(gè)葉結(jié)點(diǎn)，設(shè)其權(quán)值分別為為1，3，5，7，我們可以構(gòu)造出形狀不同的多個(gè)二叉樹，我們可以構(gòu)造出形狀不同的多個(gè)二叉樹。下圖給出了其中。下圖給出了其中5個(gè)不同形狀的二叉樹，其帶權(quán)路徑個(gè)不同形狀的二叉樹，其帶權(quán)路徑長度分別為：長度分別為： （a）WPL1232527232 （b）WPL1333527129 （c）WPL1233537133 （d）WPL735332

38、1143 （e）WPL7152331329 如何找到帶權(quán)路徑長度最小的二叉樹（即哈夫曼樹）呢？根據(jù)如何找到帶權(quán)路徑長度最小的二叉樹（即哈夫曼樹）呢？根據(jù)哈夫曼樹的定義，一棵二叉樹要使其哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越值最小，必須使權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。哈夫曼（哈夫曼（Haffman）依據(jù)這一特點(diǎn)提出了一種方法，這種方法的依據(jù)這一特點(diǎn)提出了一種方法，這種方法的基本思想是：基本思想是： （1）由給定的）由給定的n個(gè)權(quán)值個(gè)權(quán)值W1，W2，Wn構(gòu)造構(gòu)造n棵只有一個(gè)棵只有一個(gè)葉結(jié)點(diǎn)的

39、二叉樹，從而得到一個(gè)二叉樹的集合葉結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合FT1，T2，Tn； （2）在在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；其左、右子樹根結(jié)點(diǎn)權(quán)值之和； （3）在集合）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合立的二叉樹加入到集合F中；中； （4）重復(fù)（）重復(fù)（2）（）（3）兩步，當(dāng)）兩步，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。二叉樹便是所要建立的哈夫曼樹。 下圖給出前面提到的葉結(jié)點(diǎn)權(quán)值集合為下圖給出前面提到的葉結(jié)點(diǎn)權(quán)值集合為W1，3，5，7的哈夫曼樹的構(gòu)造過程?？梢杂?jì)算出其帶權(quán)路的哈夫曼樹的構(gòu)造過程?？梢杂?jì)算出其帶權(quán)路徑長度為徑長度為29，由此可見，對(duì)于同一組給定葉結(jié)點(diǎn)所構(gòu)，由此可見，對(duì)于同一組給定葉結(jié)點(diǎn)所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但帶權(quán)路徑長度造