In this HackerRank Tree: Huffman Decoding Interview preparation kit problem You are given a pointer to the root of the Huffman tree and a binary coded string to decode. You need to print the decoded string.
Problem solution in Python programming.
import queue as Queue
cntr = 0
class Node:
def __init__(self, freq, data):
self.freq = freq
self.data = data
self.left = None
self.right = None
global cntr
self._count = cntr
cntr = cntr + 1
def __lt__(self, other):
if self.freq != other.freq:
return self.freq < other.freq
return self._count < other._count
def huffman_hidden():#builds the tree and returns root
q = Queue.PriorityQueue()
for key in freq:
q.put((freq[key], key, Node(freq[key], key) ))
while q.qsize() != 1:
a = q.get()
b = q.get()
obj = Node(a[0] + b[0], '\0' )
obj.left = a[2]
obj.right = b[2]
q.put((obj.freq, obj.data, obj ))
root = q.get()
root = root[2]#contains root object
return root
def dfs_hidden(obj, already):
if(obj == None):
return
elif(obj.data != '\0'):
code_hidden[obj.data] = already
dfs_hidden(obj.right, already + "1")
dfs_hidden(obj.left, already + "0")
"""class Node:
def __init__(self, freq,data):
self.freq= freq
self.data=data
self.left = None
self.right = None
"""
# Enter your code here. Read input from STDIN. Print output to STDOUT
def decodeHuff(root, s):
#Enter Your Code Here
cur = root
chararray = []
#For each character,
#If at an internal node, move left if 0, right if 1
#If at a leaf (no children), record data and jump back to root AFTER processing character
for c in s:
if c == '0' and cur.left:
cur = cur.left
elif cur.right:
cur = cur.right
if cur.left is None and cur.right is None:
chararray.append(cur.data)
cur = root
#Print final array
print("".join(chararray))
ip = input()
freq = {}#maps each character to its frequency
cntr = 0
for ch in ip:
if(freq.get(ch) == None):
freq[ch] = 1
else:
freq[ch]+=1
root = huffman_hidden()#contains root of huffman tree
code_hidden = {}#contains code for each object
dfs_hidden(root, "")
if len(code_hidden) == 1:#if there is only one character in the i/p
for key in code_hidden:
code_hidden[key] = "0"
toBeDecoded = ""
for ch in ip:
toBeDecoded += code_hidden[ch]
decodeHuff(root, toBeDecoded)Problem solution in Java Programming.
import java.util.*;
abstract class Node implements Comparable<Node> {
public int frequency; // the frequency of this tree
public char data;
public Node left, right;
public Node(int freq) {
frequency = freq;
}
// compares on the frequency
public int compareTo(Node tree) {
return frequency - tree.frequency;
}
}
class HuffmanLeaf extends Node {
public HuffmanLeaf(int freq, char val) {
super(freq);
data = val;
}
}
class HuffmanNode extends Node {
public HuffmanNode(Node l, Node r) {
super(l.frequency + r.frequency);
left = l;
right = r;
}
}
class Decoding {
/*
class Node
public int frequency; // the frequency of this tree
public char data;
public Node left, right;
*/
void decode(String S, Node root)
{
StringBuilder sb = new StringBuilder();
Node c = root;
for (int i = 0; i < S.length(); i++) {
c = S.charAt(i) == '1' ? c.right : c.left;
if (c.left == null && c.right == null) {
sb.append(c.data);
c = root;
}
}
System.out.print(sb);
}
}
public class Solution {
// input is an array of frequencies, indexed by character code
public static Node buildTree(int[] charFreqs) {
PriorityQueue<Node> trees = new PriorityQueue<Node>();
// initially, we have a forest of leaves
// one for each non-empty character
for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));
assert trees.size() > 0;
// loop until there is only one tree left
while (trees.size() > 1) {
// two trees with least frequency
Node a = trees.poll();
Node b = trees.poll();
// put into new node and re-insert into queue
trees.offer(new HuffmanNode(a, b));
}
return trees.poll();
}
public static Map<Character,String> mapA=new HashMap<Character ,String>();
public static void printCodes(Node tree, StringBuffer prefix) {
assert tree != null;
if (tree instanceof HuffmanLeaf) {
HuffmanLeaf leaf = (HuffmanLeaf)tree;
// print out character, frequency, and code for this leaf (which is just the prefix)
//System.out.println(leaf.data + "\t" + leaf.frequency + "\t" + prefix);
mapA.put(leaf.data,prefix.toString());
} else if (tree instanceof HuffmanNode) {
HuffmanNode node = (HuffmanNode)tree;
// traverse left
prefix.append('0');
printCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length()-1);
// traverse right
prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String test= input.next();
// we will assume that all our characters will have
// code less than 256, for simplicity
int[] charFreqs = new int[256];
// read each character and record the frequencies
for (char c : test.toCharArray())
charFreqs[c]++;
// build tree
Node tree = buildTree(charFreqs);
// print out results
printCodes(tree, new StringBuffer());
StringBuffer s = new StringBuffer();
for(int i = 0; i < test.length(); i++) {
char c = test.charAt(i);
s.append(mapA.get(c));
}
//System.out.println(s);
Decoding d = new Decoding();
d.decode(s.toString(), tree);
}
}Problem solution in C++ programming.
//
// main.cpp
// Huffman
//
// Created by Vatsal Chanana
#include<bits/stdc++.h>
using namespace std;
typedef struct node {
int freq;
char data;
node * left;
node * right;
} node;
struct deref:public binary_function<node*, node*, bool> {
bool operator()(const node * a, const node * b)const {
return a->freq > b->freq;
}
};
typedef priority_queue<node *, vector<node*>, deref> spq;
node * huffman_hidden(string s) {
spq pq;
vector<int>count(256,0);
for(int i = 0; i < s.length(); i++ ) {
count[s[i]]++;
}
for(int i=0; i < 256; i++) {
node * n_node = new node;
n_node->left = NULL;
n_node->right = NULL;
n_node->data = (char)i;
n_node->freq = count[i];
if( count[i] != 0 )
pq.push(n_node);
}
while( pq.size() != 1 ) {
node * left = pq.top();
pq.pop();
node * right = pq.top();
pq.pop();
node * comb = new node;
comb->freq = left->freq + right->freq;
comb->data = '\0';
comb->left = left;
comb->right = right;
pq.push(comb);
}
return pq.top();
}
void print_codes_hidden(node * root, string code, map<char, string>&mp) {
if(root == NULL)
return;
if(root->data != '\0') {
mp[root->data] = code;
}
print_codes_hidden(root->left, code+'0', mp);
print_codes_hidden(root->right, code+'1', mp);
}
/*
The structure of the node is
typedef struct node {
int freq;
char data;
node * left;
node * right;
} node;
*/
void decode_huff(node * root,string s)
{
string ans = "";
node* n = root;
for(auto itr = s.begin(); itr != s.end();itr++){
node* next;
if(*itr == '0'){
next = n -> left;
}
else{
next = n -> right;
}
if(next -> data == '\0'){
n = next;
}
else{
ans += next -> data;
n = root;
}
}
cout << ans << endl;
}
int main() {
string s;
std::cin >> s;
node * tree = huffman_hidden(s);
string code = "";
map<char, string>mp;
print_codes_hidden(tree, code, mp);
string coded;
for( int i = 0; i < s.length(); i++ ) {
coded += mp[s[i]];
}
decode_huff(tree,coded);
return 0;
} 
0 Comments