《樹(shù)與二叉樹(shù) 》PPT課件.ppt

,第八章 樹(shù)與二叉樹(shù),1.樹(shù)的定義及其基本概念,2.二叉樹(shù)的基本概念和存儲(chǔ)結(jié)構(gòu),3.二叉樹(shù)的遍歷,4.線索二叉樹(shù)的概念及其遍歷,6.哈夫曼樹(shù)及其構(gòu)造方法,7.樹(shù)與森林,5.二叉排序樹(shù),8.1 樹(shù)的概念和基本術(shù)語(yǔ),一、樹(shù)的定義 樹(shù)是由 n (n 0) 個(gè)結(jié)點(diǎn)的有限集合。如果 n = 0，稱為空樹(shù)；如果 n 0，則 有且僅有一個(gè)特定的稱之為根(Root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)； 當(dāng)n 1，除根以外的其它結(jié)點(diǎn)劃分為 m (m 0) 個(gè)互不相交的有限集 T1, T2 , Tm，其中每個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)(SubTree)。,根,子樹(shù),特點(diǎn)：樹(shù)中至少有一個(gè)結(jié)點(diǎn)根 樹(shù)中各子樹(shù)是互不相交的集合,二、樹(shù)的表示,1樹(shù)形結(jié)構(gòu)表示法,2. 凹入法表示法,3. 嵌套集合表示法（文氏圖表示法）,4.廣義表表示法（括號(hào)表現(xiàn)法） 對(duì)樹(shù)結(jié)構(gòu)，廣義表表示法可表示為： (A(B(E(J，K，L)，F(xiàn))，C(G)，D(H(M)，I),分支(branch)：結(jié)點(diǎn)之間的二元關(guān)系（序偶）。 結(jié)點(diǎn)(node)：一個(gè)數(shù)據(jù)元素及指向其子樹(shù)的分支。 結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)。 葉結(jié)點(diǎn)(leaf)：度為零的結(jié)點(diǎn)。 分支結(jié)點(diǎn)(branch node):有后繼的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。 兒子(sons)：結(jié)點(diǎn)x的子樹(shù)的根。 父親(parent):結(jié)點(diǎn)x的前驅(qū)結(jié)點(diǎn)稱為x的父親。 兄弟(brother)：同一父親的結(jié)點(diǎn)的子女結(jié)點(diǎn)。 祖先(ancestor)：根到該結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)。 子孫(descendant)：某結(jié)點(diǎn)為根的子樹(shù)上的任意結(jié)點(diǎn)。 堂兄弟(cousin):父親是兄弟關(guān)系或堂兄弟關(guān)系的結(jié)點(diǎn)。,結(jié)點(diǎn)層次(level)：從根開(kāi)始，根為第一層，根的子女為第二層，以此類推。 樹(shù)的深度（高度）(depth)：樹(shù)中結(jié)點(diǎn)的最大層次數(shù) 樹(shù)的度：一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)。 結(jié)點(diǎn)按層編號(hào)（層中編號(hào)）：將樹(shù)中結(jié)點(diǎn)按從上層到下層，同層從左到右的次序排成一個(gè)線性序列，依次給他們編以連續(xù)的自然數(shù)。 祖輩（上層）：層號(hào)比結(jié)點(diǎn)x小的結(jié)點(diǎn)，稱為x的祖輩。 后輩（下層）：層號(hào)比結(jié)點(diǎn)x大的結(jié)點(diǎn)，稱為x的后輩。 有序樹(shù)：若一棵樹(shù)中所有子樹(shù)從左到右的排序是有順序的，不能顛倒次序。稱該樹(shù)為有序樹(shù)。 無(wú)序樹(shù)：若一棵樹(shù)中所有子樹(shù)的次序無(wú)關(guān)緊要，則稱為無(wú)序樹(shù)。 森林(forest)：m(m 0)棵互不相交的樹(shù)。,三、樹(shù)的基本術(shù)語(yǔ),1層,2層,4層,3層,height = 4,A,C,G,B,D,E,F,K,L,H,M,I,J,結(jié)點(diǎn) 結(jié)點(diǎn)的度 葉結(jié)點(diǎn) 分支結(jié)點(diǎn),子女 雙親 兄弟,祖先 子孫 結(jié)點(diǎn)層次,樹(shù)的深度 樹(shù)的度 有序樹(shù) 無(wú)序樹(shù) 森林,結(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的父親：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的祖先,8.2 二叉樹(shù) (Binary Tree),定義:,五種形態(tài):,一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。,特點(diǎn):,每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)（二叉樹(shù)中 不存在度大于2的結(jié)點(diǎn)）,二叉樹(shù)的基本操作,（1）creat_tree(bt,str) 根據(jù)二叉樹(shù)的括號(hào)表示法str建立一棵二叉樹(shù)bt。 （2）disptree(bt) 以凹入法顯示一棵二叉樹(shù)bt。 （3）depth_bttree(bt) 求一棵二叉樹(shù)bt的深度。 （4）count_bttree(bt) 求一棵二叉樹(shù)bt的結(jié)點(diǎn)個(gè)數(shù)。 （5）leafcount_bttree(bt) 求一棵二叉樹(shù)bt的葉子結(jié)點(diǎn)個(gè)數(shù)。 （6）nleafcount_bttree(bt) 求一棵二叉樹(shù)bt 的非葉子結(jié)點(diǎn)個(gè)數(shù)。,性質(zhì)1 在二叉樹(shù)的第 i 層上至多有 2i 1個(gè)結(jié)點(diǎn)。(i 1) 證明用歸納法 證明：當(dāng)i=1時(shí)，只有根結(jié)點(diǎn)，2 i-1=2 0=1。 假設(shè)對(duì)所有j，ij1，命題成立，即第j層上至多有2 j-1 個(gè)結(jié)點(diǎn)。 由歸納假設(shè)第i-1 層上至多有 2i 2個(gè)結(jié)點(diǎn)。 由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度至多為2，故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍，即2* 2i 2= 2 i-1。,二叉樹(shù)的性質(zhì),性質(zhì)2 深度為 k 的二叉樹(shù)至多有 2k -1個(gè)結(jié)點(diǎn)(k 1)。 證明：由性質(zhì)1可見(jiàn)，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為,性質(zhì)3 對(duì)任何一棵二叉樹(shù)T, 如果其葉結(jié)點(diǎn)數(shù)為 n0, 度為2的結(jié)點(diǎn)數(shù)為 n2,則n0n21. 證明：若度為1的結(jié)點(diǎn)有 n1 個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為 n，總邊數(shù)為 e，則根據(jù)二叉樹(shù)的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,定義1 滿二叉樹(shù) (Full Binary Tree) 一棵深度為k且有2k -1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。,兩種特殊形態(tài)的二叉樹(shù),非完全二叉樹(shù),定義2 完全二叉樹(shù) (Complete Binary Tree) 若設(shè)二叉樹(shù)的高度為h，則共有h層。除第 h 層外，其它各層 (0 h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)。,完全二叉樹(shù),性質(zhì)4 具有 n (n 0) 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2(n) 1 證明： 設(shè)完全二叉樹(shù)的深度為 h，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義有 2h1 - 1 n 2h - 1或 2h1 n 2h 取對(duì)數(shù) h1 log2n h，又h是整數(shù)， 因此有 h = log2(n) 1,性質(zhì)5 如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào) 1, 2, , n，則有以下關(guān)系： 若i = 1, 則 i 無(wú)雙親 若i 1, 則 i 的雙親為(i /2) 若2*i n, 則 i 無(wú)左孩子,否則其左孩子是結(jié)點(diǎn)2i. 若2*i+1n,則結(jié)點(diǎn)i無(wú)右孩子,否則其右孩子為結(jié)點(diǎn)2*i+1,完全二叉樹(shù) 一般二叉樹(shù) 的順序表示 的順序表示,8.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),一、順序表示,二、鏈表表示,二叉樹(shù)鏈表表示的示例,二叉樹(shù) 二叉鏈表 三叉鏈表,typedef struct btnode struct btnode *lchild; int data; struct btnode *rchild; bitnode,*bitree;,二叉鏈表的定義,若一個(gè)二叉樹(shù)含有n個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必含有2n個(gè)指針域，其中必有n+1個(gè)空鏈域。 證明：邊數(shù)e=n-1;即非空鏈域?yàn)閚-1個(gè)，則空鏈域?yàn)?n-(n-1)=n+1個(gè)。,三、二叉鏈表的遞歸創(chuàng)建及其基本操作的實(shí)現(xiàn),char s= ,a,b,c,d, , ,e,f,g, , , , ,h,I; root =creat_tree(s,1); bitree creat_tree(char *s,int p) bitree new; if(sp= |p15) return NULL; else new=(bitree)malloc(sizeof(bitree); new-data=sp; new-lchild=creat_tree(s,2*p); new-rchile=creat_tree(s,2*p+1); return new; ,8.4 二叉樹(shù)遍歷,樹(shù)的遍歷就是按某種次序訪問(wèn)樹(shù)中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。 設(shè)訪問(wèn)根結(jié)點(diǎn)記作 V 遍歷根的左子樹(shù)記作 L 遍歷根的右子樹(shù)記作 R 則可能的遍歷次序有 前序 VLR 中序 LVR 后序 LRV,中序遍歷二叉樹(shù)算法的定義： 若二叉樹(shù)為空，則空操作； 否則 中序遍歷左子樹(shù) (L)； 訪問(wèn)根結(jié)點(diǎn) (V)； 中序遍歷右子樹(shù) (R)。 遍歷結(jié)果 a + b * c - d - e / f,中序遍歷 (Inorder Traversal),void inorder (bitree bt) if (bt!= NULL ) inorder ( bt-lchild ); printf(“ %c”,bt-data); inorder ( bt-rchild ); ,中序遍歷二叉樹(shù)的遞歸算法,前序遍歷二叉樹(shù)算法的定義： 若二叉樹(shù)為空，則空操作； 否則 訪問(wèn)根結(jié)點(diǎn) (V)； 前序遍歷左子樹(shù) (L)； 前序遍歷右子樹(shù) (R)。 遍歷結(jié)果 - + a * b - c d / e f,前序遍歷 (Preorder Traversal),前序遍歷二叉樹(shù)的遞歸算法 void preorder (bitree bt) if (bt!= NULL ) printf(“ %c”,bt-data); preorder ( bt-lchild ); preorder (bt-rchild ); ,后序遍歷二叉樹(shù)算法的定義： 若二叉樹(shù)為空，則空操作； 否則 后序遍歷左子樹(shù) (L)； 后序遍歷右子樹(shù) (R)； 訪問(wèn)根結(jié)點(diǎn) (V)。 遍歷結(jié)果 a b c d - * + e f / -,后序遍歷 (Postorder Traversal),后序遍歷二叉樹(shù)的遞歸算法： void postorder (bitree bt) if ( bt != NULL ) postorder ( bt-lchild ); postorder ( bt-rchild ); printf(“ %c”,bt-data); ,非遞歸實(shí)現(xiàn)先序遍歷二叉樹(shù) 利用一個(gè)一維數(shù)組作為棧，來(lái)存儲(chǔ)二叉鏈表中結(jié)點(diǎn)，算法思想為： 1、從二叉樹(shù)根結(jié)點(diǎn)開(kāi)始，先將根結(jié)點(diǎn)入棧。 2、然后將棧頂結(jié)點(diǎn)出棧，輸出結(jié)點(diǎn)的值，同時(shí)判斷該結(jié)點(diǎn)有沒(méi)有右子樹(shù)，有則將右子樹(shù)的根結(jié)點(diǎn)入棧；再判斷有沒(méi)有左子樹(shù)，有則將左子樹(shù)的根結(jié)點(diǎn)入棧。如果棧不空則重復(fù)第2步，直到棧為空。,void preorder (bitree root) bitree p, stack100; int top=-1; /top為棧頂指針 if(root!=NULL) top+; stacktop=root;/將根結(jié)點(diǎn)壓入棧內(nèi) while(top!=-1) p=stacktop; top-; printf(“%d ”,p-data); if(p-rchild!=NULL) stack+top=p-rchlid; /壓右子樹(shù) if(p-lchild!=NULL) stack+top=p-lchild; /壓左子樹(shù) ,非遞歸實(shí)現(xiàn)中序遍歷二叉樹(shù) 同樣利用一個(gè)一維數(shù)組作棧，來(lái)存貯二叉鏈表中結(jié)點(diǎn)，算法思想為： 1、將所指的結(jié)點(diǎn)的左子樹(shù)入棧，其下面的左子樹(shù)也入棧 2、彈出一個(gè)結(jié)點(diǎn)并輸出，判斷其是否有右子樹(shù)，有則入棧，再轉(zhuǎn)到第1步，沒(méi)有右子樹(shù)則判斷棧是否為空，不空則彈出一個(gè)結(jié)點(diǎn)，轉(zhuǎn)回第2步，為空則結(jié)束。,void inorder ( bitree root) bitree p=root,stack100; /s為一個(gè)棧，top為棧頂指針 int top=-1; do while(p!=NULL) top+; stacktop=p; p=p-lchild; if(top=0) p=stacktop; top-; printf(“%d ”,p-data); p=p-rchild; while(p!=NULL|top=0); ,非遞歸實(shí)現(xiàn)后序遍歷二叉樹(shù) 在后序遍歷中，當(dāng)搜索指針指向某一個(gè)結(jié)點(diǎn)時(shí)，不能馬上進(jìn)行訪問(wèn)，而先要遍歷左子樹(shù)，所以此結(jié)點(diǎn)應(yīng)先進(jìn)棧保存，當(dāng)遍歷完它的左子樹(shù)后，再次回到該結(jié)點(diǎn)，還不能訪問(wèn)它，還需先遍歷其右子樹(shù),所以該結(jié)點(diǎn)還必須再次進(jìn)棧，只有等它的右子樹(shù)遍歷完后，再次退棧時(shí)，才能訪問(wèn)該結(jié)點(diǎn)。 為了區(qū)分同一結(jié)點(diǎn)的三次進(jìn)棧及出棧，引入一個(gè)棧次數(shù)的標(biāo)志，一個(gè)元素第一次進(jìn)棧標(biāo)志為1，第二次進(jìn)標(biāo)志為2，第三次進(jìn)棧標(biāo)志為3，并將標(biāo)志同時(shí)存入棧中，當(dāng)出棧的元素的標(biāo)志為3時(shí)，才輸出此結(jié)點(diǎn)。,struct forpost int sign; bitnode *treenode; void postorder(bitnode *root) forpost stack100,p,q; int top=0,i; p.treenode=root; p.sign=1; stacktop=p; top+;/將根結(jié)點(diǎn)入棧,while(top!=0) top-; p=stacktop; if(p.treenode!=NULL) if(p.sign=1) q.treenode=p.treenode; q.sign=2; stacktop+=q; q.treenode=p.treenode-lchild; q.sign=1; stacktop+=q; if(p.sign=2) q.treenode=p.treenode; q.sign=3; stacktop+=q; q.treenode=p.treenode-rchild; q.sign=1; stacktop+=q; if(p.sign=3) printf(“%dt”,p.treenode-data); ,線索二叉樹(shù)的引入： 對(duì)二叉樹(shù)遍歷的過(guò)程實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化的操作。以二叉鏈表為存儲(chǔ)結(jié)構(gòu)時(shí),結(jié)點(diǎn)的左右孩子可以直接找到,但不能直接找到結(jié)點(diǎn)的前驅(qū)和后繼,而結(jié)點(diǎn)的前驅(qū)和后繼只有在遍歷二叉樹(shù)的過(guò)程中才能得到。 用二叉鏈表表示的二叉樹(shù)中,n個(gè)結(jié)點(diǎn)的二叉樹(shù)有n+1個(gè)空鏈域，可利用這些空鏈域存儲(chǔ)結(jié)點(diǎn)的前驅(qū)或后繼。,8.5 線索二叉樹(shù) (Threaded Binary Tree),ltag=0, lchild為左孩子指針 ltag=1, lchild為前驅(qū)線索 rtag=0, rchild為右孩子指針 rtag=1, rchild為后繼線索,typedef struct bithrnode elemtype data; /*數(shù)據(jù)域*/ struct bithrnode *lchild，*rchild; /*左右指針*/ ptrtag ltag,rtag;/*左右標(biāo)志*/ bithrnode,*bithrtree;,線索二叉樹(shù) 中結(jié)點(diǎn)的定義,線索二叉樹(shù)的創(chuàng)建和遍歷,中序構(gòu)造線索二叉樹(shù)算法思想: 對(duì)二叉樹(shù)一邊中序遍歷一邊建線索,若訪問(wèn)結(jié)點(diǎn)的左孩子為空,建立前趨線索;若右孩子為空,建立后繼線索。 并且在二叉樹(shù)的線索鏈表上也添加一個(gè)頭結(jié)點(diǎn)，并令其lchild域的指針指向二叉樹(shù)的根結(jié)點(diǎn)，其rchild域的指針指向中序序列的最后一個(gè)結(jié)點(diǎn)；反之，令二叉樹(shù)的中序序列的第一個(gè)結(jié)點(diǎn)的lchild域指針和最后一個(gè)結(jié)點(diǎn)rchild域的指針均指向頭結(jié)點(diǎn)。,先序序列為：ABCD,中序序列為：BADC,后序序列為：BDCA,void inthread(bithrtree p,bithrtree pre) if(p) inthread(p-lchild,pre)/左子樹(shù)線索化 if(p-lchild=NULL) p-ltag=1; p-lchild=pre;/產(chǎn)生前驅(qū) if(p-rchild=NULL) pre-rtag=1; pre-rchild=p;/產(chǎn)生后繼 pre=p;/保持pre指向p的前驅(qū) inthread(p-rchild,pre);/右子樹(shù)線索化 ,遍歷中序線索二叉樹(shù)算法思想： 先判斷指針域是用作線索還是指向子樹(shù)，再?zèng)Q定是否進(jìn)行遞歸調(diào)用。 bithrtree inorder_thread(bithrtree t) bithrtree thrt,pre,p; thrt=(bithrtree)malloc(sizeof(bithrnode); thrt-ltag=0;thrt-rtag=1; thrt-rchild=thrt; if(t=NULL) thrt-lchild=thrt; else p=thrt-lchild=t; thrt-ltag=0; pre=thrt; inthread(p,pre); pre-rtag=1; thrt-rchild=pre; thrt-rtag=1; return thrt;,8.6 二叉排序樹(shù),二叉排序樹(shù)（二叉查找樹(shù)）是一種特殊的二叉樹(shù)，一般二叉樹(shù)中只區(qū)分左、右子樹(shù)，但不區(qū)分結(jié)點(diǎn)的順序，在二叉排序樹(shù)中，所有結(jié)點(diǎn)都是有序的。 特征： （1）若它左子樹(shù)非空，則左子樹(shù)上的所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字。 （2）若它右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字。 （3）左、右子樹(shù)本身各又是一個(gè)二叉排序樹(shù)。,利用二叉排序樹(shù)進(jìn)行查找，算法比較簡(jiǎn)單 如想查找數(shù)據(jù)6，先和根5比較，轉(zhuǎn)到右子樹(shù)上查找，再比較7，轉(zhuǎn)左子樹(shù)上，就找到了6。即為查找算法中的二分查找法。,二叉查找樹(shù)的查找 bitree binary_traverse_search(bitree p,int v) while(p!=NULL) if(p-data=value) return p; else if(p-datav) p=p-lchild; else p=p-rchild; return NULL; ,main() bitree root=NULL,p; int v,s16=0,5,4,7,2,0,6,8,1,3,0,0,0,0,0,0; root=creat_tree(s,1); printf(“請(qǐng)輸入要查找的結(jié)點(diǎn)的值：n”); scanf(“%d”, ,8.7 哈夫曼樹(shù) (Huffman Tree),一、哈夫曼 (Huffman)樹(shù),又稱最優(yōu)樹(shù),是一類帶權(quán)路徑長(zhǎng)度最短的樹(shù) 1路徑和路徑長(zhǎng)度 在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。 2結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度 若將樹(shù)中結(jié)點(diǎn)賦予一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。,3樹(shù)的帶權(quán)路徑長(zhǎng)度 樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和， 記為wpl= ，其中n 為葉子結(jié)點(diǎn)數(shù)目，wi為第i 個(gè)葉子結(jié)點(diǎn)的權(quán)值，li 為第i 個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。,WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35,帶權(quán)路徑長(zhǎng)度達(dá)到最小,哈夫曼樹(shù),樹(shù)的帶權(quán)路徑長(zhǎng)度達(dá)到最小的二叉樹(shù)即為哈夫曼樹(shù)。 在哈夫曼樹(shù)中，權(quán)值大的結(jié)點(diǎn)離根最近。,(1) 由給定的 n 個(gè)權(quán)值 w0, w1, w2, , wn-1，構(gòu)造具有 n 棵擴(kuò)充二叉樹(shù)的森林 F = T0, T1, T2, , Tn-1 ，其中每棵擴(kuò)充二叉樹(shù) Ti 只有一 個(gè)帶權(quán)值 wi 的根結(jié)點(diǎn), 其左、右子樹(shù)均為空。,二、哈夫曼樹(shù)的構(gòu)造算法,(2) 重復(fù)以下步驟, 直到 F 中僅剩下一棵樹(shù)為止： 在 F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹(shù), 做為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)。置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。 在 F 中刪去這兩棵二叉樹(shù)。 把新的二叉樹(shù)加入 F。,哈夫曼樹(shù)的構(gòu)造過(guò)程,例 w=5, 29, 7, 8, 14, 23, 3, 11,三、哈夫曼樹(shù)的應(yīng)用-哈夫曼編碼,在傳送電文時(shí),總是希望傳送的時(shí)間盡可能短，如果每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，且能讓出現(xiàn)頻率高的采用盡可能短的編碼，則傳送的電文長(zhǎng)度就會(huì)縮短。 例如：需要傳送的電文為“ABACCDA”,如果設(shè)計(jì)A、B、C、D的編碼分別為0 、00、1和01，則上述7個(gè)字符的電文就轉(zhuǎn)換成為長(zhǎng)度為9個(gè)字符串“000011010”。,前綴編碼：設(shè)計(jì)長(zhǎng)短不等的編碼，必須使任何一個(gè)字符都不是另一個(gè)字符的前綴，這樣保證譯碼的唯一性。,哈夫曼編碼,主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮。,設(shè)給出一段報(bào)文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各字符出現(xiàn)概率為 C:2/18, A:7/18, S:4/18, T:5/18 ,化整為 2, 7, 4, 5 。 若給每個(gè)字符以等長(zhǎng)編碼 A : 00 T : 10 C : 01 S : 11 則總編碼長(zhǎng)度為 ( 2+7+4+5 ) * 2 = 36.,若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，盡可能減少總編碼長(zhǎng)度。 各字符出現(xiàn)概率為 2, 7, 4, 5 。以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值, 建立哈夫曼樹(shù)。左分支賦 0，右分支賦 1，得哈夫曼編碼(變長(zhǎng)編碼)。,CAST CAST SAT AT A TASA A : 0 T : 10 C : 110 S : 111 它的總編碼長(zhǎng)度：7*1+5*2+( 2+4 )*3 = 35。比等長(zhǎng)編碼的情形要短。 總編碼長(zhǎng)度正好等于哈夫 曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。 哈夫曼編碼是一種無(wú)前綴 編碼(都由葉結(jié)點(diǎn)組成,路徑 不會(huì)重復(fù))。解碼時(shí)不會(huì)混淆。 哈夫曼編碼: A : 0 T : 10 C : 110 S : 111 110011110 11001111011101001001001110 等長(zhǎng)編碼: A : 00 T : 10 C : 01 S : 11 010011100100111011001000100010001100,#define MAX 50 typedef struct char data; int weight; int parent; int left; int right; int flag;huffnode; huffnode ht2*MAX;,int select(int i) int k=32767,j,q; for(j=0;j=i;j+) if(htj.weightk,void creat_hufftree(int n) int i,k,l,r; for(i=0;i2*n-1;i+) hti.parent=hti.left=hti.right=hti.flag=-1; for(i=n;i2*n-1;i+) l=select(i-1); r=select(i-1); htl.parent=i ; htr.parent=i; hti.weight=htl.weight+htr.weight; hti.left=l; hti.right=r; ,哈夫曼編碼算法： 在建好的哈夫曼樹(shù)中求哈夫曼編碼，實(shí)質(zhì)上就是從葉結(jié)點(diǎn)開(kāi)始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過(guò)了哈夫曼樹(shù)的一個(gè)分支，從而得到一位哈夫曼碼值。 這樣求得的碼是從低位到高位，可以設(shè)置一結(jié)構(gòu)體數(shù)組huffcode來(lái)存放各字符的哈夫曼編碼。其結(jié)構(gòu)如下：,其中cd是一維數(shù)組用來(lái)存放編碼，start表示該編碼在數(shù)組cd中的開(kāi)始位置。對(duì)于第i個(gè)字符，它的編碼存放在huffcodei.cd中的從huffcodei.start到n的分量上。,typedef struct char cdMAX; int start;huffcode; huffcode hcdMAX;,w parent l r flag,0 1 2 3 4 5 6,creat_huffcode(int n) int i,f,c; huffcode d; for(i=0;in;i+) d.start=n+1; c=i; f=hti.parent; while(f!=-1) if(htf.left=c) d.cd-d.start=0; else d.cd-d.start=1; c=f; f=htf.parent; hcdi=d; ,void display_huffcode(int n) int i,k; printf(“輸出哈夫曼編碼：n”); for(i=0;in;i+) printf(“%c:”,hti.data); for(k=hcdi.start;k=n;k+) printf(“%c”,hcdi.cdk); printf(“n”); ,一、樹(shù)的存儲(chǔ)結(jié)構(gòu) 1、雙親表示：以一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在結(jié)點(diǎn)中附設(shè)一個(gè)指針，存放雙親結(jié)點(diǎn)在鏈表中的位置。該方法利用每個(gè)結(jié)點(diǎn)只有一個(gè)雙親的特點(diǎn)，可以很方便求結(jié)點(diǎn)的雙親，但不方便求結(jié)點(diǎn)的孩子。,8.8 樹(shù)與森林,用雙親表示實(shí)現(xiàn)的樹(shù)定義,typedef struct char data; int parent; ptnode; typedef struct ptnode nodesMAXSIZE; int nodenum; pttree;,A,B,C,D,E,F,G,2、孩子表示法(多重鏈表),第一種解決方案 等數(shù)量的鏈域 (d為樹(shù)的度),第二種解決方案 孩子鏈表,將每個(gè)結(jié)點(diǎn)的孩子鏈在該結(jié)點(diǎn)之后組成鏈表，再將所有頭結(jié)點(diǎn)組成一個(gè)線性表。,孩子表示法的存儲(chǔ)結(jié)構(gòu)類型定義,typedef struct cnode int child; struct cnode *next; childlink; typedef struct char data; childlink *headptr; ctnode; /*表頭向量中結(jié)點(diǎn)結(jié)構(gòu)*/ typedef struct ctnode nodesMAXSIZE; /*表頭向