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