數(shù)據(jù)結(jié)構(gòu)-第6章-數(shù)和二叉樹(shù).ppt

1、1,數(shù)據(jù)結(jié)構(gòu)： 樹(shù),2,3,4,第六章 樹(shù)和二叉樹(shù),5,課前思考,家族譜系圖,一對(duì)多關(guān)系,6,徐海學(xué)院計(jì)算機(jī)系,7,概述,樹(shù)型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu) 樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu) 樹(shù)的應(yīng)用 人類社會(huì)的族譜 社會(huì)組織結(jié)構(gòu) 在編譯程序中的語(yǔ)法樹(shù) 在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹(shù)來(lái)組織信息,8,樹(shù)的定義,樹(shù)是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集合,若n=0，稱為空樹(shù)；,有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)。它只有直接后繼，但沒(méi)有直接前驅(qū)；,遞歸定義子樹(shù),9,樹(shù)基本操作（P119）：,10,樹(shù)的基本術(shù)語(yǔ),結(jié)點(diǎn)：包含一個(gè)元素及若干指向其子樹(shù)的分支，大寫(xiě)字母表示,度：一個(gè)結(jié)點(diǎn)包含子樹(shù)的數(shù)目，稱為該結(jié)點(diǎn)的度A:3,B:

2、2,F:0,葉子：度為0的結(jié)點(diǎn)，稱為葉子結(jié)點(diǎn)或樹(shù)葉，也叫終端結(jié)點(diǎn)(J,K,L)。,11,樹(shù)的基本術(shù)語(yǔ),孩子結(jié)點(diǎn)：若結(jié)點(diǎn)X有子樹(shù)，則子樹(shù)的根結(jié)點(diǎn)為X的孩子結(jié)點(diǎn)A:B,C,D,雙親結(jié)點(diǎn)：若結(jié)點(diǎn)A有子女B，則A為B的雙親結(jié)點(diǎn)。,祖先結(jié)點(diǎn)：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過(guò)分枝上的所有結(jié)點(diǎn)為該結(jié)點(diǎn)的祖先，M的祖先結(jié)點(diǎn)為：H,D,A,12,樹(shù)的基本術(shù)語(yǔ),子孫結(jié)點(diǎn)：某一結(jié)點(diǎn)的子女及子女的子女都為該結(jié)點(diǎn)子孫。A:C,G,兄弟結(jié)點(diǎn)：具有同一個(gè)雙親的結(jié)點(diǎn)，稱為兄弟結(jié)點(diǎn)。E，F(xiàn),分枝結(jié)點(diǎn)：除葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)，為分枝結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn).C,13,樹(shù)的基本術(shù)語(yǔ),層數(shù)：根結(jié)點(diǎn)的層數(shù)為1，其它結(jié)點(diǎn)的層數(shù)為從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過(guò)

3、的分支數(shù)目再加1。,樹(shù)的高度（深度） ：樹(shù)中結(jié)點(diǎn)所處的最大層數(shù)稱為樹(shù)的高度。,14,有序樹(shù) 若一棵樹(shù)中所有子樹(shù)從左到右的排序是有順序的，不能顛倒次序。稱該樹(shù)為有序樹(shù)。 無(wú)序樹(shù) 若一棵樹(shù)中所有子樹(shù)的次序無(wú)關(guān)緊要，則稱為無(wú)序樹(shù)。 森林（樹(shù)林） 若干棵互不相交的樹(shù)組成的集合為森林。一棵樹(shù)可以看成是一個(gè)特殊的森林。刪去一棵非空樹(shù)的根結(jié)點(diǎn)，樹(shù)就變成身森林；反之,若增加一個(gè)根結(jié)點(diǎn),讓森林中每一棵樹(shù)的根結(jié)點(diǎn)都變成它的子女,森林就成為一棵樹(shù),15,樹(shù)與線性結(jié)構(gòu)的區(qū)別,16,結(jié)點(diǎn)A的度：3 結(jié)點(diǎn)B的度：2 結(jié)點(diǎn)M的度：0,葉子：K，L，F(xiàn)，G，M，I，J,結(jié)點(diǎn)A的孩子：B，C，D 結(jié)點(diǎn)B的孩子：E，F(xiàn),結(jié)點(diǎn)I的

