Topic: HuffmanCode

Policy: $1)$ Each lab is due at the end of each allocated Lab Section. The TA will be available to

help you for the lab$/$homework$.$

$2)$ Exception: if you plan to do the lab in advance, you must submit your lab answer before the

start of your allocated lab section.

Instruction:

$1)$ Finish public HuffmanNode encode$($ char$[]$ charArray, int$[]$ charfreq$)$;

$2)$ Finish public String decodeFile$($HuffmanNode root, String s$).$import java.util.Comparator;

import java.util.PriorityQueue;

public class Lab$6$CS$3\{$

public static void main$($String$[]$ args$)\{$

$//$ number of characters.

int n $=6$;

char$[]$ charArray $=\{\text{'}$A$\text{'},\text{'}$B$\text{'},\text{'}$I$\text{'},\text{'}$M$\text{'},\text{'}$S$\text{'},\text{'}$X$\text{'},\text{'}$Z$\text{'}\}$;

int$[]$ charfreq $=\{12,7,18,10,9,5,2\}$;

HuffmanCode hc $=$ new HuffmanCode$()$;

HuffmanNode root $=$ hc$.$encode$($charArray$,$charfreq$)$;

$//$ print the codes by traversing the tree

hc$.$printCode$($root$,"")$;

System.out.println$($hc$.$decodeFile$($root$,"01100010101010"))$;

System.out.println$($hc$.$decodeFile$($root$,"1000100001010"))$;

System.out.println$($hc$.$decodeFile$($root$,"11100100111101"))$;

System.out.println$($hc$.$decodeFile$($root$,"1000010011100"))$;

$\}$

$\}$

class HuffmanCode $\{$

$//$ recursive function to print the

$//$ huffman$-$code through the tree traversal.

$//$ Here s is the huffman $-$ code generated.

public void printCode$($HuffmanNode root, String s$)$

$\{$

$//$ base case; if the left and right are null

$//$ then its a leaf node and we print

$//$ the code s generated by traversing the tree.

if $($root$.$left $==$ null && root.right $==$ null

&& Character.isLetter$($root$.$c$))\{$

$//$ c is the character in the node

System.out.println$($root$.$c $+"$:$"+$ s$)$;

return;

$\}$

$//$ if we go to left then add $"0"$ to the code.

$//$ if we go to the right add"$1"$ to the code.

$//$ recursive calls for left and

$//$ right sub$-$tree of the generated tree.

printCode$($root$.$left, s $+"0")$;

printCode$($root$.$right, s $+"1")$;

$\}$

public HuffmanNode encode$($ char$[]$ charArray, int$[]$ charfreq$)\{$

HuffmanNode root $=$ null; $//$ create a root node

$//$ creating a priority queue q$.$

$//$ makes a min$-$priority queue$($min$-$heap$).$

$//$ creating a Huffman node object

$//$ and add it to the priority queue.

$//$ Here we will extract the two minimum value

$//$ from the heap each time until

$//$ its size reduces to $1,$ extract until

$//$ all the nodes are extracted.

return root; $//$replace it with root

$\}$

public String decodeFile$($HuffmanNode root, String s$)\{$

String ans $=""$;

HuffmanNode curr $=$ root;

$//$finish your code

return ans $+\text{'}\backslash 0\text{'}$;

$\}$

$\}$

$//$node class is the basic structure

$//$of each node present in the Huffman $-$ tree.

class HuffmanNode $\{$

int data; $//$store frequency

char c; $//$store character

HuffmanNode left;

HuffmanNode right;

$\}$

$//$comparator class helps to compare the node

$//$on the basis of one of its attribute.

$//$Here we will be compared

$//$on the basis of data values of the nodes.

class MyComparator implements Comparator $\{$

public int compare$($HuffmanNode x$,$ HuffmanNode y$)$

$\{$

return x$.$data $-$ y$.$data;

$\}$

$\}$