數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)ppt

1、樹(shù)的概念樹(shù)的遍歷及存儲(chǔ)二叉樹(shù) 二叉樹(shù)的遍歷 線索二叉樹(shù) 哈夫曼樹(shù)及其應(yīng)用,第七章 樹(shù)和二叉樹(shù),樹(shù)的遞歸定義 樹(shù)是由 n (n ? 0) 個(gè)結(jié)點(diǎn)組成的有限集合。如果 n = 0，稱(chēng)為空樹(shù)；如果 n > 0，則 ? 有一個(gè)特定的稱(chēng)之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)； ? 除根以外的其它結(jié)點(diǎn)劃分為 m (m ? 0) 個(gè) 互不相交的有限集合T0, T1, …, Tm-1

2、，每個(gè)集合又是一棵樹(shù)，并且稱(chēng)之為根的子樹(shù)。,樹(shù)的概念,樹(shù)的邏輯結(jié)構(gòu)?除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)。?所有結(jié)點(diǎn)可以有多個(gè)直接后繼。 1--多,樹(shù)的表示,(1) 樹(shù)形表示法。這是樹(shù)的最基本的表示,使用一棵倒置的樹(shù)表示樹(shù)結(jié)構(gòu),非常直觀和形象。下圖就是采用這種表示法。,(2) 文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。下圖就是樹(shù)的文氏圖表示法。,,(3) 凹入表示法。使用線段的伸縮描述樹(shù)