4、雙親：D 結(jié)點(diǎn)L的雙親：E,結(jié)點(diǎn)B，C，D為兄弟 結(jié)點(diǎn)K，L為兄弟,樹(shù)的度：3,結(jié)點(diǎn)A的層次：1 結(jié)點(diǎn)M的層次：4,樹(shù)的深度：4,結(jié)點(diǎn)F，G為堂兄弟 結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先,17,練習(xí)1,列出下圖所示樹(shù)的葉結(jié)點(diǎn)、分支結(jié)點(diǎn)和每個(gè)結(jié)點(diǎn)的層次。,18,徐海學(xué)院計(jì)算機(jī)系,19,什么是二叉樹(shù)？,每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子,度=2,有序樹(shù)（分左右）,20,一個(gè)典型的二叉樹(shù),21,練習(xí),試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。,22,回顧 樹(shù)的基本特點(diǎn)、基本術(shù)語(yǔ),一個(gè)三層的二叉樹(shù)最多有幾個(gè)節(jié)點(diǎn)、最少有幾個(gè)節(jié)點(diǎn)。,23,有一棵樹(shù)的括號(hào)表示為A(B,C(E,F(G),D)，回答下面的問(wèn)題： 1

5、、這棵樹(shù)的根結(jié)點(diǎn)是多少 2、這棵樹(shù)的葉子結(jié)點(diǎn)是什么 3、結(jié)點(diǎn)C的度是多少 4、這棵樹(shù)的度是多少 5、這棵樹(shù)的深度是多少 6、結(jié)點(diǎn)C的孩子結(jié)點(diǎn)是哪些 7、結(jié)點(diǎn)C的雙親結(jié)點(diǎn)是誰(shuí),24,若一棵度為4的樹(shù)中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、3、2、2，則該樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)是多少？總結(jié)點(diǎn)個(gè)數(shù)是多少？,25,二叉樹(shù)的性質(zhì)1,歸納法證明,26,二叉樹(shù)的性質(zhì)2,27,二叉樹(shù)的性質(zhì)3,n=n0+n1+n2 1,n=n1+2n2+1 2,n0=n2+1,28,兩種特殊形態(tài)的二叉樹(shù),滿二叉樹(shù),29,兩種特殊形態(tài)的二叉樹(shù),完全二叉樹(shù),如果一棵具有n個(gè)結(jié)點(diǎn)的深度為k的二叉樹(shù)，它的每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編

6、號(hào)為1 n的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱這棵二叉樹(shù)為完全二叉樹(shù)。,30,實(shí)例,31,二叉樹(shù)的性質(zhì)4,3.3=3 3.3=4,根據(jù)性質(zhì)2和完全二叉樹(shù)性質(zhì)： 2k-1 1n 2k 1 或 2k-1 n 2k k-1 log2n k,表明：若 log2n 是整數(shù)，則等于 k-1，若 log2n 不是整數(shù)，則它大于 k-1 而小于 k。 log2n 表示僅取 log2n 的整數(shù)部分，舍去它的小數(shù)部分。,32,二叉樹(shù)的性質(zhì)5,性質(zhì)5 如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右對(duì)結(jié)點(diǎn)編號(hào)1，2，n，并簡(jiǎn)稱編號(hào)為i的結(jié)點(diǎn)為 i(1in)，則有如下結(jié)論成立：,(1) 如果 i=1，則編號(hào)為 i 的結(jié)點(diǎn)是二叉樹(shù)的

