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