3、結(jié)構(gòu)。下圖是樹(shù)的凹入表示法。,,(4) 括號(hào)表示法。將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫(xiě)在括號(hào)中并用逗號(hào)間隔來(lái)描述樹(shù)結(jié)構(gòu)。下圖是樹(shù)的括號(hào)表示法。,,ADT Tree{ 數(shù)據(jù)對(duì)象: D={ai|1?i ? n, n ? 0, ai屬Elemtype類(lèi)型 數(shù)據(jù)關(guān)系: R1={| ai ,aj ?D, 1?i ? n, 1?j ? n, 每個(gè)元素只有一

4、個(gè)前驅(qū)可以有多個(gè)后繼} 基本運(yùn)算: InitTree(t); ClearTree(t); Parent(t,e); Sons(t,e); Traver(t);},抽象數(shù)據(jù)類(lèi)型數(shù)的定義,樹(shù)的基本常用術(shù)語(yǔ),層次 根為第1層 最大層數(shù)為樹(shù)的深度（高度）,雙親 (直接前驅(qū)） 孩子（直接后繼） 兄弟 堂兄弟 子孫 祖先,森林----m(m

5、>=0)棵互不相交的樹(shù)的集合。,d=3,d=0,度 一個(gè)結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。,度為零的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。,度不為零的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)。,樹(shù)中所有結(jié)點(diǎn)的度的最大值為樹(shù)的度。dmax=3,d=2,樹(shù)和森林的遍歷,深度優(yōu)先遍歷 先根次序遍歷 后根次序遍歷廣度優(yōu)先遍歷 按層次序遍歷,先根次序遍歷當(dāng)樹(shù)非空*訪問(wèn)根結(jié)點(diǎn)*依次先根遍歷根的各子樹(shù) D T1 T2 T3

6、 A,BEF,CG,DH IJ,先根次序遍歷森林依次先根遍歷各子樹(shù) T1 T2 T3,ABCDE,FG,HIKJ,樹(shù)和森林的遍歷,后根次序遍歷當(dāng)樹(shù)非空*依次后根遍歷根的各子樹(shù)*訪問(wèn)根結(jié)點(diǎn) T1 T2 T3 D A,EFB,GC,H IJD,后根次序遍歷森林

7、依次后根遍歷各子樹(shù) T1 T2 T3,BCEDA,GF,KIJH,樹(shù)和森林的遍歷,按層次序遍歷當(dāng)樹(shù)非空*自上向下依次遍歷每一層*每層從左向右訪問(wèn)結(jié)點(diǎn) 層次： 1 2 3,A,BCD,EFGH IJ,按層次序遍歷森林依次遍歷森林中各層結(jié)點(diǎn)層次： 1 2 3,AFH,BCDGIJ,EK,? 雙親表示,樹(shù)的存儲(chǔ)結(jié)構(gòu),A B

8、 C D E F G,-1 0 0 0 1 1 3,指向其雙親的位置,特點(diǎn)：很快確定雙親結(jié)點(diǎn),? 孩子表示法,每個(gè)結(jié)點(diǎn)擁有孩子的個(gè)數(shù)不同，所以采用單鏈表鏈接孩子結(jié)點(diǎn)。,孩子結(jié)點(diǎn)的序號(hào),指向下一個(gè)孩子結(jié)點(diǎn),指向第一個(gè)孩子結(jié)點(diǎn),ABCDEFG,?,?,?,?,1,2,3,4,5,6,typedef struct cnode{ int child; struct c

9、node *next;}link;,typedef struct{ datatype data; link *headptr;}ctree;ctree T[maxnode];,特點(diǎn)：很快確定孩子結(jié)點(diǎn) 但確定雙親效率低,,data parent headprt,-1000113,孩子雙親表示法,,?,?,?,?,?,?,?,?,? 孩子兄弟表示,指向第一個(gè)孩子結(jié)點(diǎn),指向右兄弟結(jié)點(diǎn)

10、,,,,,,定義： 一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。,二叉樹(shù) (Binary Tree),二叉樹(shù)的五種不同形態(tài),,度?2 有序樹(shù),？二叉樹(shù)與度為2的樹(shù)的區(qū)別,度 ?2 =2 序 有序 無(wú)序,分別有0個(gè) 1個(gè) 2個(gè) 3個(gè)4個(gè)結(jié)點(diǎn)的不同二叉樹(shù)如下,,n0 =1,n1 =1,n

11、2 =2,n3 =5,n4 =14,0個(gè),1個(gè),2個(gè),3個(gè),4個(gè),性質(zhì)2 深度為 k 的二叉樹(shù)至多有 2k-1個(gè)結(jié)點(diǎn)。(k ? 1),二叉樹(shù)的性質(zhì),性質(zhì)1 在二叉樹(shù)的第 i 層最多有 2i-1 個(gè)結(jié)點(diǎn)。(i ? 1),[證] （數(shù)學(xué)歸納法） i=1 , 2i-1 =20=1 。設(shè)i=j成立，即第j層至多2j-1個(gè)結(jié)點(diǎn)。 則j+1層，最多有2*2j-1= 2(j+1)-1

12、（由于每個(gè)最多有兩個(gè)后繼）,[證] 20 + 21 + … + 2k-1 = 2k-1,性質(zhì)3 對(duì)任何一棵二叉樹(shù), 若其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的結(jié)點(diǎn)個(gè)數(shù)為 n2, 則有 n0＝n2＋1。,完全二叉樹(shù) (Complete Binary Tree),滿二叉樹(shù) (Full Binary Tree),滿二叉樹(shù)和完全二叉樹(shù),深度為k且有2k-1個(gè)結(jié)點(diǎn)，所有分支結(jié)點(diǎn)的度為 2，

13、 n1=0 葉子結(jié)點(diǎn)都在最下一層。,葉子結(jié)點(diǎn)都在最下兩層，且最下一層集中在最左邊。,12 34 5 6 78 9 10 11 12 13 14 15,12 34 5 6 78 9 10,若按層次編號(hào)，則各結(jié)點(diǎn)的編號(hào)與其位置1-1對(duì)應(yīng)。,性質(zhì)4 具

14、有 n (n ? 0) 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 ?log2(n+1)? -1,[證]設(shè)完全二叉樹(shù)的高度為 k，則有： 2k-1 - 1 < n ? 2k - 1變形 2k-1 ? < n< 2k 取對(duì)數(shù) k-1 ? log2(n) < k 因此有 h = ?log2(n) ? +1,性質(zhì)5 一棵有n個(gè)結(jié)點(diǎn)的

15、完全二叉樹(shù)，若按層次結(jié)點(diǎn)編號(hào)，對(duì)于任一編號(hào)為i結(jié)點(diǎn)，則有： 若i = 1, 則結(jié)點(diǎn) i 無(wú)雙親 若i > 1, 則結(jié)點(diǎn)i 的雙親編號(hào)為?i /2? 若2*i<= n, 則結(jié)點(diǎn) i 的左孩子編號(hào)為 2*i 若2*i<= n, 則結(jié)點(diǎn) i 的右孩子編號(hào)為2*i +1,12 34 5 6 78 9 10,例：結(jié)點(diǎn)4的雙親

16、編號(hào)為2結(jié)點(diǎn)4的左孩子編號(hào)為8結(jié)點(diǎn)4的右孩子編號(hào)為9,由于（性質(zhì)5）完全二叉樹(shù)按層次編號(hào)后，可確定各結(jié)點(diǎn)與其雙親及孩子的關(guān)系，則完全二叉樹(shù)按編號(hào)次序進(jìn)行順序表示。,順序表示,二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),1 2 3 4 5 6 7 8 9 10,將一般二叉樹(shù)轉(zhuǎn)換為完全二叉樹(shù)（添加虛結(jié)點(diǎn)），然后按層次編號(hào)次序進(jìn)行順序表示。,A B C D E F G H I J,結(jié)點(diǎn)5： 雙親是結(jié)點(diǎn) 2 左孩子是結(jié)點(diǎn)