7、根，無(wú)雙親； 如果 i1，則其雙親結(jié)點(diǎn) parent(i) 的編號(hào)是 i/2 。,如果 2in，則編號(hào)為 i 的結(jié)點(diǎn)無(wú)左孩子（編號(hào)為 i 的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn) lChild(i) 的編號(hào)是 2i 。,(3) 如果 2i+1n，則編號(hào)為 i 的結(jié)點(diǎn)無(wú)右孩子；否則其右孩子結(jié)點(diǎn) rChild(i) 的編號(hào)是結(jié)點(diǎn) 2i+1，左孩子為2i,33,34,練習(xí),1、具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(從1層開(kāi)始計(jì)數(shù))( ) A.6 B.5 C.4 D.7 2、二叉樹(shù)第i（i=1）層上至多有（ ）結(jié)點(diǎn)。 A. 2i B. 2i C. 2i-1 D. 2i-1 3、將一棵有50個(gè)結(jié)點(diǎn)的完全二叉

8、樹(shù)按層編號(hào)(從1開(kāi)始)，則對(duì)編號(hào)為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)（ ） A.無(wú)左、右孩子 B.有左孩子，無(wú)右孩子 C.有右孩子，無(wú)左孩子 D.有左、右孩子,35,回顧,二叉樹(shù)的5個(gè)性質(zhì) 某一層上的最大結(jié)點(diǎn)數(shù)為： K深度的二叉樹(shù)最多結(jié)點(diǎn)數(shù)為： n0=n2+1 n結(jié)點(diǎn)完全二叉樹(shù)深度： n結(jié)點(diǎn)完全二叉樹(shù)任一結(jié)點(diǎn)i有：,2i-1,2k-1,log2n +1,雙親 i/2,左孩子2i,右孩子 2i+1,36,4. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表 三叉鏈表 線索鏈表,37,二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu),/二叉樹(shù)的順序存儲(chǔ)表示 #define MAX_TREE_SIZE 100 typedef TEl

9、emType SqBiTree MAX_TREE_SIZE； /0號(hào)單元存儲(chǔ)根結(jié)點(diǎn) SqBiTree bt；,38,完全二叉樹(shù)的數(shù)組表示,表示方法：對(duì)完全二叉樹(shù)所有得結(jié)點(diǎn)按照層次次序自頂向下，同一層次自左向右順序編號(hào)1,2 ,n,得到一線性序列，并把此序列放入到一維數(shù)組中。這種方法可以很容易的找到一個(gè)結(jié)點(diǎn)的雙親、兄弟、子女（性質(zhì)5）。 比如結(jié)點(diǎn)C,39,一般二叉樹(shù)的樹(shù)組表示,若該二叉樹(shù)為非完全二叉樹(shù)，則必須將相應(yīng)位置空出來(lái)，使存放的結(jié)果符合完全二叉樹(shù)形狀。如圖給出了順序存貯形式。,40,41,設(shè)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如下：,根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫(huà)出該二叉樹(shù)。,42,二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),適用

