You will construct a Huffman tree based on the given frequencies of 26 English alphabets in upper case plus the space character. An internal tree node class in HuffmanTree with necessary information is required.

You will not randomly switch left and right children when merger two trees. Instead, you will build a right-heavy tree according to the following strategies to select the right child.

(1) The tree that is taller will be the right child, i.e., the height is greater; (2) If the two tree of the same height, then the tree with more nodes will be the right child; (3) If (1) and (2) fail to discriminate, then the sum of the ASCII values of the alphabets in the tree is greater will be the right child. Use the same criteria if frequency is not sufficient to decide which two trees should be merged.

(1) HuffmanTree(char[] a, int[] f) This is a constructor that builds a Huffman tree based on a and f, where a is an array of characters to be encoded and f is an array of frequencies corresponding to the characters in a. For example, if a[3] = D and f[3] = 43, that means the frequency of D is 43.

(2) public void printCodeWords() This method prints out all codewords in the Huffman tree from left leaves to right leaves in the tree. Use the following format: Huffman Codes: E[69]:000 (127) H[72]:0010 (61) S[82]:0011 (63) ..... Z[90]:1111111111 (1) The 0-1 string indicates that 000 is the Huffman code for E, [69] indicates the ASCII value of character E, and (127) is the frequency; same to characters H, S and Z.

(3) public String encode(String text) This method will return a 0-1 String using the Huffman codes. For example, encode("EHS") should return "00000100011".

(4) public String decode(String codeString) The reverse of the function above. For example, decode("00000100011") returns "EHS". -------------------------------------------------------------------------------------------------------------------------- Here is the driver provided

This is my driver class, Asg7.java /** * You should not modify this program. You should develop your own * HuffmanTree.java and put it in the package, myUtil. * * @author cli2 * */ import myUtil.HuffmanTree;

public class Asg7 { // this example is extended from Corman's book static public void CormanFrequency() { int[] f = {82,15,29,43,127,22,20,61,70,5,8,40,24,67,75,19,4,60,63,91,28,10,23,2,21,1,123}; char[] a = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',' '}; HuffmanTree ht = new HuffmanTree(a, f); // Construct a Huffman Tree based on a and f ht.printCodeWords(); System.out.printf("%nCode: %s%n", ht.encodeToStr("HUFFMAN ENCODING IS VERY USEFUL")); System.out.printf("%nText: %s%n", ht.decodeFromStr("00100111011110011110011111011001000010000100001111101011010100110001101100101001001101010111110000110110111010011111010101010110")); System.out.printf("%nText: %s%n", ht.decodeFromStr("0111101101101111011101110101011011001101100101110001011011101010010011010111100011101000")); System.out.printf("%nText: %s%n", ht.decodeFromStr("11100010100100110101001001101011100010000010101101100001111100101100001100111001110110100011111000010001110")); } public static void main(String[] args) { CormanFrequency(); }

}