17、 10 沒(méi)有右孩子,結(jié)點(diǎn)E（6）： 雙親是結(jié)點(diǎn)C（3） 左孩子是結(jié)點(diǎn) I（12） 沒(méi)有右孩子（13為空）,完全二叉樹(shù),一般二叉樹(shù),指向左孩子結(jié)點(diǎn),指向右孩子結(jié)點(diǎn),二叉鏈表表示,,?,,,?,?,,,?,?,?,?,三叉鏈表表示,指向雙親結(jié)點(diǎn),typedef struct node { //二叉樹(shù)結(jié)點(diǎn)定義

18、 ElemType data; //結(jié)點(diǎn)數(shù)據(jù)域 struct node * lchild, * rchild; //左右孩子指針域} BTNode;BTNode *root; //根指針唯一確定二叉鏈表,二叉鏈表結(jié)點(diǎn)結(jié)構(gòu),數(shù)據(jù)類(lèi)型,二叉樹(shù)的遍歷,樹(shù)的遍歷就是按某種次序訪問(wèn)樹(shù)中的所有結(jié)點(diǎn)， 要求每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。

19、遍歷二叉樹(shù)三方面工作：訪問(wèn)根結(jié)點(diǎn)記作 D 遍歷根的左子樹(shù)記作 L 遍歷根的右子樹(shù)記作 R則可能的遍歷次序有： 前序 DLR 鏡像 DRL 中序 LDR 鏡像 RDL

20、 后序 LRD 鏡像 RLD,前序 DLR中序 LDR后序 LRD,前序遍歷二叉樹(shù)：若二叉樹(shù)非空，則訪問(wèn)根結(jié)點(diǎn) (D)前序遍歷左子樹(shù) (L)前序遍歷右子樹(shù) (R),void preorder ( BTNode *t ) { if ( t != NULL ) { visite (t->data); preorder ( t->

21、;lchild ); preorder ( t->rchild ); }},前序遍歷序列： D L R a,b d e,c f g,中序遍歷二叉樹(shù)：若二叉樹(shù)非空，則中序遍歷左子樹(shù) (L)訪問(wèn)根結(jié)點(diǎn) (D)中序遍歷右子樹(shù) (R),void inorder ( BTNode *t ) { if ( t != NULL ) { inorder

22、( t->lchild ); visite (t->data); inorder ( t->rchild ); }},中序遍歷序列： L D R a,d b e,c g f,后序遍歷二叉樹(shù)：若二叉樹(shù)非空，則后序遍歷左子樹(shù) (L)后序遍歷右子樹(shù) (R)訪問(wèn)根結(jié)點(diǎn) (D),后序遍歷序列： L R

23、D a,d e b,g f c,void postorder ( BTNode *t ) { if ( t != NULL ) { postorder ( t->lchild ); postorder ( t->rchild ); visite (t->data); }},應(yīng)用二叉樹(shù)遍歷的事例,表達(dá)式：a +

24、b * ( c - d ) - e / f,后綴表達(dá)式：,a b c d -* + e f / -,二叉樹(shù)表示表達(dá)式構(gòu)造原則：*兩個(gè)操作數(shù)分別作為左右子樹(shù)*運(yùn)算符作為根結(jié)點(diǎn),前序遍歷序列：- + a * b - c d / e f 中序遍歷序列：a + b * c - d - e / f 后序遍歷序列：a b c d - * + e f / -,在二叉樹(shù)中查找指定結(jié)點(diǎn),判斷根是否？根是成功,若不是，查找左子樹(shù),若左無(wú)，查找右子

25、樹(shù),？,,,? find(BTNode *b, elemtype x){ if(b==NULL) return(NULL); /*空樹(shù)*/ if ( b->data==x ) return(b); /*查找成功*/ p=find( b->lchild ,x); /*查找左子樹(shù)*/ if( p==NULL)

26、 p=find( b->rchild ,x); /*查找右子樹(shù)*/ return( p );},int leaf ( BTNode *b ) { if ( b == NULL ) return 0; if (?) return 1; nl=leaf( b->lchild ); nr=leaf( b->rchild );

27、 return nl+nr;},統(tǒng)計(jì)二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù),空樹(shù)：n=0,根是葉子：n=1,根是分支：n=nl+nr,？統(tǒng)計(jì)二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù)？統(tǒng)計(jì)二叉樹(shù)分支結(jié)點(diǎn)的個(gè)數(shù)？統(tǒng)計(jì)二叉樹(shù)度為2的個(gè)數(shù)？統(tǒng)計(jì)二叉樹(shù)度為1的個(gè)數(shù),0,0,0,0,0,0,1,1,1,1,1,0,0,2,3,構(gòu)造二叉樹(shù) 由二叉樹(shù)的前序序列和中序序列可唯一地確定一棵二叉樹(shù)。,利用pre[ ]存儲(chǔ)二叉樹(shù)的前序序列

