BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 957

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[ 2 * 128 ];
29 assignCode(root, codes);
30

getCode

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 23.9
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
59 heap.add( new Tree(t1, t2)); // Combine two trees
60 }
61
62

assignCode

getHuffmanTree

return heap.remove(); // The final tree

63 }
64
65 /** Get the frequency of the characters */

66 public static int [] getCharacterFrequency(String text) {

getCharacterFrequency

67 int [] counts = new int [ 256 ]; // 256 ASCII characters

68
69 for ( int i = 0 ; i < text.length(); i++)
70 counts[( int )text.charAt(i)]++; // Count the characters 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

Huffman tree

/** Create a tree with two subtrees */