Huffman coding is a variable length encoding technique. More about it can be found here.
This program accepts the characters and their probability as the input. and generates the Huffman codes for each of the characters. I have used a Linked list which slowly transforms into a tree thereby creating the Huffman Tree. The codes are obtained by the inorder traversal.
class Node{
friend class HuffmanTree;
char ch;
float prob;
Node *lptr , *rptr , *next;
public:
Node(char _ch , float _prob , Node *_lptr = NULL , Node *_rptr = NULL , Node *_next = NULL){
lptr = _lptr;
rptr = _rptr;
next = _next;
prob = _prob;
ch = _ch;
}
};
The HuffmanTree looks like this..
class HuffmanTree{
Node *start , *Root;
public:
HuffmanTree(){
start = NULL;
}
void addNode(char , float);
void display();
void sort();
void findHuffmanCodes();
void inorder( Node * , string);
void printHuffmanCodes();
};
The code can be downloaded here
For testing i prefer redirecting a file as input. So i'm attaching the input file as well.. One can do the same..
$ g++ huffman.cpp
$ ./a.out < huffman.input
Here's the
