《管理學(xué)六樹》ppt課件

1、r樹形圖表示樹形圖表示r嵌套集合表示嵌套集合表示r凹入表凹入表/書目表表示書目表表示A- B- E- F- J- K- C- G- D- H- I- r雙親表示法雙親表示法r孩子表示法孩子表示法r雙親孩子表示法雙親孩子表示法 datafirstChildnextSibling 一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合或者為一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。子樹的、互不相交的二叉樹組成。證明：假設(shè)設(shè)度為證明：假設(shè)設(shè)度為1的結(jié)點(diǎn)有的結(jié)點(diǎn)有n1個，總結(jié)點(diǎn)個，總結(jié)點(diǎn)個數(shù)

2、為個數(shù)為n，總邊數(shù)為，總邊數(shù)為e，那么根據(jù)二叉樹的，那么根據(jù)二叉樹的定義，定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1因此，有因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 定義定義1 滿二叉樹滿二叉樹(Full Binary Tree) 深度為深度為k的且有的且有 2k+1-1個結(jié)點(diǎn)的二叉樹稱為滿二個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。叉樹。定義定義2 完全二叉樹完全二叉樹(Complete Binary Tree) 假設(shè)設(shè)二叉樹的深度為假設(shè)設(shè)二叉樹的深度為h，那么共有，那么共有h+1層。除第層。除

3、第h層外，其它各層層外，其它各層(0h-1)的結(jié)點(diǎn)數(shù)都到達(dá)最大個數(shù)，的結(jié)點(diǎn)數(shù)都到達(dá)最大個數(shù)，第第h層從右向左延續(xù)缺假設(shè)干結(jié)點(diǎn)，這就是完全二層從右向左延續(xù)缺假設(shè)干結(jié)點(diǎn)，這就是完全二叉樹。叉樹。完全二叉樹的數(shù)組表示完全二叉樹的數(shù)組表示 普通二叉樹的數(shù)組表示普通二叉樹的數(shù)組表示 單支樹struct node /二叉樹結(jié)點(diǎn)的類型二叉樹結(jié)點(diǎn)的類型 struct node *lchild; /存儲左孩子結(jié)點(diǎn)位置存儲左孩子結(jié)點(diǎn)位置 typedef data; /數(shù)據(jù)域數(shù)據(jù)域 struct node *rchild; /存儲右孩子結(jié)點(diǎn)位置存儲右孩子結(jié)點(diǎn)位置struct node /二叉樹結(jié)點(diǎn)的類型二叉樹結(jié)點(diǎn)的

4、類型 struct node *lchild; /存儲左孩子結(jié)點(diǎn)位置存儲左孩子結(jié)點(diǎn)位置 typedef data; /數(shù)據(jù)域數(shù)據(jù)域 struct node *rchild; /存儲右孩子結(jié)點(diǎn)位置存儲右孩子結(jié)點(diǎn)位置 struct node *parent; /存儲雙親結(jié)點(diǎn)位置存儲雙親結(jié)點(diǎn)位置二叉樹鏈表表示的例如二叉樹鏈表表示的例如二叉樹鏈表表示的例如二叉樹鏈表表示的例如二叉樹鏈表表示的例如二叉樹鏈表表示的例如算法實(shí)現(xiàn)：二叉樹的創(chuàng)建算法實(shí)現(xiàn)：二叉樹的創(chuàng)建struct tree * creat() char c; struct tree * t; c=getchar(); if(c= ) t=NUL

5、L; else t=(struct tree *)malloc(LEN); /創(chuàng)建新結(jié)點(diǎn) t-data=c; t-lchild=creat(); /遞歸建立左子樹 t-rchild=creat(); /遞歸建立右子樹 return t; /前往頭結(jié)點(diǎn)n以前序次序ABC D E 建立二叉樹，如下圖。算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：前序遍歷前序遍歷1/前序遍歷二叉樹的遞歸算法void preorder(bintree t) if (t) printf(%c,t-data); preorder(t-lchild); preorder(t-rchild); 算法實(shí)現(xiàn)：前序遍歷算法實(shí)現(xiàn)：前序遍歷2/非遞歸實(shí)現(xiàn)二叉樹

