PROBLEM DESCRIPTION
Given a string S, implement Huffman Encoding and Decoding.
SOLUTION
- Start with an empty string
ansto store the decoded characters. - Initialize another node
curr, which is set to the root of the Huffman tree. - Loop through each bit in the string
s.- If the bit is ‘0’, move
currto its left child. - If the bit is ‘1’, move
currto its right child. - If
curris at a leaf node (it has no children), this means you have reached a decoded character.- Add the character to
ans. - Set
currback to the root of the Huffman tree.
- Add the character to
- If the bit is ‘0’, move
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class GfG {
String decode_file(minHeapNode root, String encodedStr){
int n = encodedStr.length();
StringBuilder sb = new StringBuilder();
minHeapNode ptr = root;
for(int i=0; i<n; i++){
char ch = encodedStr.charAt(i);
if(ch == '0'){
ptr = ptr.left;
}else
ptr = ptr.right;
if(ptr.left == null && ptr.right == null){
sb.append(ptr.data);
ptr = root;
}
}
return sb.toString();
}
}