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

F IGURE 25.22

The animation tool enables you to create and view a Huffman tree, and it performs encoding and decoding

using the tree.

The algorithm used here is an example of a greedy algorithm . A greedy algorithm is often
used in solving optimization problems. The algorithm makes the choice that is optimal locally
in the hope that this choice will lead to a globally optimal solution. In this case, the algorithm
always chooses two trees with the smallest weight and creates a new node as their parent.
This intuitive optimal local solution indeed leads to a final optimal solution for constructing a
Huffman tree. As another example, consider changing money into the fewest possible coins.
A greedy algorithm would take the largest possible coin first. For example, for 98¢, you
would use three quarters to make 75¢, additional two dimes to make 95¢, and additional three
pennies to make the 98¢. The greedy algorithm finds an optimal solution for this problem.
However, a greedy algorithm is not always going to find the optimal result; see the bin pack-
ing problem in Programming Exercise 25.22.
Listing 25.12 gives a program that prompts the user to enter a string, displays the frequency
table of the characters in the string, and displays the Huffman code for each character.

greedy algorithm

L ISTING 25.12

HuffmanCode.java
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 text: " );
7 String text = input.nextLine();
8
9 int [] counts = getCharacterFrequency(text); // Count frequency 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

get Huffman tree
code for each character 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" ,