6、的前序遍歷void preorder1(bintree t) seqstack s; s.top=-1; while (t)|(s.top!=-1) /當(dāng)前處置的子樹不為空或棧不為空那么循環(huán) while (t) printf(%c ,t-data); s.top+; s.datas.top=t; t=t-lchild; if (s.top-1) t=pop(&s); t=t-rchild; 算法實(shí)現(xiàn)：中序遍歷算法實(shí)現(xiàn)：中序遍歷1/中序遍歷二叉樹的遞歸算法void inorder(bintree t) if(t) inorder(t-lchild); printf(%c,t-data);

7、 inorder(t-rchild); 算法實(shí)現(xiàn)：中序遍歷算法實(shí)現(xiàn)：中序遍歷2void inorder1(bintree t) /非遞歸實(shí)現(xiàn)二叉樹的中序遍歷 seqstack s; s.top=-1; while(t!=NULL) | (s.top!=-1) while (t) push(&s,t); t=t-lchild; if (s.top!=-1) t=pop(&s); printf(%c ,t-data); t=t-rchild; 結(jié)點(diǎn)地址結(jié)點(diǎn)地址 *Node 退棧次數(shù)退棧次數(shù) PopTimn請寫出后序遍歷的算法遞歸與非遞歸算法ABCDEIJFGKH 假設(shè)前序序列固定不

8、變，給出不同的中序序列，可得到不同的二叉樹。1根根bnnnnnnnnC111122()!n問題的提出問題的提出6.5 哈夫曼編碼及其運(yùn)用電子期刊、網(wǎng)絡(luò)音樂、網(wǎng)絡(luò)電影數(shù)據(jù)存儲的壓力數(shù)據(jù)通訊的壓力計算機(jī)處置的壓力 數(shù)據(jù)緊縮是關(guān)鍵。緊縮的關(guān)鍵在于編碼。數(shù)據(jù)緊縮是關(guān)鍵。緊縮的關(guān)鍵在于編碼。n教學(xué)目的教學(xué)目的本節(jié)課的教學(xué)目的是在研討編碼的要求和原理的根底上，學(xué)習(xí)一種被廣泛運(yùn)用而且高效的編碼方法哈夫曼編碼。6.5 哈夫曼編碼及其運(yùn)用號碼是一種常用的編碼澳門625512340086 106027打重?fù)芤?、編碼的要求編碼不當(dāng)鬧笑話武漢發(fā)短信 ？n編碼編碼n解碼解碼p一個集合中任一編碼不能 是另一編碼的前半部分

9、， 即前綴編碼。編碼要求1625512340086 106 02712340086 10 60276255一、編碼的要求n大陸編碼大陸編碼008600853n澳門編碼澳門編碼p變長編碼，運(yùn)用次數(shù)越多的編碼越短，使電文總長 p 度最短。編碼要求2大陸有大陸有1313億人口億人口澳門有澳門有5353萬人口萬人口一、編碼的要求p 前綴編碼編碼要求1p 二進(jìn)制編碼編碼要求3p 電文總長度最短編碼要求2一、編碼的要求二、哈夫曼編碼n哈夫曼編碼是一種效率高、哈夫曼編碼是一種效率高、運(yùn)算速度快的編碼方法，運(yùn)算速度快的編碼方法，根據(jù)待緊縮數(shù)據(jù)的特征，根據(jù)待緊縮數(shù)據(jù)的特征，緊縮率可到達(dá)緊縮率可到達(dá)20%-90%

10、20%-90%。n許多知名的緊縮工具和緊許多知名的緊縮工具和緊縮算法里如縮算法里如WinZipWinZip和和JPEGJPEG，都有哈夫曼編碼，都有哈夫曼編碼的身影。的身影。David A. Huffman 19251999 二、哈夫曼編碼n19501950年，哈夫曼年，哈夫曼HuffmanHuffman在在MIT(MIT(麻省理工麻省理工) )的研討生班學(xué)習(xí)。的研討生班學(xué)習(xí)。范諾范諾FanoFano教授讓學(xué)生們本教授讓學(xué)生們本人決議是參與期未考試還是做人決議是參與期未考試還是做一個大作業(yè)。哈夫曼選擇了后一個大作業(yè)。哈夫曼選擇了后者，這個大作業(yè)促使了后來哈者，這個大作業(yè)促使了后來哈夫曼算法的誕

