1  import java.util.Scanner;
  2  
  3  public class HuffmanCode {
  4    public static void main(String[] args) {
  5      Scanner input = new Scanner(System.in);
  6      System.out.print("Enter a text: ");
  7      String text = input.nextLine();
  8      
  9      int[] counts = getCharacterFrequency(text); // Count frequency
 10  
 11      System.out.printf("%-15s%-15s%-15s%-15s\n",
 12        "ASCII Code", "Character", "Frequency", "Code");  
 13      
 14      Tree tree = getHuffmanTree(counts); // Create a Huffman tree
 15      String[] codes = getCode(tree.root); // Get codes
 16          
 17      for (int i = 0; i < codes.length; i++)
 18        if (counts[i] != 0) // (char)i is not in text if counts[i] is 0
 19          System.out.printf("%-15d%-15s%-15d%-15s\n", 
 20            i, (char)i + "", counts[i], codes[i]);
 21    }
 22    
 23    /** Get Huffman codes for the characters 
 24     * This method is called once after a Huffman tree is built
 25     */
 26    public static String[] getCode(Tree.Node root) {
 27      if (root == null) return null;    
 28      String[] codes = new String[128];
 29      assignCode(root, codes);
 30      return codes;
 31    }
 32    
 33    /* Recursively get codes to the leaf node */
 34    private static void assignCode(Tree.Node root, String[] codes) {
 35      if (root.left != null) {
 36        root.left.code = root.code + "0";
 37        assignCode(root.left, codes);
 38        
 39        root.right.code = root.code + "1";
 40        assignCode(root.right, codes);
 41      }
 42      else {
 43        codes[(int)root.element] = root.code;
 44      }
 45    }
 46    
 47    /** Get a Huffman tree from the codes */  
 48    public static Tree getHuffmanTree(int[] counts) {
 49      // Create a heap to hold trees
 50      Heap<Tree> heap = new Heap<>(); // Defined in Listing 24.10
 51      for (int i = 0; i < counts.length; i++) {
 52        if (counts[i] > 0)
 53          heap.add(new Tree(counts[i], (char)i)); // A leaf node tree
 54      }
 55      
 56      while (heap.getSize() > 1) { 
 57        Tree t1 = heap.remove(); // Remove the smallest weight tree
 58        Tree t2 = heap.remove(); // Remove the next smallest weight 
 59        heap.add(new Tree(t1, t2)); // Combine two trees
 60      }
 61  
 62      return heap.remove(); // The final tree
 63    }
 64    
 65    /** Get the frequency of the characters */
 66    public static int[] getCharacterFrequency(String text) {
 67      int[] counts = new int[128]; // 128 ASCII characters
 68      
 69      for (int i = 0; i < text.length(); i++)
 70        counts[(int)text.charAt(i)]++; // Count the character in text
 71      
 72      return counts;
 73    }
 74    
 75    /** Define a Huffman coding tree */
 76    public static class Tree implements Comparable<Tree> {
 77      Node root; // The root of the tree
 78  
 79      /** Create a tree with two subtrees */
 80      public Tree(Tree t1, Tree t2) {
 81        root = new Node();
 82        root.left = t1.root;
 83        root.right = t2.root;
 84        root.weight = t1.root.weight + t2.root.weight;
 85      }
 86      
 87      /** Create a tree containing a leaf node */
 88      public Tree(int weight, char element) {
 89        root = new Node(weight, element);
 90      }
 91      
 92      @Override /** Compare trees based on their weights */
 93      public int compareTo(Tree t) {
 94        if (root.weight < t.root.weight) // Purposely reverse the order
 95          return 1;
 96        else if (root.weight == t.root.weight)
 97          return 0;
 98        else
 99          return -1;
100      }
101  
102      public class Node {
103        char element; // Stores the character for a leaf node
104        int weight; // weight of the subtree rooted at this node
105        Node left; // Reference to the left subtree
106        Node right; // Reference to the right subtree
107        String code = ""; // The code of this node from the root
108  
109        /** Create an empty node */
110        public Node() {
111        }
112        
113        /** Create a node with the specified weight and character */
114        public Node(int weight, char element) {
115          this.weight = weight;
116          this.element = element;
117        }
118      }
119    }  
120  }