10、范圍： 一般的二叉樹(shù)，并且如果在一棵樹(shù)中進(jìn)行添加刪除時(shí)，要移動(dòng)許多結(jié)點(diǎn)。,43,二叉鏈表,44,與單鏈表類似,整個(gè)二叉樹(shù)可以 以一個(gè)指向根結(jié)點(diǎn)的指針(表頭指針)表示,45,/ 基本操作的原型 Status CreateBiTree( BiTree ,46,也可以有類似于雙向鏈表的結(jié)構(gòu)-三叉鏈表,47,二叉鏈表和三叉鏈表,48,三叉鏈表,49,三叉鏈表結(jié)構(gòu)圖,50,可以證明,在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域。,51,徐海學(xué)院計(jì)算機(jī)系,52,何為遍歷二叉樹(shù),按某種順序 訪問(wèn) 一次所有結(jié)點(diǎn),讀取數(shù)據(jù) 修改數(shù)據(jù),必須先左后右 DLR前序遍歷 LDR中序遍歷 LRD后序遍歷,53,先序遍歷,定

11、義如下,若二叉樹(shù)為空，則空操作;否則 （1）訪問(wèn)根結(jié)點(diǎn) （2）前序遍歷左子樹(shù); （3）前序遍歷右子樹(shù);,A B D E G H C F I J,54,前序遍歷動(dòng)畫(huà)演示,55,中序遍歷,定義如下,若二叉樹(shù)為空，則空操作；否則 (1) 中序遍歷左子樹(shù)； (2) 訪問(wèn)根結(jié)點(diǎn)； (3) 中序遍歷右子樹(shù),D B G E H A C I J F,56,中序遍歷動(dòng)畫(huà)演示,57,后序遍歷,定義如下,若二叉樹(shù)為空，則空操作；否則 (1) 后序遍歷左子樹(shù)； (2) 后序遍歷右子樹(shù)； (3) 訪問(wèn)根結(jié)點(diǎn)。,D G H E B J I F C A,58,后序遍歷動(dòng)畫(huà)演示,59,前序遍歷算法實(shí)現(xiàn)-遞規(guī)算法,voidPr

12、eorder (BiTree T，void(*visit)( BiTree )/先序遍歷以T為根指針的二叉樹(shù)if(T) /T=NULL時(shí)，二叉樹(shù)為空樹(shù)，不做任何操作visit(T);/通過(guò)函數(shù)指針 *visit 訪問(wèn)根結(jié)點(diǎn)Preorder(T-Lchild, visit);/先序遍歷左子樹(shù)Preorder(T-Rchild, visit);/先序遍歷右子樹(shù)/if,60,a+b*(c-d)-e/f,61,練習(xí),先序遍歷序列： 中序遍歷序列： 后序遍歷序列：,ABDGCEFH BGDAECFH GDBEHFCA,62,經(jīng)典題：寫(xiě)出三個(gè)結(jié)點(diǎn)的二叉樹(shù)的前序、中序、后序遍歷的序列,前序后序決定層次，中序

13、決定左右,63,畫(huà)出和下列已知序列對(duì)應(yīng)的二叉樹(shù),二叉樹(shù)的前序訪問(wèn)序列為:EBADCFHGIKJ 二叉樹(shù)的中序訪問(wèn)序列為:ABCDEFGHIJK 2.二叉樹(shù)的中序訪問(wèn)序列為:DCBGEAHFIJK 二叉樹(shù)的后序訪問(wèn)序列為:DCEGBFHKJIA,64,寫(xiě)出前、中、后序遍歷,65,畫(huà)出和下列已知序列對(duì)應(yīng)的二叉樹(shù),前：A B E F C D G H 中：F E B A D C G H,后：F E B D H G C A 中：F E B A D C G H,66,線索二叉樹(shù),問(wèn)題？,如何保存在遍歷過(guò)程中得到的前驅(qū)和后繼信息？,n個(gè)結(jié)點(diǎn)有 n+1 個(gè)鏈域的值為NULL,好好利用NULL,67,線索二叉樹(shù)

14、的結(jié)構(gòu)如下：,0 lchild 域指示結(jié)點(diǎn)的左孩子 ltag= 1 lchild 域指示結(jié)點(diǎn)的前驅(qū) 0 rchild 域指示結(jié)點(diǎn)的右孩子 rtag= 1 rchild 域指示結(jié)點(diǎn)的后繼,以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),叫做線索鏈表,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索.加上線索的二叉樹(shù)稱之為線索二叉樹(shù)。 對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫線索化。,68,中序線索二叉樹(shù),a + b * c d e / f,69,中序線索鏈表,在二叉樹(shù)的線索鏈表上添加了一個(gè)頭結(jié)點(diǎn)。P134。,70,如何在中序線索樹(shù)中找結(jié)點(diǎn)的后繼、前趨？ 結(jié)點(diǎn)的后繼：應(yīng)該是遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)