11、生。夫曼算法的誕生。n19521952年，范諾提出了范諾編碼，年，范諾提出了范諾編碼，該編碼可以獲得一定的緊縮效該編碼可以獲得一定的緊縮效果，但是離真正適用的緊縮算果，但是離真正適用的緊縮算法還相去甚遠(yuǎn)。法還相去甚遠(yuǎn)。n同年，哈夫曼提出了哈夫曼編同年，哈夫曼提出了哈夫曼編碼，這是第一個真正適用的編碼，這是第一個真正適用的編碼方法。碼方法。David A. Huffman 19251999 要了解哈夫曼編碼，先要了解一哈夫曼樹的定義二如何構(gòu)造哈夫曼樹三如何構(gòu)造哈夫曼編碼二、哈夫曼編碼 一哈夫曼樹的定義例1：一個數(shù)據(jù)文件僅包含字符a, b, c, d, 字符的權(quán)值分別為6, 4, 1, 2，可構(gòu)造

12、如下一棵二叉樹。a6c1d2b4n結(jié)點(diǎn)的帶權(quán)途徑長度：結(jié)點(diǎn)結(jié)點(diǎn)的帶權(quán)途徑長度：結(jié)點(diǎn)的途徑長度與該結(jié)點(diǎn)權(quán)值的的途徑長度與該結(jié)點(diǎn)權(quán)值的乘積。乘積。 n結(jié)點(diǎn)的途徑長度：從根結(jié)點(diǎn)結(jié)點(diǎn)的途徑長度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的途徑上分支的數(shù)到該結(jié)點(diǎn)的途徑上分支的數(shù)目。目。 000111一哈夫曼樹的定義n在一切含在一切含 n n 個葉子結(jié)點(diǎn)、個葉子結(jié)點(diǎn)、并帶一樣權(quán)值的二叉樹中，并帶一樣權(quán)值的二叉樹中，帶權(quán)途徑長度取最小值的帶權(quán)途徑長度取最小值的二叉樹，即最優(yōu)二叉樹，二叉樹，即最優(yōu)二叉樹，又稱哈夫曼樹。又稱哈夫曼樹。n樹的帶權(quán)途徑長度：樹中一樹的帶權(quán)途徑長度：樹中一切葉子結(jié)點(diǎn)的帶權(quán)途徑長度切葉子結(jié)點(diǎn)的帶權(quán)途徑長度之和。

13、之和。 a6c1d2b4000111WPL=6+4*2+(1+2)*3=23WPL=1+2*2+(4+6)*3=35例例1：字符：字符a, b, c, d分別帶權(quán)分別帶權(quán)6, 4, 1, 2, 可構(gòu)造出如下可構(gòu)造出如下三棵二叉樹三棵二叉樹(還有許多棵還有許多棵)，它們的，它們的WPL分別為：分別為：WPL=(6+4+1+2)*2=26(2)c1d2b4a6(3)c1d2b4a6(1)c1d2b4a6二構(gòu)造哈夫曼樹n構(gòu)造哈夫曼樹的原理構(gòu)造哈夫曼樹的原理n權(quán)值越大的葉子結(jié)點(diǎn)離根越近權(quán)值越大的葉子結(jié)點(diǎn)離根越近n權(quán)值越小的葉子結(jié)點(diǎn)離根越遠(yuǎn)權(quán)值越小的葉子結(jié)點(diǎn)離根越遠(yuǎn)二構(gòu)造哈夫曼樹二構(gòu)造哈夫曼樹a6c1d