28、 in[ ]存儲(chǔ)二叉樹(shù)的中序序列,構(gòu)造二叉樹(shù)立的基本思想：建立根結(jié)點(diǎn)，分別構(gòu)造左、右子樹(shù)。,前序序列 ABHFDECKG中序序列 HBDFAEKCG,ABHFDECKGHBDFAEKCG,右前序 ECKG 中序 EKCG,右前序 ECKG 中序 EKCG,無(wú)左,左前序 BHFD 中序 HBDF,左前序 BHFD 中序 HBDF,,左,,,左,,右,前序確定根中序分左右,建立子樹(shù)pre

29、[l1..h1]和in[l2..h2]：（1）建立根結(jié)點(diǎn)pre[l1]（2）在in[l2..h2]中確定根in[k]=pre[l1]（3）分別建立左右子樹(shù)， 并將左右孩子的指針填入根結(jié)點(diǎn),利用遞歸方法建立二叉樹(shù),參數(shù)？出口？,中序遍歷二叉樹(shù)的非遞歸算法,,,,,,,,,中序遍歷LDR基本思想：保存根結(jié)點(diǎn) 遍歷左子樹(shù) 取出根結(jié)點(diǎn)

30、 訪問(wèn)根結(jié)點(diǎn) 遍歷右子樹(shù),注：利用棧保存根結(jié)點(diǎn),,,,,,,,,,左空,右空,左空,右空,,f,b,d,a,中序遍歷序列： f b d a e c,d,a,e,c,b,f,設(shè)活動(dòng)指針p掃描每個(gè)結(jié)點(diǎn)當(dāng)p!= ? p入棧 p指向其左孩子當(dāng)p== ? 出棧p 訪問(wèn)p

31、 p指向其右孩子,設(shè)活動(dòng)指針p掃描每個(gè)結(jié)點(diǎn)當(dāng)p!= ? p入棧 p指向其左孩子當(dāng)p== ? 出棧p 訪問(wèn)p p指向其右孩子,inorder(BTNode *b){ BTNode *p; init(S); /*棧初始化*/ p=b; for( p!=NULL )

32、 { while(p!=NULL) {push(S,p);/*p入棧*/ p=p->lchild; /*進(jìn)入左子樹(shù)*/ } if(empty(S)) return; p=pop(S); /*出棧*/ visite(p); /*訪問(wèn)*/ p

33、=p->rchild; /*進(jìn)入右子樹(shù)*/ }},中序遍歷二叉樹(shù)的非遞歸算法,按層次遍歷二叉樹(shù),注：利用隊(duì)列保存結(jié)點(diǎn),,,,遍歷序列：a b c d e f g,a,a,a,b,b,b,c,c,c,d,d,d,e,e,e,f,f,f,g,g,g,按層次遍歷過(guò)程,隊(duì)列,隊(duì)頭：當(dāng)前訪問(wèn)的結(jié)點(diǎn)隊(duì)尾：保存當(dāng)前訪問(wèn) 的孩子結(jié)點(diǎn)操作過(guò)程： 取出隊(duì)頭作為當(dāng)前結(jié)點(diǎn) 訪

