使用霍夫曼樹解碼消息

Question

當我發送要解碼的一串比特時，似乎需要一個額外的比特才能正確解碼。我已經預先打印出樹，並且我已經在紙上畫了樹，以確保我沒有錯過任何東西。預訂和我繪製的樹匹配，但生成正確字母所需的位已關閉。

public void decode(String code){ 
    String result = ""; 
    TreeNode current = root; 
    current.preOrder(); 
    for(int i = 0;i < code.length();i++){ 
     //left--0 
     if(Character.getNumericValue(code.charAt(i))==0){ 
      if(current.getLeft() == null){ 
       result += current.getWeight().getLetter(); 
       current = root; 
       i--; 
      }else 
       current=current.getLeft(); 
     } 
     //right--1 
     else if(Character.getNumericValue(code.charAt(i))==1){ 
      if(current.getRight() == null){ 
       result += current.getWeight().getLetter(); 
       current = root; 
       i--; 
      }else 
       current=current.getRight(); 
     } 
    } 
    System.out.println(result); 
} 

我的樹每次都正確構建，這讓我相信錯誤在解碼方法中。但是，我似乎無法弄清楚爲什麼需要額外的位。

Answer 1

沒有看到你的節點佈局如何，我只能猜測。當遍歷左/右時，你可能需要檢查你是否落在了一個葉節點上，如果是的話就發出它的字符。

if (current.getLeft() == null) { 
    ... 
} 
else { 
    current = current.getLeft(); 
    if (current.isLeaf()) { 
     result += current.getWeight().getLetter(); 
     current = root; 
    } 
} 

右側也是如此。

不要重複自己

爲了避免重複追加角色和當前節點重置爲根四倍兩條線，你可以改爲設置一個標誌和的結束檢查for塊。

boolean append = false; 
if (Character.getNumericValue(code.charAt(i)) == 0) { 
    if (current.getLeft() == null) { 
     append = true; 
     i--; 
    } 
    else { 
     current = current.getLeft(); 
     if (current.isLeaf()) { 
      append = true; 
     } 
    } 
} 
// same for right side ... 
if (append) { 
    result += current.getWeight().getLetter(); 
    current = root; 
} 

其他提示

• 交換機從兩個if檢查0或1的switch有default拋出一個IllegalArgumentException。
• 將for循環切換爲while以避免預先遞減i只是爲了讓它再次遞增並避免停止循環。
• 從append開始設置爲true，因爲追加了六個案例中的四個案例。