[計算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)06gj-資料下載頁
2025-10-10 04:11本頁面
【正文】 kkklw1 基本術(shù)語 D到 H的 路徑 DGH D到 H路徑的長 為 2 A到 H的 路徑 ADGH A到 H路徑的長 為 3 樹的路徑長度 =1+1+1+2+2+2+3+3=15 n個結(jié)點(diǎn)的二叉樹路徑長度最小的是完全二叉樹 A B C D E F H I G 基本術(shù)語示例 A B C D E F G H I 每個葉子結(jié)點(diǎn)都帶權(quán)的二叉樹叫帶權(quán)二叉樹 7 5 2 4 A到 C的帶權(quán)路徑的長 二叉樹的帶權(quán)路徑的長 本樹帶權(quán)路徑的長 =7*3+5*2+2*3+4*3=49 帶權(quán)路徑的長 WPL=Σ wklk k=1 n 二叉樹帶權(quán)路徑的長 n個葉子結(jié)點(diǎn)權(quán)值分別為 w1,w2,,wn的二叉樹中，帶權(quán)路徑長度 WPL最小的二叉樹。 5 2 7 4 5 2 7 4 WPL=49 WPL=(7+5+2+4)*2 =36 最優(yōu)二叉樹 ( 赫夫曼樹 ) 5 2 4 7 5 2 4 7 WPL=36 WPL=7+5*2+2*3+4*3 =35 最優(yōu)二叉樹 ( 赫夫曼樹續(xù) ) 將百分制轉(zhuǎn)換成五級計分制 if(a60) b=‘E’。 else if(a70) b=‘D’。 else if(a80) b=‘C’。 else if(a90) b=‘B’。 else b=‘A’。 a60 b=‘E’ a70 b=‘D’ a80 b=‘C’ a90 b=‘B’ b=‘A’ 100個學(xué)生中 5個不及格 15個 60幾分 40個 70幾分 30個 80幾分 10個 90幾分 5 15 40 30 10 需比較5+2*15+3*40+4*30+4*10 =315次 帶權(quán)路徑長度的例子 (1)根據(jù)給定的 n個權(quán)值 {w1,w2,…,w n}，構(gòu)成 n棵二叉樹的集合 F={T1,T2,…,T n}， Ti 為只有一個結(jié)點(diǎn)的樹，其權(quán)為 wi。 (2)在 F中選取兩棵權(quán)值最小的作為左右子樹構(gòu)造一棵新二叉樹，其根結(jié)點(diǎn)的權(quán)值為其左右子樹權(quán)值之和。 (3)在 F中刪除這兩棵樹，同時將新得到的二叉樹加入 F中。 (4)重復(fù) (2)和 (3)，直到 F中只含一棵樹為止。該樹即為赫夫曼樹。 赫夫曼樹算法 5 2 7 4 A B C D C D 6 5 7 A B C D B A 11 7 C D B A 數(shù)字通信傳輸電文 ABACCDA 一般編碼方案 A B C D 00 01 10 11 電文 00010010101100 14位 岐義編碼方案 A: 0 B: 00 C: 1 D: 01 不是 赫夫曼編碼的應(yīng)用 A B C D 0 10 110 111 理想編碼方案 通信中，可以采用 0,1的不同排列來表示不同的字符，稱為 二進(jìn)制編碼 。 在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為 前綴編碼 。 可以利用二叉樹來設(shè)計二進(jìn)制的前綴編碼。約定左分支表示字符‘ 0’，右分支便是字符‘ 1’，以分支字符串作為該葉子結(jié)點(diǎn)字符的編碼。 哈夫曼編碼 如何得到最短的二進(jìn)制編碼？ 用 n個字符出現(xiàn)的頻率作權(quán)，構(gòu)造一顆赫夫曼樹，來求得最短的二進(jìn)制編碼，稱為赫夫曼編碼。 哈夫曼編碼是一種不等長的二進(jìn)制編碼。 在哈夫曼樹中得到的葉子結(jié)點(diǎn)的編碼為 從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)中所有路徑中 0、 1的順序排列 。 哈夫曼編碼 電文 ABACCDA 01001101101110 14位 A B C D 0 10 110 111 B C D A 0 1 0 1 0 1 用二叉樹設(shè)計前綴碼 ? 電文 ABACCDA 字符出現(xiàn)的頻度 A 3次 B 1次 C 2次 D 1次 構(gòu)造一棵權(quán)為 {3， 1， 2， 1} 的赫夫曼樹 A B C D 0 110 10 111 電文 0110010101110 13位 C B D A 0 1 0 1 0 1 赫夫曼編碼設(shè)計示例 由于赫夫曼樹中沒有度為 1的結(jié)點(diǎn) (這類樹又稱嚴(yán)格的 (strict)(或正則的 )二叉樹 )；則一棵有 n個葉子結(jié)點(diǎn)的赫夫曼樹共有 2n1個結(jié)點(diǎn) (因 n2=n01)，可以存儲在一個大小為 2n1的一維數(shù)組中。 如何選定結(jié)構(gòu)類型？ （ 1） 編碼 需要從葉子到根 （ 2） 譯碼 需要從根到葉子 對于每個結(jié)點(diǎn)，既要含雙親結(jié)點(diǎn)的信息，又要含孩子結(jié)點(diǎn)的信息。 赫夫曼編碼和譯碼 樹的計數(shù) 已知二叉樹的遍歷序列： 前序序列為 ABECDFGHIJ， 中序序列為 EBCDAFHIGJ， 求其樹的構(gòu)成以及后序遍歷序列 E B F C G H A D I J E B F C G HI A D J E B F CD HIGJ A EBCD FHIGJ A 前序序列為 ABECDFGHIJ， 中序序列為 EBCDAFHIGJ 二叉樹構(gòu)造 本章小結(jié) 遍歷二叉樹的 算法與實現(xiàn)。 。 本章作業(yè) Huffman 編碼的譯碼過程。 即輸入一個碼串，請翻譯成相應(yīng)的字符串。要求有編碼過程和解碼過程。 {15, 03, 14, 02, 06, 09, 16, 17}, 構(gòu)造相應(yīng)的赫夫曼樹 , 并計算它的帶權(quán)外部路徑長度 ABECDFGHIJ，中序序列為 eBCDAFHIGJ，求其樹的構(gòu)成以及后序遍歷序列 03 06 15 14 02 09 16 17 06 15 14 09 16 17 03 02 05 15 14 09 16 17 03 06 02 05 11 15 14 16 17 03 06 02 09 05 11 20
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1