1 import java.util.HashMap;
2 import java.util.Map;
3 import java.util.PriorityQueue;
4
5 /**
6 A tree for decoding Huffman codes.
7 */
8 public class HuffmanTree
9 {
10 private Node root;
11
12 /**
13 Constructs a Huffman tree from given character frequencies.
14 @param frequencies a map whose keys are the characters to be encoded
15 and whose values are the frequencies of the characters
16 */
17 public HuffmanTree(Map<Character, Integer> frequencies)
18 {
19 PriorityQueue<Node> nodes = new PriorityQueue<Node>();
20 for (char ch : frequencies.keySet())
21 {
22 Node newNode = new Node();
23 newNode.character = ch;
24 newNode.frequency = frequencies.get(ch);
25 nodes.add(newNode);
26 }
27
28 while (nodes.size() > 1)
29 {
30 Node smallest = nodes.remove();
31 Node nextSmallest = nodes.remove();
32 Node newNode = new Node();
33 newNode.frequency = smallest.frequency + nextSmallest.frequency;
34 newNode.left = smallest;
35 newNode.right = nextSmallest;
36 nodes.add(newNode);
37 }
38
39 root = nodes.remove();
40 }
41
42 /**
43 Decodes an encoded string.
44 @param input a string made up of 0 and 1
45 */
46 public String decode(String input)
47 {
48 String result = "";
49 Node n = root;
50 for (int i = 0; i < input.length(); i++)
51 {
52 char ch = input.charAt(i);
53 if (ch == '0')
54 {
55 n = n.left;
56 }
57 else
58 {
59 n = n.right;
60 }
61 if (n.left == null) // n is a leaf
62 {
63 result = result + n.character;
64 n = root;
65 }
66 }
67 return result;
68 }
69
70 public Map<Character, String> getEncodingMap()
71 {
72 Map<Character, String> map = new HashMap<Character, String>();
73 if (root != null) { root.fillEncodingMap(map, ""); }
74 return map;
75 }
76
77 class Node implements Comparable<Node>
78 {
79 public char character;
80 public int frequency;
81 public Node left;
82 public Node right;
83
84 public int compareTo(Node other) { return frequency - other.frequency; }
85
86 public void fillEncodingMap(Map<Character, String> map, String prefix)
87 {
88 if (left == null) // it's a leaf
89 {
90 map.put(character, prefix);
91 }
92 else
93 {
94 left.fillEncodingMap(map, prefix + "0");
95 right.fillEncodingMap(map, prefix + "1");
96 }
97 }
98 }
99 }
100