7個權值是 7 2 8 4 16 3 9(1) 從小到大排序 2 3 4 7 8 9 16 (這是有序序列)(2) 每次提取最小的兩個結點,取結點2和結點3,組成新結點N5,其權值=2+3=5, 取數值較小的結點作為左分支,結點2作為左分支,而結點3就作為右分支.(3) 將新結點N5放入有序序列,保持從小到大排序: 4 N5 7 8 9 16(4) 重複步驟(2),提取最小的兩個結點,結點4與N5組成新結點N9,其權值=4+5=9, 結點4的數值較小,作為左分支,N5就作為右分支.(5) 將新結點N9放入有序序列,保持從小到大排序: 7 8 9 N9 16 [注意:新結點N9排在原有結點9的後面](6) 重複步驟(2),提取最小的兩個結點,結點7與結點8組成新結點N15,其權值=7+8=15, 結點7的數值較小,作為左分支,結點8就作為右分支.(7) 將新結點N15放入有序序列,保持從小到大排序: 9 N9 N15 16(8) 重複步驟(2),提取最小的兩個結點,結點9與N9組成新結點N18,其權值=9+9=18, 結點9作為左分支,N9就作為右分支.(9) 將新結點N18放入有序序列,保持從小到大排序: N15 16 N18(10)重複步驟(2),提取最小的兩個結點,N15與結點16組成新結點N31,其權值=15+16=31, N15的數值較小,作為左分支,結點16就作為右分支.(11)將新結點N31放入有序序列,保持從小到大排序: N18 N31(12)重複步驟(2),提取剩下的兩個結點,N18與N31組成新結點N49,其權值=18+31=49, 數值較小的N18作為左分支,N31就作為右分支. 最後得到"哈夫曼樹": N49 / \ N18 N31 / \ / \ 9 N9 N15 16 / \ / \ 4 N5 7 8 / \ 2 3帶權路徑長度(WPL):根結點N49到結點16的路徑長度是2,結點16的帶權路徑長度是16*2根結點N49到結點9的路徑長度是2,結點9的帶權路徑長度是9*2根結點N49到結點8的路徑長度是3,結點8的帶權路徑長度是8*3根結點N49到結點7的路徑長度是3,結點7的帶權路徑長度是7*3根結點N49到結點4的路徑長度是3,結點4的帶權路徑長度是4*3根結點N49到結點3的路徑長度是4,結點3的帶權路徑長度是3*4根結點N49到結點2的路徑長度是4,結點2的帶權路徑長度是2*4所以,哈夫曼樹的帶權路徑長度(WPL)等於16*2 + 9*2 + 8*3 + 7*3 + 4*3 + 3*4 + 2*4 = 127附:哈夫曼編碼:規定哈夫曼樹的左分支代表0,右分支代表1.從根結點N49到結點16,連續經歷兩次右分支,編碼就是11從根結點N49到結點9,連續經歷兩次左分支,編碼就是00從根結點N49到結點8,先經歷右分支,再左分支,最後右分支,編碼就是101如此類推,可以得出所有的結點的 哈夫曼編碼:權值16: 11權值 9: 00權值 8: 101權值 7: 100權值 4: 010權值 3: 0111權值 2: 0110
7個權值是 7 2 8 4 16 3 9(1) 從小到大排序 2 3 4 7 8 9 16 (這是有序序列)(2) 每次提取最小的兩個結點,取結點2和結點3,組成新結點N5,其權值=2+3=5, 取數值較小的結點作為左分支,結點2作為左分支,而結點3就作為右分支.(3) 將新結點N5放入有序序列,保持從小到大排序: 4 N5 7 8 9 16(4) 重複步驟(2),提取最小的兩個結點,結點4與N5組成新結點N9,其權值=4+5=9, 結點4的數值較小,作為左分支,N5就作為右分支.(5) 將新結點N9放入有序序列,保持從小到大排序: 7 8 9 N9 16 [注意:新結點N9排在原有結點9的後面](6) 重複步驟(2),提取最小的兩個結點,結點7與結點8組成新結點N15,其權值=7+8=15, 結點7的數值較小,作為左分支,結點8就作為右分支.(7) 將新結點N15放入有序序列,保持從小到大排序: 9 N9 N15 16(8) 重複步驟(2),提取最小的兩個結點,結點9與N9組成新結點N18,其權值=9+9=18, 結點9作為左分支,N9就作為右分支.(9) 將新結點N18放入有序序列,保持從小到大排序: N15 16 N18(10)重複步驟(2),提取最小的兩個結點,N15與結點16組成新結點N31,其權值=15+16=31, N15的數值較小,作為左分支,結點16就作為右分支.(11)將新結點N31放入有序序列,保持從小到大排序: N18 N31(12)重複步驟(2),提取剩下的兩個結點,N18與N31組成新結點N49,其權值=18+31=49, 數值較小的N18作為左分支,N31就作為右分支. 最後得到"哈夫曼樹": N49 / \ N18 N31 / \ / \ 9 N9 N15 16 / \ / \ 4 N5 7 8 / \ 2 3帶權路徑長度(WPL):根結點N49到結點16的路徑長度是2,結點16的帶權路徑長度是16*2根結點N49到結點9的路徑長度是2,結點9的帶權路徑長度是9*2根結點N49到結點8的路徑長度是3,結點8的帶權路徑長度是8*3根結點N49到結點7的路徑長度是3,結點7的帶權路徑長度是7*3根結點N49到結點4的路徑長度是3,結點4的帶權路徑長度是4*3根結點N49到結點3的路徑長度是4,結點3的帶權路徑長度是3*4根結點N49到結點2的路徑長度是4,結點2的帶權路徑長度是2*4所以,哈夫曼樹的帶權路徑長度(WPL)等於16*2 + 9*2 + 8*3 + 7*3 + 4*3 + 3*4 + 2*4 = 127附:哈夫曼編碼:規定哈夫曼樹的左分支代表0,右分支代表1.從根結點N49到結點16,連續經歷兩次右分支,編碼就是11從根結點N49到結點9,連續經歷兩次左分支,編碼就是00從根結點N49到結點8,先經歷右分支,再左分支,最後右分支,編碼就是101如此類推,可以得出所有的結點的 哈夫曼編碼:權值16: 11權值 9: 00權值 8: 101權值 7: 100權值 4: 010權值 3: 0111權值 2: 0110