Need help for creating the HuffmanTree.java and HuffmanNode.java . For the Huffm

Question

Need help for creating the HuffmanTree.java and HuffmanNode.java .

For the Huffman Node class will through the description of Huffman compression below and the following organization will become apparent. We are building a binary tree, where the "data" is a count of the frequency of each character.

   public class HuffmanNode implements Comparable<HuffmanNode> {

      public int frequency;

      public char character;

      public HuffmanNode left;

      public HuffmanNode right;

The HuffmanNode class will also need a boolean isLeaf() method, plus a static method to actually provide a count of the characters in an input file, and place those counts into a Map, with character as the unique key mapped into the integer counts of that character:

   public static Map<Character, Integer> getCounts(FileInputStream input)

Your Huffman Tree class must have the following defined:

   public HuffmanTree(Map<Character, Integer> counts) // Constructor

   public StringBuilder compress(InputStream inputFile) // inputFile is a text file

   public StringBuilder decompress(StringBuilder inputString) //inputString 1's & 0's

   public String printSideways()

Explanation / Answer

import java.lang.Math; /* Program to build a Huffman tree and Huffman code */ class Huffman { final static int NCHAR = 128; // the number of ASCII chars /* Class Tree is a Huffman tree. A Tree has a weight, the combined frequency of all the characters in its leaves A Tree is one of a Leaf, holding a character a Node, with left and right subtrees toString() Input: an instance (this) of a Huffman tree Output: a string-form represention a Leaf with character C is represented by #C a Node whose subtrees are represented by strings l and r is represented by *lr Example: o / / o o **#a#X*#**#c#d / / a X * o / c d The string-form is intended to be machine-readable and easy to reconstruct the tree from. buildCode(Code code, String path) Input: an instance (this) of a Huffman subtree a partially constructed code table a string of 0's and 1's that specifies the path from the Huffman root to the subtree Output: code-table entries are made for all leaves in subtree */ static abstract class Tree { //CLASS TREE int weight; abstract void buildCode(Code code, String path); public abstract String toString(); } static class Node extends Tree { //CLASS NODE Tree left, right; Node(Tree l, Tree r, int w) { left = l; right = r; weight = w; } public String toString() { return "##"; // REPLACE THIS CODE } void buildCode(Code code, String path) { // FILL IN THIS CODE } } static class Leaf extends Tree { char ch; Leaf(char c, int w) { ch = c; weight = w; } public String toString() { return "#" + ch; } void buildCode(Code code, String path) { code.table[ch] = path; } } /* Class Code embodies a code table indexed by character. The codes are given as character strings of "0" and "1" for simplicity, because Jave doesn't directly support bit strings. bitsPerChar(String text) Input: an instance (this) of a code table a text string Output: average number of bits per character in an encoding of the text according to the given code */ static class Code { String table[]; Code(Tree tree) { table = new String[NCHAR]; tree.buildCode(this, ""); } double bitsPerChar(String text) { int count = 0; for(int i=0; i

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.