14、2b4n構(gòu)造哈夫曼樹的方法構(gòu)造哈夫曼樹的方法n(1) (1) 初始化初始化n(2) (2) 選擇與合并選擇與合并n(3) (3) 刪除與參與刪除與參與n(4) (4) 反復(fù)反復(fù)2 2，3 3直到直到F F中只需一棵樹。中只需一棵樹。二構(gòu)造哈夫曼樹例2：假設(shè)有一個包含1 000 000個字符的數(shù)據(jù)文件僅包含字符a-e，每個字符出現(xiàn)的頻度如下表中所示。請構(gòu)造哈夫曼樹。二構(gòu)造哈夫曼樹字字 符符abcde頻度頻度(萬字萬字)62131285二構(gòu)造哈夫曼樹 (1)初始化：根據(jù)給定的初始化：根據(jù)給定的n個權(quán)值個權(quán)值wl，w2，wn構(gòu)成構(gòu)成n棵棵二叉樹的森林二叉樹的森林F=T1，T2，Tn，其中每棵二叉樹，

15、其中每棵二叉樹Ti中都只需一個權(quán)值為中都只需一個權(quán)值為wi的根結(jié)點(diǎn)。的根結(jié)點(diǎn)。字字 符符abcde頻度頻度(萬字萬字)62131285 62a 13b 12c 5e 8dT1T2T3T4T5二構(gòu)造哈夫曼樹(2)選擇與合并：從F中選根權(quán)最小的兩棵二叉樹Ti和Tj，分別作為左右子樹，根結(jié)點(diǎn)r的權(quán)為wi+wj 。13 5e 8d 62a 13b 12c 5e 8dT1T2T3T4T5二構(gòu)造哈夫曼樹 62a 13b 12c 5e 8d(3)刪除與參與：從F中刪除Ti和Tj ，新的樹參與F。13 5e 8dT1T2T3T4T5二構(gòu)造哈夫曼樹13 5e 8dT1T2T3T4 62a 13b 12c(3)刪

16、除與參與：從F中刪除Ti和Tj ，新的樹參與F。二構(gòu)造哈夫曼樹(4) 反復(fù)2，3 直到F中只需一棵樹。13 5e 8dT1T2T3T4 62a 13b 12c二構(gòu)造哈夫曼樹 13b 12c2513 5e 8d 62a(4) 反復(fù)2，3 直到F中只需一棵樹。T1T2T3二構(gòu)造哈夫曼樹(4)反復(fù)2，3 直到F中只需一棵樹。13 5e 8dT1T2T3T4 62a 13b 12c二構(gòu)造哈夫曼樹(4) 反復(fù)2，3 直到F中只需一棵樹。13 5e 8dT1 62a 13b 12c25T3T2二構(gòu)造哈夫曼樹13 5e 8d 13b 12c2538(4) 反復(fù)2，3 直到F中只需一棵樹。T2T1 62a二構(gòu)

17、造哈夫曼樹 62a13 5e 8d 13b 12c2538T1(4) 反復(fù)2，3 直到F中只需一棵樹。100二構(gòu)造哈夫曼樹(4)反復(fù)2，3 直到F中只需一棵樹。 62a13 5e 8d 13b 12c2538T1100 13b 12c2513 5e 8d 62aT1T2T3二構(gòu)造哈夫曼樹(4) 反復(fù)2，3 直到F中只需一棵樹。 13b 12c2513 5e 8d 62aT1T238 62a13 5e 8d 13b 12c2538T1100二構(gòu)造哈夫曼樹(4)反復(fù)2，3 直到F中只需一棵樹。 13b 12c2513 5e 8d 62a38100T1 62a13 5e 8d 13b 12c2538

18、T1100二構(gòu)造哈夫曼樹WPL=62*1+(13+12+8+5)*3= 176WPL=62*1+13*2+12*3+(5+8)*4= 176 62a13 5e 8d 13b 12c2538100 13b 12c2513 5e 8d 62a38100 5e 8d 13b 12c有問題：不滿足前綴編碼的要求。二構(gòu)造哈夫曼樹哈夫曼樹的形狀能夠不獨(dú)一，WPL最小。 61a字字 符符abcde頻度頻度(萬字萬字)62131285哈夫曼編碼哈夫曼編碼1011010001 62a13 5e 8d 13b 12c253810001010101000三構(gòu)造哈夫曼編碼將哈夫曼樹的左分 支標(biāo)0， 右分支標(biāo)1；(2)根到結(jié)點(diǎn)的途徑上的 標(biāo)號序列是該結(jié)點(diǎn)的 編碼。10095575205 5e 8d 62a 13b 12c等