34、問(wèn)當(dāng)前結(jié)點(diǎn) 若有左孩子，則入隊(duì)列 若有右孩子，則入隊(duì)列,void layer(BTNode *b){ BTNode *p; init(Q); /*隊(duì)列初始化*/ enqueue(Q,b); while(!empty(Q)) { p=dequeue(Q); /*取對(duì)頭*/ visite(p); /*訪問(wèn)當(dāng)前結(jié)點(diǎn)*/

35、 if (p->lchild!=NULL) enqueue(Q,p->lchild); if (p->rchild!=NULL) enqueue(Q,p-rchild)； }},§6.4 線索二叉樹(shù),問(wèn)題：n個(gè)結(jié)點(diǎn)的二叉鏈表中， 每個(gè)結(jié)點(diǎn)有兩個(gè)指針域 ， 共2n個(gè)指針域，空指

36、針域？,n=8 共16個(gè)指針域空指針域：9,n+1,[證] 設(shè)二叉樹(shù)中度分別為0、1和 2 的結(jié)點(diǎn)個(gè)數(shù)為n0、n1和n2。 空指針域?yàn)?n1+2n0 由于：n0=n2+1 n= n0+n1+n2 則：n1+2n0= n1+ n0 + n0 = n1+

37、n0 + n2 + 1 = n + 1,為了充分利用存儲(chǔ)空間，在空指針域填上線索，即：*若無(wú)左孩子，則lchild指向某種遍歷的前驅(qū)；*若無(wú)右孩子，則rchild指向某種遍歷的后繼；,中序遍歷序列：EBIFJACG,,,,,,,,?,?,中序線索二叉樹(shù),dbeacgf,前序線索二叉樹(shù),abdecfg,后序線索二叉樹(shù),debgfca,,,,,,,二叉樹(shù)線索化,線索二叉樹(shù)

38、的結(jié)點(diǎn)結(jié)構(gòu),typedef struct node{ ElemType data; int ltag,rtag; struct node *lchild,*rchild;}TBTNode;,前序線索樹(shù),前序遍歷序列：abdgcef,中序線索樹(shù),中序遍歷序列：dgbaecf,后序線索樹(shù),后序遍歷序列：gdbaefc,線索二叉樹(shù)的遍歷,求指定結(jié)點(diǎn)p的后繼qp->rtag=1:,q=p->

39、rchild,p->rtag=0:,中序遍歷序列： dgbaecf,q=p->rchild;while(q->ltag==0) q=q->lchild;,右子樹(shù)左下角的結(jié)點(diǎn),建立線索二叉樹(shù),主要操作過(guò)程：*建立一般的二叉鏈表*通過(guò)遍歷進(jìn)行線索化 設(shè)p為當(dāng)前處理結(jié)點(diǎn) pre為p的前驅(qū)填標(biāo)志：若p無(wú)左：p->ltag=1若p無(wú)右：p->rtag=1填線索：

40、若p->ltag==1: p->lchild=pre;若pre->rtag==1: pre->rchild=p;,bithptr *pre=NULL;inthread(TBTNode *p){ if(p!=NULL) { inthread(p->lchild); if(p->lchild==NULL)

41、 {p->ltag=1; p->lchild=pre;} if(p->rchild==NULL) p->rtag=1; if(pre!=NULL &&pre->rtag==1) pre->rchild=p;

42、 pre=p; inthread(p->rchild); }},,,,,樹(shù)和森林與二叉樹(shù)的相互轉(zhuǎn)換,樹(shù)轉(zhuǎn)換成二叉樹(shù),*第一個(gè)孩子作為左孩子*右兄弟作為右孩子,,,,,,,,森林轉(zhuǎn)換成二叉樹(shù),樹(shù)和森林與二叉樹(shù)的相互轉(zhuǎn)換,*依次將每棵樹(shù) 轉(zhuǎn)換成二叉樹(shù),*第一棵樹(shù)的根 作為二叉樹(shù)的根*從第二棵樹(shù)到 最后一棵樹(shù)的根， 依次作為前一棵 樹(shù)根的右孩子,,,二叉樹(shù)

43、轉(zhuǎn)換為樹(shù)或森林,樹(shù)和森林與二叉樹(shù)的相互轉(zhuǎn)換,*左孩子作為第一個(gè)孩子*左孩子的右孩子作為第二個(gè)孩子*左孩子的右孩子的右孩子作為第三個(gè)孩子………………..,,,,,,*根作為第一棵樹(shù)的根*根的右孩子作為第二棵樹(shù)的根*根的右孩子的右孩子作為第三棵樹(shù)的根………………..,遍歷二叉樹(shù)前序遍歷序列：中序遍歷序列：后序遍歷序列：,遍歷森林先根遍歷序列：后根遍歷序列：,,樹(shù)和森林與二叉樹(shù)的相互轉(zhuǎn)換,abdgiecfh,dgibea

