In this question, you will practice using binary trees in a real-world application. Huffman encoding is a technique for encoding characters using a variable number of bits for each character. More frequent characters are encoded with fewer bits, resulting in a compression of the number of bits required to encode a complete file (this is one technique used in the PKZIP program to compress .zip files). A Huffman encoding of the alphabet {A, B, C, D, E} can be represented as a binary tree like the one shown in Figure 1, with the characters stored at the leaves. To find the encoding for any character, you simply follow the path from the root to the leaf containing that character. If you go to a left child, you add a 0 to the encoding. If you go to the right, you add a 1. For example, the encoding for the letter E is 101.

For this lab, your task is to complete the provided Huffman tree program (see attached to the question) by implementing the decode() method. Your method should read in the input string of 0s and 1s, and starting with the first digit, follow the specified path starting from the root. When you hit a leaf, print the stored character and re-start traversing from the root. You will know when you have correctly implemented the program when you decode the message encoded in the main() method.

Source Code:

import java.util.*;

public class Tree {

Node root

public Tree(){

PriorityQueue characters = new PriorityQueue<>();

characters.add(new Node(3,' '));

characters.add(new Node(2, 'a'));

characters.add(new Node(2, 'e'));

characters.add(new Node(2, 'm'));

characters.add(new Node(2, 'o'));

characters.add(new Node(1, 'd'));

characters.add(new Node(1, 'g'));

characters.add(new Node(1, 'h'));

characters.add(new Node(1, 'r'));

characters.add(new Node(1, 's'));

characters.add(new Node(1, 'u'));

characters.add(new Node(1, 'v'));

Node current = null;

while(characters.size() > 1){

Node left = characters.poll();

Node right = characters.poll();

current = new Node(left.freq + right.freq);

current.left = left;

current.right = right;

characters.add(current);

}

root = current;

}

public void decode(String s){

//IMPLEMENT: traverse the tree and print the letters in succession to reveal the message

}

public static void main(String[] args){

Tree lab = new Tree();

lab.decode("101110011000011111001111101100000010101111101001000110110010101");

}

//The Huffman tree node class: DO NOT MODIFY

private class Node implements Comparable{

char data;

int freq;

Node left;

Node right;

Node(int freq){

data = '~';

this.freq = freq;

left = null;

right = null;

}

Node(int freq, char c){

data = c;

this.freq = freq;

left = null;

right = null;

}

public int compareTo(Node node){

return (this.freq - node.freq);

}

public boolean isLeaf(){

return (left == null && right == null);

}

@Override

public String toString(){

String toReturn = freq + ": " + data;

return toReturn;

}

}

}