In this assignment, you will be implementing Huffman coding scheme which is used to

compress files or images to save space as well as for efficient transmission over networks. It is a

variable length binary coding scheme where each symbol can have a different code length and it

has a prefix property in that no code for a symbol is a prefix of code for another symbol. This is

possible due to the binary tree representation of Huffman coding where the leaves are the

symbols and the labels $(0$ or $1)$ on the edges in the path from the root to a leaf node when

concatenated give the code for that symbol. An example is given below:

Huffman coding minimizes the expected $($average$)$ length of a code for a symbol based on the

probabilities $($frequencies$)$ of using the symbol. It is equivalent to minimizing the number of

bits required to encode a file. This is done by using a greedy algorithm where in each step, we

merge two binary trees with $2$ least frequency values into a single tree with the new frequency

the sum of the frequencies of the two trees merged. Initially each symbol is a single node binary

tree with its frequency. We use Java PriorityQueue $($binary heap$)$ class for identifying nodes

with $2$ least frequency values and replacing them with a new node.

Example given below:

You need to complete the following in HuffmanTreeNode inner class:

public HuffmanTreeNode$($double weight,HuffmanTreeNode left,

HuffmanTreeNode right$)\{..\}$

You need to complete the following in HuffmanTreeCoder class:

public void buildTree$($Map freqMap$)\{..\}$

private void encodeChars$($HuffmanTreeNode node, String prefix$)$

$\{..\}$

Download the following files:

HuffmanTreeNavigator.java $($relies on BinTreeNavigator class used in previous assignment$)$

HuffmanTreeCoder.java $($inner class HuffmanTreeNode relies on BinTreeNode used in

previous assignment$)$