Question

1. Create a Huffman Tree and generate the codes for each character of the following input:

create a huffman tree

For consistency:

1. If same frequency – put in priority queue alphabetically; put space before other characters of the same frequency

2. Add subtrees to end of group with same priority

3. Lower number has higher priority (goes to front)

Answer 1

import java.util.*;
class HN { // node class is the basic structure of each node present in the Huffman - tree.
int d;
char c;
HN l;
HN r;
}
  

class MyComparator implements Comparator<HN> { // comparator helps to compare the node
public int compare(HN x, HN y)
{
  
return x.d - y.d;
}
}
  
public class Main {
public static void pCode(HN r1, String s)
{
if (r1.l == null && r1.r == null && Character.isLetter(r1.c)) { // base case; if the l and r are null then its a leaf node and we print the code s generated by traversing the tree.
System.out.println(r1.c + ":" + s);
return;
}
pCode(r1.l, s + "0"); // if we go to l then add "0" to the code.
pCode(r1.r, s + "1"); // if we go to the r add"1" to the code.
}
  
  
public static void main(String[] args) // main function
{
  
Scanner s = new Scanner(System.in);
  
  
int n = 7; // number of characters.
char[] cArray = { 'm', 'i', 's', 'p','r','v','e'};
int[] cFreq = { 1, 5, 4, 2, 2, 1, 1 };
PriorityQueue<HN> q = new PriorityQueue<HN>(n, new MyComparator()); // creating a priority queue q.
  
for (int i = 0; i < n; i++) {
HN hn = new HN(); // creating a Huffman node object and add it to the priority queue.
hn.c = cArray[i];
hn.d = cFreq[i];
hn.l = null;
hn.r = null;
q.add(hn);// add functions adds the huffman node to the queue.
}
HN r1 = null; // create a r1 node
while (q.size() > 1) {
HN x = q.peek(); // first min extract.
q.poll();
HN y = q.peek(); // second min extarct.
q.poll();
HN f = new HN(); // new node f which is equal
f.d = x.d + y.d; // to the sum of the frequency of the two nodes assigning values to the f node.
f.c = '-';
f.l = x; // first extracted node as l child.
f.r = y; // second extracted node as the r child.
r1 = f; // marking the f node as the r1 node.
q.add(f); // add this node to the priority-queue.
}
pCode(r1, ""); // print the codes by traversing the tree
}
}

If you found this answer helpful please give a thumbs up.