15、，即右子樹(shù)中最左下的結(jié)點(diǎn)。,71,結(jié)點(diǎn)的前趨：若其左標(biāo)志為“1”，則左鏈為線索，指示其前驅(qū)，否則遍歷左子樹(shù)時(shí)的最后訪問(wèn)的一個(gè)結(jié)點(diǎn)（左子樹(shù)最右下的結(jié)點(diǎn)）為其前驅(qū)。,72,什么時(shí)候采用線索鏈表做存儲(chǔ)結(jié)構(gòu)？ 程序中所用二叉樹(shù)需要經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)和后繼時(shí)。,73,徐海學(xué)院計(jì)算機(jī)系,74,樹(shù)的存儲(chǔ)結(jié)構(gòu)1-雙親表示法,順序存儲(chǔ)結(jié)構(gòu) constMAX_TREE_SIZE = 100;typedef struct /結(jié)點(diǎn)結(jié)構(gòu) ElemType data; int parent;/雙親位置域PTNode; typedef struct /樹(shù)結(jié)構(gòu)PTNode nodesMAX_TREE

16、_SIZE;intr, n;/根的位置和結(jié)點(diǎn)數(shù)PTree;,data,parent,75,雙親表示法示例,data,parent,利用唯一雙親的性質(zhì) 適用于：PARENT(T,x),76,孩子表示法多重鏈表,同構(gòu)：樹(shù)中每個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域而外，還有d個(gè)域，分別存放結(jié) 點(diǎn)的每個(gè)孩子結(jié)點(diǎn)的位置。其中d是樹(shù)的度，即樹(shù)的各個(gè)結(jié)點(diǎn)的 最大度。這種存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)是，浪費(fèi)存儲(chǔ)空間。一棵具有n個(gè) 結(jié)點(diǎn)的度為k的樹(shù)中必有n(k-1)+1個(gè)空鏈域。,異構(gòu)：若樹(shù)的每個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域而外，僅僅存儲(chǔ)各自的孩子 結(jié)點(diǎn)的位置，則每個(gè)結(jié)點(diǎn)將是異構(gòu)的。雖然這樣可以節(jié)約 存儲(chǔ)空間，但是操作麻煩。,77,2 樹(shù)的孩子表示法,type

17、def structCTNode/孩子結(jié)點(diǎn)intchild;structCTNode *next;*ChildPtr; typedef struct ElemType data;/結(jié)點(diǎn)的數(shù)據(jù)元素ChildPtr firstchild;/孩子鏈表頭指針CTBox; typedef struct CTBox nodesMAX_TREE_SIZE;intn, r;/結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置CTree;,J,78,孩子表示法示例,適用于：求孩子的操作,J,79,J,為了方便我們可以,80,4 二叉鏈表表示法（孩子兄弟表示法）,以二叉鏈表做樹(shù)的存儲(chǔ)結(jié)構(gòu),鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下

18、一個(gè)兄弟結(jié)點(diǎn)(fchild 和nsibling) Typedef struct CSNode ElemType data; Struct CSNode * firstchild ,*nextsibling; CSNode,*CSTree;,81,訪問(wèn)結(jié)點(diǎn)x的第 i 個(gè)孩子，則只要從firstchild域找到第1個(gè)孩子結(jié)點(diǎn)，然后沿著孩子結(jié)點(diǎn)的nextsibling域連續(xù)走i -1步，則可以找到第 i 個(gè)孩子。 如果為每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)PARENT域，則同樣能方便實(shí)現(xiàn)PARENT（T, x）操作。,82,樹(shù)和二叉樹(shù)的對(duì)應(yīng),83,練習(xí),畫(huà)出此樹(shù)的 雙親表示、孩子鏈表表示、二叉鏈表表示法。,84,森林與

19、二叉樹(shù)的轉(zhuǎn)換,森林是樹(shù)的有限集合。,從樹(shù)的二叉鏈表表示定義知道：任何一棵和樹(shù)對(duì)應(yīng)的二叉樹(shù)的右子樹(shù)必空。若將森林中第二棵樹(shù)的根結(jié)點(diǎn)看成第一棵樹(shù)的根結(jié)點(diǎn)的兄弟，則可以導(dǎo)出森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系。,如何存儲(chǔ)一片森林？,85,森林和二叉樹(shù)的對(duì)應(yīng)：,86,二叉樹(shù)轉(zhuǎn)換成森林,87,練習(xí),88,森林和樹(shù)的遍歷,樹(shù)的遍歷： （1）先根遍歷：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù)； （2）后根遍歷：先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。,樹(shù)的先根序列為：ABCDE 樹(shù)的后根序列為：BDCEA,當(dāng)以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，樹(shù)的先根遍歷和后根遍歷分別 對(duì)應(yīng)二叉樹(shù)的先序遍歷和中序遍歷算法。,89,森林的

