JAVA: Write an application to test the HuffmanTree class. Your application will need to read a text file and build a frequency table for the characters occurring in that file. Once that table is built, create a Huffman code tree and then a string consisting of '0' and '1' digit characters that represents the code string for that file. Read that string back in and recreate the contents of the original file.

HuffMan Tree Class:

import java.io.*; import java.util.*;

public class HuffmanTree implements Serializable { public static class HuffData implements Serializable { private double weight; private Character symbol;

public HuffData(double weight, Character symbol) { this.weight = weight; this.symbol = symbol; }

public Character getSymbol() {return symbol;} } protected BinaryTree huffTree; private static class CompareHuffmanTrees implements Comparator> {

@Override public int compare(BinaryTree treeLeft,BinaryTree treeRight) { double wLeft = treeLeft.getData().weight; double wRight = treeRight.getData().weight; return Double.compare(wLeft, wRight); } }

public void buildTree(HuffData[] symbols) { Queue> theQueue = new PriorityQueue>(symbols.length,new CompareHuffmanTrees()); for (HuffData nextSymbol : symbols) { BinaryTree aBinaryTree = new BinaryTree(nextSymbol, null, null); theQueue.offer(aBinaryTree); }

// Build the tree. while (theQueue.size() > 1) { BinaryTree left = theQueue.poll(); BinaryTree right = theQueue.poll(); double wl = left.getData().weight; double wr = right.getData().weight; HuffData sum = new HuffData(wl + wr, null); BinaryTree newTree = new BinaryTree(sum, left, right); theQueue.offer(newTree); } huffTree = theQueue.poll(); }

private void printCode(PrintStream out, String code, BinaryTree tree) { HuffData theData = tree.getData(); if (theData.symbol != null) { if (theData.symbol.equals(' ')) { out.println("space: " + code); } else { out.println(theData.symbol + ": " + code); } } else { printCode(out, code + "0", tree.getLeftSubtree()); printCode(out, code + "1", tree.getRightSubtree()); } }

public void printCode(PrintStream out) { printCode(out, "", huffTree); } public String decode(String codedMessage) { StringBuilder result = new StringBuilder(); BinaryTree currentTree = huffTree; for (int i = 0; i < codedMessage.length(); i++) { if (codedMessage.charAt(i) == '1') { currentTree = currentTree.getRightSubtree(); } else { currentTree = currentTree.getLeftSubtree(); } if (currentTree.isLeaf()) { HuffData theData = currentTree.getData(); result.append(theData.symbol); currentTree = huffTree; } } return result.toString(); } public static void main(String [] args) { HuffmanTree hf = new HuffmanTree(); double freq[]=new double[12];

try { HuffmanTree.HuffData hd[]=new HuffmanTree.HuffData[256]; Scanner input = new Scanner(new FileInputStream("huff.txt")); while(input.hasNext()) { System.out.println("pizza"); } } catch(FileNotFoundException e) { System.out.println("File huff.txt was not found "); System.out.println("or could not be opened. "); System.exit(0); } }

}

BINARY TREE CLASS:

import java.io.BufferedReader; import java.io.IOException; import java.io.Serializable;

public class BinaryTree implements Serializable {

protected static class Node implements Serializable { public E data; public Node left; public Node right;

public Node(E data) { this.data = data; left = null; right = null; }

@Override public String toString() { return data.toString(); } }

protected Node root;

public BinaryTree() { root = null; }

protected BinaryTree(Node root) { this.root = root; }

public BinaryTree(E data, BinaryTree leftTree, BinaryTree rightTree) { root = new Node(data); if (leftTree != null) { root.left = leftTree.root; } else { root.left = null; } if (rightTree != null) { root.right = rightTree.root; } else { root.right = null; } }

public BinaryTree getLeftSubtree() { if (root != null && root.left != null) { return new BinaryTree(root.left); } else { return null; } }

public BinaryTree getRightSubtree() { if (root != null && root.right != null) { return new BinaryTree(root.right); } else { return null; } }

public E getData() { if (root != null) { return root.data; } else { return null; } }

public boolean isLeaf() { return (root == null || (root.left == null && root.right == null)); }

@Override public String toString() { StringBuilder sb = new StringBuilder(); preOrderTraverse(root, 1, sb); return sb.toString(); }

private void preOrderTraverse(Node node, int depth, StringBuilder sb) { for (int i = 1; i < depth; i++) { sb.append(" "); } if (node == null) { sb.append("null "); } else { sb.append(node.toString()); sb.append(" "); preOrderTraverse(node.left, depth + 1, sb); preOrderTraverse(node.right, depth + 1, sb); } }

public static BinaryTree readBinaryTree(BufferedReader bR) throws IOException { // Read a line and trim leading and trailing spaces. String data = bR.readLine().trim(); if (data.equals("null")) { return null; } else { BinaryTree leftTree = readBinaryTree(bR); BinaryTree rightTree = readBinaryTree(bR); return new BinaryTree(data, leftTree, rightTree); } }

public String preorderToString() { StringBuilder stb = new StringBuilder(); preorderToString(stb, root); return stb.toString(); }

private void preorderToString(StringBuilder stb, Node root) { stb.append(root); if (root.left != null) { stb.append(" "); preorderToString(stb, root.left); } if (root.right != null) { stb.append(" "); preorderToString(stb, root.right); } }

public String postorderToString() { StringBuilder stb = new StringBuilder(); postorderToString(stb, root); return stb.toString(); }

private void postorderToString(StringBuilder stb, Node root) { if (root.left != null) { postorderToString(stb, root.left); stb.append(" "); } if (root.right != null) { postorderToString(stb, root.right); stb.append(" "); } stb.append(root); }

public String inorderToString() { StringBuilder stb = new StringBuilder(); inorderToString(stb, root); return stb.toString(); }

private void inorderToString(StringBuilder stb, Node root) { if (root.left != null) { stb.append("("); inorderToString(stb, root.left); stb.append(") "); } stb.append(root); if (root.right != null) { stb.append(" ("); inorderToString(stb, root.right); stb.append(")"); } } }