44、fhc,igdebhfca,abdgiecfh,dgibeafhc,二叉樹(shù),樹(shù)或森林,前序==先根,中序==后根,哈夫曼樹(shù) (Huffman Tree),樹(shù)的應(yīng)用舉例,帶權(quán)路徑長(zhǎng)度 (Weighted Path Length, WPL) 擴(kuò)充二叉樹(shù)的帶權(quán) (外部) 路徑長(zhǎng)度是樹(shù)的各葉結(jié)點(diǎn)所帶的權(quán)值 wi 與該結(jié)點(diǎn)到根的路徑長(zhǎng)度 li 的乘積的和，即：,WPL=2*1+4*2+6*3+7*3+8*4

45、=81,具有相同的帶權(quán)葉子有多種不同的二叉樹(shù),WPL = 2*2+4*2 +5*2+7*2 = 36,WPL = 2*1+4*2 +5*3+7*3 = 46,WPL = 7*1+5*2 +2*3+4*3 = 35,帶權(quán)(外部)路徑長(zhǎng)度達(dá)到最小,,哈夫曼樹(shù) (Huffman Tree),哈夫曼樹(shù)帶權(quán)路徑

46、長(zhǎng)度達(dá)到最小的擴(kuò)充二叉樹(shù)。哈夫曼樹(shù)的特點(diǎn)：權(quán)值大的結(jié)點(diǎn)離根最近。,,,,,(1) 初始狀態(tài)：構(gòu)造具有 n 棵二叉樹(shù)的森林 F = { T1, …, Tn}，其中每棵二叉樹(shù) Ti 只有一 個(gè)帶權(quán)值 wi 的根結(jié)點(diǎn)。,哈夫曼樹(shù) (Huffman Tree),霍夫曼樹(shù)的構(gòu)造過(guò)程,F : {7，5，2，4},(2) 重復(fù)合并:直到 剩一棵樹(shù)① 在 F 中選取兩棵根的權(quán)值最小的二叉樹(shù), 做為左、右子樹(shù)合并成一棵新二叉樹(shù)。置新的二叉樹(shù)的根

47、結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。② 在 F 中刪去這兩棵二叉樹(shù)。③ 把新的二叉樹(shù)加入 F。,7 0 0 05 0 0 02 0 0 04 0 0 0 0

48、 0 0 0 0 0 0 0 0,哈夫曼樹(shù) (Huffman Tree),注：m個(gè)葉子，經(jīng)m-1次合并，產(chǎn)生m-1分支結(jié)點(diǎn)，則哈夫曼共有2m-1個(gè)結(jié)點(diǎn)。,*,*,5,5,6,3,4,*,6,*,11,6,6,2,5,*,*,18,7,7,1,head編碼:,哈夫曼編碼,{ 5, 29, 7

49、, 8, 14, 23, 3, 11 },*不能出現(xiàn)重碼*不能出現(xiàn)一個(gè)編碼是另一個(gè)編碼的前綴。,a b c d e f g h,a,b,c,d,e,f,g,h,a :0001b :10c :1110d :1111,e :110 f :01 g :0000h :001,001,110,0001,1111,0100011110110譯碼：,01,0001,1110,110,f,a,c,e,設(shè)左分支

50、為0，右分支為1。,權(quán)值為各字母出現(xiàn)的頻率,電報(bào)碼要求：,判定樹(shù),WPL=0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15,最佳判定樹(shù),考試成績(jī)分布表,最佳判定樹(shù),WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = 0.3+0.45+0.5+0.7+0.3 = 2.25,考試成績(jī)分布表,小 結(jié),一、樹(shù)的定義（遞歸）、樹(shù)的邏輯結(jié)構(gòu)（1-多）。二、樹(shù)

51、的常用術(shù)語(yǔ)：結(jié)點(diǎn)的度、樹(shù)的度。 樹(shù)的層次、樹(shù)的高度。 雙親結(jié)點(diǎn)、孩子結(jié)點(diǎn)、子孫、祖先。 森林。三、樹(shù)的存儲(chǔ)方式：雙親表示法、孩子表示法及孩子兄弟表示法。四、樹(shù)的遍歷：先根遍歷、后根遍歷及按層次遍歷。五、二叉樹(shù)的定義及二叉樹(shù)的基本形式。六、二叉樹(shù)的五個(gè)基本性質(zhì)。七、二叉樹(shù)的存儲(chǔ)方式：順序方式、二叉鏈表及三叉鏈表。八、二叉