Huffman Encoding

HuffmanEncoding.cpp

#include<iostream>
#include<string>
#define debug(x) cout<< #x << " = "<< x <<endl
#define swap(typ,A,B) { typ temp;temp=B; B=A;A=temp;}
using namespace std;

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;
        }
};

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();
};

void HuffmanTree :: addNode(char ch , float prob){
    if(start == NULL){
        start = new Node(ch , prob);
        return;
    }
    Node *temp = start;
    while(temp -> next != NULL)
        temp = temp -> next;
    temp->next = new Node(ch , prob);
}

void HuffmanTree :: display(){
    Node *temp = start;
    while(temp != NULL){
        cout << temp->ch << " : " << temp->prob << endl;
        temp = temp -> next;
    }
    cout<<endl;
}

void HuffmanTree :: sort(){
    Node *outer=start, *inner=start;
    int swapped;
    while(outer-> next != NULL){
        inner = start;
        swapped = 0;
        while(inner-> next != NULL){
            if( inner -> prob > (inner -> next) -> prob ){
                swap(char , inner -> ch, (inner->next) -> ch);
                swap(float , inner -> prob, (inner -> next) -> prob);
                swap(Node* , inner -> lptr, inner -> next -> lptr);
                swap(Node* , inner -> rptr, inner -> next -> rptr);
                swapped = 1;
            }
            inner = inner -> next;
        }
        if(!swapped)    // return if there was no swap in the previous iteration;
            return;
        outer = outer -> next;
    }
}

void HuffmanTree :: findHuffmanCodes(){
    do{
        sort();
        Node *newnode = new Node('*',start->prob + start->next->prob, 
            start, start->next,start->next->next);
        Root = start = newnode;
    }while(Root->prob != 1);
}

void HuffmanTree :: inorder(Node *root , string code){
    string tempcode = code;
    if(root->lptr != NULL){
        tempcode.push_back('0');
        inorder(root->lptr , tempcode);
    }
    if(root->ch !='*' && root->prob !=0)
        cout<< root -> ch << " ("<< root -> prob << ") : "<< code << endl;
    if(root->rptr != NULL){
        code.push_back('1');
        inorder(root -> rptr , code);
    }
}

void HuffmanTree :: printHuffmanCodes(){
    string code="";
    inorder(Root , code);
    cout << endl;
}

int main(){
    HuffmanTree HT;
    int testcases , chars;
    cin >> testcases;
    char ch;
    float prob;
    for(int i = 0 ; i < testcases ; i++){
        cin >> chars;
        for(int j = 0 ; j < chars ; j++){
            cin >> ch >> prob;
            HT.addNode(ch , prob);
        }
    }
    HT.findHuffmanCodes();
    HT.printHuffmanCodes();
    return 0;
}