20、遍歷： （1）先序遍歷森林：若森林非空，則可按下述規(guī)則遍歷之：,（2）中序遍歷森林：若森林非空，則可按下述規(guī)則遍歷之：,訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)； 先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林； 先序遍歷除去第一樹(shù)之后剩余的樹(shù)構(gòu)成的森林。,中序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林； 訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)； 中序遍歷除去第一樹(shù)之后剩余的樹(shù)構(gòu)成的森林。,90,森林的先序遍歷和中序遍歷分別對(duì)應(yīng)二叉樹(shù)的先序和中序遍歷。,91,徐海學(xué)院計(jì)算機(jī)系,92,赫夫曼樹(shù),路徑長(zhǎng)度 定義：在樹(shù)中從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成了這兩個(gè)結(jié)點(diǎn)間的路徑，路徑上的分支條數(shù)稱為它的路徑長(zhǎng)度。 樹(shù)的路徑長(zhǎng)度 等于從樹(shù)的根結(jié)點(diǎn)到樹(shù)中

21、各個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。,1,2,3,7,6,5,4,8,93,1,2,3,7,6,5,4,8,1,2,3,7,6,5,4,8,二叉樹(shù)(a),二叉樹(shù)(b),可以得到：a的路徑長(zhǎng)度PL=13，b的路徑長(zhǎng)度PL=14。 為什么分支數(shù)相同、結(jié)點(diǎn)數(shù)相同，而路徑長(zhǎng)度不同？,94,赫夫曼樹(shù)帶權(quán)路徑長(zhǎng)度WPL,什么是權(quán)？ 若將樹(shù)中葉子結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該葉子結(jié)點(diǎn)的權(quán)。 假定一個(gè)有n個(gè)權(quán)值的集合w1,w2wn，其中wi=0。若T是一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，并且將權(quán)值w1,w2wn分別賦給T的n個(gè)葉結(jié)點(diǎn)，則我們稱T是權(quán)值為w1,w2wn的擴(kuò)充二叉樹(shù)。 帶權(quán)值的稱為外結(jié)點(diǎn)，不帶權(quán)值的

22、稱為內(nèi)結(jié)點(diǎn)。,95,樹(shù)的帶權(quán)路徑長(zhǎng)度,樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，其中n 為葉子結(jié)點(diǎn)數(shù)目，wi為第i 個(gè)葉子結(jié)點(diǎn)的權(quán)值，li 為第i 個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。,WPL=,在權(quán)值為w1,w2wn的擴(kuò)充二叉樹(shù)中，其WPL最小的擴(kuò)充二叉樹(shù)稱為最優(yōu)二叉樹(shù)。,96,判斷哪棵樹(shù)是最優(yōu)二叉樹(shù),97,4,5,7,2,4,5,7,2,5,2,4,7,上圖中的3棵二叉樹(shù)都是權(quán)值為7,5,2,4的擴(kuò)充二叉樹(shù) a的帶權(quán)路徑長(zhǎng)度WPL為：36；b的為46，c的為35。 由此可見(jiàn)，帶權(quán)路徑長(zhǎng)度最小的擴(kuò)充二叉樹(shù)不一定是完全二叉樹(shù)。 直觀的看：帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)應(yīng)是權(quán)值大的外結(jié)點(diǎn)離根最近的擴(kuò)充二

