[電腦基礎知識]第7章樹-資料下載頁
2025-01-19 15:32本頁面
【正文】 1）樹中所有葉結點的右鏈是線索，因此葉結點的 right指向該結點的后繼結點。 2）非終端結點若無右孩子，則其右鏈是線索，指向后繼，若有右孩子，則其后繼是中序遍歷其右子樹時訪問的第一個結點，即 右子樹中最左下結點 。 找結點的前驅結點的過程 （以中序線索為例） ： 1）樹中所有葉結點的左鏈是線索（左線索標志為 1），因此葉結點的 Left直接指向其前驅結點。 2）若該結點的左線索標志為 0，則該結點的前驅為遍歷其左子樹時最后訪問的那個結點，即左子樹中最右下的結點 為其前驅結點。 若線索二叉樹的高度為 h，則在最壞情況下，可在 O(h)時間內找到一個結點的前驅和后繼結點 。 如何進行二叉樹的線索化呢？ 線索化的實質是將二叉鏈表中的空指針改為指向結點前驅或后繼的線索，而一個結點的前驅和后繼的信息只有在遍歷時才能得到，因此線索化過程即為 在遍歷的過程中修改空指針的過程。 pre p 哈夫曼樹及其應用 ? 樹的路徑長度的概念： 從樹中一個結點到另一個結點之間的分支數(shù)目。 從樹根到每一結點的路徑長度之和。如圖所示： 1 2 4 5 3 6 7 樹的路徑長度PL=0+1+1+2+2+2+2=10 ? 結點帶權的路徑長度： 從該結點到樹根之間的路徑長度與結點上權的乘積。 ? 樹的帶權路徑長度 （ weighted path length of tree）：樹中所有 葉子結點 的帶權路徑長度之和。 ???nkKLKWW P L1記作： a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 其中： Wk為樹中每個葉子結點的權 L k為每個葉子結點到根的路徑長度。 WPL最小的二叉樹就稱作 最優(yōu)二叉樹 或 哈夫曼樹 。 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 具有不同帶權路徑長度的二叉樹 d c a b 2 4 7 5 WPL=7*3+5*3+2*1+4*2=46 a b c d 7 5 2 4 WPL=7*1+5*2+2*3+4*3=35 ? 怎樣構造一棵 哈 夫曼樹呢？ 方法： （ 1）根據(jù)給定的 n個權值 {W1,W2,… Wn}構成 n棵二叉樹的森林 F={T1,T2,… Tn}，其中每棵二叉樹 Ti中只有一個帶權為 Wi的根結點，其左右子樹均為空 。 （ 2）在森林 F中選取兩棵根結點權值 最小的和次小的二叉樹 (當這樣的樹不止兩棵樹時，可以從中任選兩棵 )作為左右子樹構造一棵新的二叉樹，其根結點的權值為左右子樹根結點權值之和。 （ 3）在 F中刪除這兩棵權值最小的樹，同時將新的二叉樹加入到森林 F中 。 （ 4）重復 3步驟，直至 F中只剩一棵樹為止。 這棵樹便是 哈 夫曼樹。 6 7 5 c d (b) 11 b 5 7 c d (c) 7 18 a 11 c d b 5 6 2 4 (d) a b c d 7 5 2 4 (a) 例：給定權值 {7， 5， 2， 4}，構造哈夫曼樹。 課堂練習三 ? 給定權值 7， 18， 3， 32， 5， 26， 12， 8，構造相應的赫夫曼樹 赫夫曼樹的應用 （ 1）赫夫曼編碼 利用赫夫曼樹構造通訊中電文編碼 例如：要傳輸一個電文： {CAS； CAT；SAT； AT} 要傳輸?shù)淖址?D={C， A， S， T， ； } 每個字符出現(xiàn)的頻率是 W={ 2， 4， 2， 3， 3 } ? 等長編碼： C(000)A(001)S(010)T(011)。(100) 000001010100000001011100010001011100001011 42位 ? 不等長編碼： C(0)A(00)S(1)T(01)。(10) 000110000011010001100001 24位 無法翻譯 ? 前綴編碼 ：任一個字符的編碼都不是另一個字符編碼的前綴 C(0)A(10)S(110)T(1110)。(1111) 0101101111010111011111101011101111101110 40位前綴碼 文件總碼長達到最小的前綴編碼的方法（構造一棵赫夫曼樹）： （ 1）用頻率作為葉子結點的權值生成一棵赫夫曼樹，并將對應權值 wi的葉子結點注明對應的字符； （ 2）約定左分支表示字符 “ 0”，右分支表示字符 ‘ 1’ （ 3）從葉子結點開始，順著雙親反推上去，直到根結點，路徑上的 ‘ 0’或 ‘ 1’連接的序列就是結點對應的字符的二進制編碼的逆序。 編碼的過程：從根結點出發(fā)走一條從根到葉子的編碼路徑 例子：要傳輸?shù)碾娢氖?{CAS； CAT； SAT； AT} 要傳輸?shù)淖址? D={C， A， S， T， ； } 每個字符出現(xiàn)的頻率是 W={ 2， 4， 2， 3， 3 } 各字符編碼是 T ； A C S 00 01 10 110 111 上述電文編碼：（ 32位） 11010111011101000011111000011000 14 6 8 3 3 4 4 2 2 0 0 1 1 1 T 。 A C S 1 0 0 習題 ? 一、設某密碼電文由 8個字母組成，每個字母在電文中出現(xiàn)頻率分別是7,19,2,6,32,3,21,10，試為這 8個字母設計相應的赫夫曼編碼。
教學課件相關推薦
鄂ICP備17016276號-1