Tree.java: This is a simple binary tree class that should be used to represent the data in your Huffman tree. You only need to implement two of the methods (_printTree and compareTo). Huffman.java: This file contains all of the logic required to implement a Huffman tree. The code in this file relies on the Tree.java file. You must provide the implementation for all of the methods in this class. public class Main { /* * tree.txt should produce this tree: * 16 * / \ * 6 Z * / \ * A D * * A (1), D (5), Z (10) * * Codes: * A: 00 * D: 01 * Z: 1 * * Preorder Traversal: * 16, 6, 1 (A), 5 (D), 10 (Z) */ public static void main(String[] args) throws Exception { Huffman huff = new Huffman(); huff.buildTreeFromFile("tree.txt"); // Print the tree: System.out.println("printTree tests:"); huff.printTree(); // Expected output: [16: , 6: , 1:A, 5:D, 10:Z] // Get some codes: System.out.println("getCode tests:"); System.out.println(huff.getCode('A')); // Expected output: 00 System.out.println(huff.getCode('D')); // Expected output: 01 System.out.println(huff.getCode('Z')); // Expected output: 1 // Do some decoding: System.out.println("decode tests:"); System.out.println("1 decoded as: " + huff.decode("1")); // Expected output: Z System.out.println("00 decoded as: " + huff.decode("00")); // Expected output: A System.out.println("01 decoded as: " + huff.decode("01")); // Expected output: D System.out.println("1111100 decoded as: " + huff.decode("1111100")); // Expected output: ZZZZZA System.out.println("10001 decoded as: " + huff.decode("10001")); // Expected output: ZAD // Do some encoding: System.out.println("encode tests:"); System.out.println("ZAD encoded as: " + huff.encode("ZAD")); // Expected output: 10001 System.out.println("ZZZZZA encoded as: " + huff.encode("ZZZZZA")); // Expected output: 1111100 } } public class Tree implements Comparable { private Tree left; private Tree right; private char charecter; private int frequency; public Tree(Tree left, Tree right, char charecter, int frequency) { this.left = left; this.right = right; this.charecter = charecter; this.frequency = frequency; } public Tree getLeft() { return left; } public Tree getRight() { return right; } public int getFrequency() { return frequency; } public char getCharecter() { return charecter; } public void printTree() { _printTree(this); } public void _printTree(Tree n) { // add code here to print the tree // using a preorder traversal... } @Override public String toString() { return String.format("%s (%2d)", getCharecter(), getFrequency()); } @Override public int compareTo(Tree other) { // add code here to ensure that the natural ordering // sorts trees in ascending order based on the tree's frequency, // in the case of a tie sort in ascending order // based on the tree's letter... } } import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Huffman { private Tree root; private Map characterCodes; public Huffman() { characterCodes = new HashMap(); } public void buildTreeFromFile(String filePath) throws FileNotFoundException { List nodes = new ArrayList(); populateNodesFromFile(filePath, nodes); root = buildTreeFromNodes(nodes); buildCharacterCodes(root, ""); } private void populateNodesFromFile(String filePath, List nodes) throws FileNotFoundException { // This should populate the list nodes with Tree objects from the given file. // Each line of the file contains the character and then the weight for that // node separated by a comma. // So A,1 would mean a node with character 'A' and weight 1. } private Tree buildTreeFromNodes(List nodes) { } private void buildCharacterCodes(Tree tree, String code) { } public void printTree() { } public String getCode(char ch) { // This should perform in constant time: O(C) } public String encode(String value) { // This should perform in linear time O(n) // Iterate over the characters in value and build the encoded value. } public String decode(String code) { } }
Tree.java: This is a simple binary tree class that should be used to represent the data in your Huffman tree. You only need to implement two of the methods (_printTree and compareTo).
Huffman.java: This file contains all of the logic required to implement a Huffman tree. The code in this file relies on the Tree.java file. You must provide the implementation for all of the methods in this class.
public class Main {
/*
* tree.txt should produce this tree:
* 16
* / \
* 6 Z
* / \
* A D
*
* A (1), D (5), Z (10)
*
* Codes:
* A: 00
* D: 01
* Z: 1
*
* Preorder Traversal:
* 16, 6, 1 (A), 5 (D), 10 (Z)
*/
public static void main(String[] args) throws Exception {
Huffman huff = new Huffman();
huff.buildTreeFromFile("tree.txt");
// Print the tree:
System.out.println("printTree tests:");
huff.printTree(); // Expected output: [16: , 6: , 1:A, 5:D, 10:Z]
// Get some codes:
System.out.println("getCode tests:");
System.out.println(huff.getCode('A')); // Expected output: 00
System.out.println(huff.getCode('D')); // Expected output: 01
System.out.println(huff.getCode('Z')); // Expected output: 1
// Do some decoding:
System.out.println("decode tests:");
System.out.println("1 decoded as: " + huff.decode("1")); // Expected output: Z
System.out.println("00 decoded as: " + huff.decode("00")); // Expected output: A
System.out.println("01 decoded as: " + huff.decode("01")); // Expected output: D
System.out.println("1111100 decoded as: " + huff.decode("1111100")); // Expected output: ZZZZZA
System.out.println("10001 decoded as: " + huff.decode("10001")); // Expected output: ZAD
// Do some encoding:
System.out.println("encode tests:");
System.out.println("ZAD encoded as: " + huff.encode("ZAD")); // Expected output: 10001
System.out.println("ZZZZZA encoded as: " + huff.encode("ZZZZZA")); // Expected output: 1111100
}
}
public class Tree implements Comparable {
private Tree left;
private Tree right;
private char charecter;
private int frequency;
public Tree(Tree left, Tree right, char charecter, int frequency) {
this.left = left;
this.right = right;
this.charecter = charecter;
this.frequency = frequency;
}
public Tree getLeft() {
return left;
}
public Tree getRight() {
return right;
}
public int getFrequency() {
return frequency;
}
public char getCharecter() {
return charecter;
}
public void printTree() {
_printTree(this);
}
public void _printTree(Tree n) {
// add code here to print the tree
// using a preorder traversal...
}
@Override
public String toString() {
return String.format("%s (%2d)", getCharecter(), getFrequency());
}
@Override
public int compareTo(Tree other) {
// add code here to ensure that the natural ordering
// sorts trees in ascending order based on the tree's frequency,
// in the case of a tie sort in ascending order
// based on the tree's letter...
}
}
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Huffman {
private Tree root;
private Map<Character, String> characterCodes;
public Huffman() {
characterCodes = new HashMap<Character, String>();
}
public void buildTreeFromFile(String filePath) throws FileNotFoundException {
List<Tree> nodes = new ArrayList<Tree>();
populateNodesFromFile(filePath, nodes);
root = buildTreeFromNodes(nodes);
buildCharacterCodes(root, "");
}
private void populateNodesFromFile(String filePath, List<Tree> nodes) throws FileNotFoundException {
// This should populate the list nodes with Tree objects from the given file.
// Each line of the file contains the character and then the weight for that
// node separated by a comma.
// So A,1 would mean a node with character 'A' and weight 1.
}
private Tree buildTreeFromNodes(List<Tree> nodes) {
}
private void buildCharacterCodes(Tree tree, String code) {
}
public void printTree() {
}
public String getCode(char ch) {
// This should perform in constant time: O(C)
}
public String encode(String value) {
// This should perform in linear time O(n)
// Iterate over the characters in value and build the encoded value.
}
public String decode(String code) {
}
}
Step by step
Solved in 3 steps with 1 images