23、叉樹(shù)，這就是赫夫曼樹(shù)。,（a）,（b）,（c）,98,解某些判定問(wèn)題，利用赫夫曼樹(shù)可以得到最佳判定算法,例如，編制一個(gè)程序?qū)崿F(xiàn)從百分制到五級(jí)分制的轉(zhuǎn)換。,if ( a60 ) b=“bad”; else if ( a70 ) b=“pass”; else if ( a80 ) b=“general”; else if ( a90 ) b=“good”; else b=“excellent”;,99,a60,不及格,Y,N,a70,及格,Y,N,a80,中等,Y,N,a80,良好,Y,N,良好,100,中等,Y,N,a80,a70,Y,N,a60,及格,Y,a90,優(yōu)秀,N,良好,Y,N,不及格

24、,101,最優(yōu)樹(shù)的構(gòu)造方法 赫夫曼算法,(1) 根據(jù)給定的 n 個(gè)權(quán)值w1,w2,wn，構(gòu)成 n 棵二叉樹(shù)的集合 F=T1,T2,Tn，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為 Wi的根結(jié)點(diǎn)，其左右子樹(shù)均空。(2) 在 F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。(3) 在 F 中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入 F 中。重復(fù)(2)和(3)，直到 F 只含一棵樹(shù)為止。這棵樹(shù)便是所求的赫夫曼樹(shù)。,102,動(dòng)畫(huà)演示,103,練習(xí),給定權(quán)值集合15,03,14,02,06,09,16,17構(gòu)造相應(yīng)的赫夫曼樹(shù)，并計(jì)算

25、他的帶權(quán)路徑長(zhǎng)度。,104,赫夫曼樹(shù)的應(yīng)用赫夫曼編碼,用途：電報(bào)通訊,假設(shè)需傳送的電文為ABACCDA,A:00、B:01 、C:10、D:11,00010010101100，總長(zhǎng)14位,根據(jù)出現(xiàn)的頻率進(jìn)行簡(jiǎn)化 A:0、B:00、C:1、D:01,“000011010”，總長(zhǎng)為9位,問(wèn)題出現(xiàn)了：0000，什么含義？,105,解決方案,假設(shè)有一棵如右圖所示的二叉樹(shù)，其四個(gè)葉子結(jié)點(diǎn)分別表示A、B、C和D四個(gè)字符，且約定左分支表示字符0，右分支表示字符1，則以由從根到葉子的路徑上的分支表示的字符組成的字符串作為該葉子結(jié)點(diǎn)字符的編碼。,106,比如：,假設(shè)電文總只有5個(gè)字符，且在電文中出現(xiàn)的頻率分別為

26、：5/29，6/29，2/29，9/29，7/29 則所構(gòu)造的最優(yōu)前綴編碼如下圖所示。,107,練習(xí),假定用于通信的電文僅由8個(gè)字母c1,c2,c3,c4,c5,c6,c7,c8組成，各字母在電文中出現(xiàn)的頻率分別為5，25，3，6，10，11，36，4。試為這8個(gè)字母設(shè)計(jì)不等長(zhǎng)的huffman編碼，并給出該電文的總編碼數(shù)。,108,采用動(dòng)態(tài)分配的順序存儲(chǔ)表示存儲(chǔ)赫夫曼樹(shù) 數(shù)組的大小為2n-1的一維數(shù)組,/赫夫曼樹(shù)和赫夫曼編碼的存儲(chǔ)表示 typedef struct unsigned int weight ; unsigned int parent , lchild , rchild; HTNo

27、de , * HuffmanTree ; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù) typedef char * HuffmanCode; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表,109,void HuffmanCoding( HuffmanTree ,110,/從葉子到根逆向獲得每個(gè)字符的赫夫曼編碼 HC = ( HuffmanCode) malloc( (n+1)*sizeof( char*); ch = ( char *) malloc( n*sizeof(char) ); /分配求編碼的工作空間 cd n-1 = “0”; /編碼結(jié)束符 for ( I =1; I=n; +i) /逐個(gè)字符求赫夫曼編碼 start = n-1; /從葉子到根逆向求編碼 for ( c=I , f = HTi.parent; f != 0; c=f, f = HTf.parent; ) if ( HTf.lchild = c ) cd -start = “0”; else cd