數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)(1)-資料下載頁(yè)
2025-01-20 06:35本頁(yè)面
【正文】 點(diǎn)的路徑長(zhǎng)度 定義為從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。 ? 樹的路徑長(zhǎng)度 定義為樹中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 ? 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 定義為從樹根到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上所帶權(quán)值的乘積。 ? 樹的帶權(quán)路徑長(zhǎng)度定義為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 ** WPL(T)=? wklk (對(duì)所有葉子結(jié)點(diǎn) ) 其中 lk為帶權(quán) wk的葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 最優(yōu)二叉樹 概念 在所有含 n 個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值 (n個(gè)確定的數(shù) )的 m 叉樹中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹，稱為“ 最優(yōu)樹 ”。 對(duì)于二叉樹而言，稱為 最優(yōu)二叉樹 。 最優(yōu)二叉樹 右圖中的四棵二叉樹，都有 5個(gè)葉子結(jié)點(diǎn)且?guī)嗤瑱?quán)值 9，它們的帶權(quán)路徑長(zhǎng)度分別為： WPL=7*3+9*3+5*2 +6*2+2*2=74 (左上圖 ) WPL=2*1+6*3+7*4 +9*4+5*2=94 (右上圖 ) WPL=6*2+7*2+5*3 +2*3+9*2=65 (左下圖 ) WPL=2*1+5*3+7*3 +9*3+6*3=83 (右下圖 ) 其中以左下圖中二叉樹的帶權(quán)路徑長(zhǎng)度為最小?？梢则?yàn)證，它恰為最優(yōu)二叉樹，即在所有葉子結(jié)點(diǎn)帶權(quán)為 7的二叉樹中，帶權(quán)路徑長(zhǎng)度的最小值為65。 最優(yōu)二叉樹 Huffman樹的構(gòu)造方法（最優(yōu)二叉樹）： ① 根據(jù)給定的 n 個(gè)權(quán)值 {w1, w2, …, w n}，構(gòu)造 n 棵二叉樹的集合 F = {T1, T2, …, T n}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為 wi 的根結(jié)點(diǎn) ,其左、右子樹為空樹 。 ② 在 F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和； ③ 在 F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入 F 中。 ④ 重復(fù) (2)和 (3)，直到 F 只含一棵樹為止。這棵樹便是所求的赫夫曼樹。 最優(yōu)二叉樹 Huffman樹的構(gòu)造實(shí)例： 權(quán)值 9 2 5 6 7 ９ 2 5 6 7 ９ ７ 2 5 6 7 ９ ７ 13 最優(yōu)二叉樹 Huffman樹的構(gòu)造實(shí)例： 權(quán)值 9 2 5 6 7 ９ ７ 13 2 5 6 7 ９ ７ 13 16 2 5 6 7 ９ ７ 13 16 29 Huffman編碼 表示一個(gè)消息文本，通常有兩類二進(jìn)制編碼： ? 一類為等長(zhǎng)編碼，這類編碼的二進(jìn)制串的長(zhǎng)度取決于電文中不同的字符個(gè)數(shù)，假設(shè)需傳送的電文中只有四種字符，只需兩位字符的串便可分辨，但如果電文中可能出現(xiàn) 26種不同字符，則等長(zhǎng)編碼串的長(zhǎng)度為 5。 ? 另一類是不等長(zhǎng)編碼，即各個(gè)字符的編碼長(zhǎng)度不等。 Huffman編碼 可以利用二叉樹來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼。假設(shè)有一棵如右圖所示的二叉樹，其四個(gè)葉子結(jié)點(diǎn)分別表示A、 B、 C和 D四個(gè)字符，且約定左分支表示字符 39。039。，右分支表示字符 39。139。，則以由從根到葉子的路徑上的分支表示的字符組成的字符串作為該葉子結(jié)點(diǎn)字符的編碼。如右圖中 A、 B、 C和 D的二進(jìn)制前綴編碼分別為 0、 110和 111。容易證明，如此得到的必為二進(jìn)制前綴編碼。并且，若以字符出現(xiàn)的次數(shù)為權(quán)，構(gòu)造一棵赫夫曼樹，由此得到的二進(jìn)制前綴編碼便為 最優(yōu)前綴編碼 (赫夫曼編碼 )。即以這組編碼傳送電文可使電文總長(zhǎng)最短 (對(duì)所有其它前綴編碼而言 )。 A 0 1 B 0 1 D C 0 1 DAABABCBCA 編碼 1110010010110101100 譯碼 DAABABCBCA 樹的計(jì)數(shù) ? 另一個(gè)角度： 前序（后序）＋中序唯一確定一棵二叉樹 ? : 前序 : A、 B、 D、 E、 F、 C 中序 : D、 B、 E、 F、 A、 C ? 確定過(guò)程 : 定根 A 在中序序列中找到 A 中序序列中的 A 的左部為 A 的左子樹上的所有結(jié)點(diǎn)， A 的右部為 A 的右子樹中的所有結(jié)點(diǎn)。 根據(jù) A 的左子樹的所有結(jié)點(diǎn)的前序序列確定 A 的左子樹的根節(jié)點(diǎn)，它是 A的左兒子。 根據(jù) A 的右子樹的所有結(jié)點(diǎn)的前序序列確定 A 的右子樹的根節(jié)點(diǎn)，它是 A的右兒子。 在左、右子樹中反復(fù)以上過(guò)程。至所有結(jié)點(diǎn)處理完畢。結(jié)束 前序 : A、 B、 D、 E、 F、 C 中序 : D、 B、 E、 F、 A、 C 前序 : A、 B、 D、 E、 F、 C 中序 : D、 B、 E、 F、 A、 C A C A D、 E、 F C B 前序 : B、 D、 E、 F 中序 : D、 B、 E、 F E F A B C D 前序 : E、 F 中序 : E、 F D、 B、 E、 F
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1