Huffman Compression in C++ Implemented by James Pate Williams, Jr.

// Algorithm is found in the textbook
// "Introduction to Algorithms"
// by Thomas H. Cormen, Charles E.
// Leiserson, Ronald L. Rivest p. 340

#include "pch.h"

int leafNodes = 0;

void InorderTraversal(BinaryTreeNode<CharFreq>* node)
{
    if (node != NULL)
    {
        InorderTraversal(node->lt);

        if (node->lt == NULL && node->rt == NULL)
        {
            CharFreq cf = node->data;

            std::cout << setw(3) << leafNodes << '\t';
            std::cout << cf.ch << '\t';
            std::cout << setw(3) << cf.freq << '\n';
            leafNodes++;
        }
        
        InorderTraversal(node->rt);
    }
}

int main()
{
    int f[128] = { 0 };
    string str = "abbbccddeefffghhhhijkllmm";
    BinaryTreeNode<CharFreq> charFreqTree;
    vector<BinaryTreeNode<CharFreq>> v;

    std::cout << "The original string is: " << endl;
    std::cout << str << endl << endl;

    for (size_t i = 0; i < strlen(str.c_str()); i++)
    {
        bool found = false;
        char ch = str.c_str()[i];

        for (auto iter = v.begin(); !found &&
            iter != v.end(); iter++)
        {
            BinaryTreeNode<CharFreq> node = *iter;

            if (node.data.ch == ch)
            {
                node.data.freq++;
                *iter = node;
                found = true;
            }
        }

        if (!found)
        {
            BinaryTreeNode<CharFreq> node;

            node.data.ch = ch;
            node.data.freq = 1;
            node.lt = node.rt = NULL;
            v.push_back(node);
        }
    }

    priority_queue<BinaryTreeNode<CharFreq>, vector<BinaryTreeNode<CharFreq>>,
        greater<BinaryTreeNode<CharFreq>>> Q(v.begin(), v.end());

    size_t n = Q.size();
   
    for (size_t i = 0; i < n - 1; i++)
    {
        BinaryTreeNode<CharFreq>* x = new
            BinaryTreeNode<CharFreq>();
        BinaryTreeNode<CharFreq>* y = new
            BinaryTreeNode<CharFreq>();
        *x = Q.top();
        Q.pop();
        *y = Q.top();
        Q.pop();

        CharFreq charFreq;
        charFreq.ch = (char)(x->data.ch + y->data.ch);
        charFreq.freq = x->data.freq + y->data.freq;

        BinaryTreeNode<CharFreq>* z = new
            BinaryTreeNode<CharFreq>(charFreq, x, y);

        Q.push(*z);
    }

    BinaryTreeNode<CharFreq> root = Q.top();
    std::cout << "# characters = " << strlen(str.c_str()) << endl;
    std::cout << "The compressed codes and frequencies are:" << endl;
    InorderTraversal(&root);
    std::cout << "# leaf nodes = " << leafNodes << endl;
    std::cout << "% compressed = " <<
        (100.0 - 100.0 * ((double)leafNodes) / strlen(str.c_str())) << endl;
    return 0;
}

#pragma once
#include "pch.h"
using namespace std;

template <class T>
	class BinaryTreeNode
	{
	public:
		T data;
		BinaryTreeNode* lt;
		BinaryTreeNode* rt;

		BinaryTreeNode() { 
			lt = rt = nullptr;
		};

		BinaryTreeNode(T data)
		{
			this->data = data;
			lt = rt = nullptr;
		};

		BinaryTreeNode(T data, BinaryTreeNode* lt, BinaryTreeNode* rt)
		{
			this->data = data;
			this->lt = lt;
			this->rt = rt;
		};

		friend bool operator > (BinaryTreeNode lhs, BinaryTreeNode rhs)
		{
			return lhs.data > rhs.data;
		};

		friend bool operator < (BinaryTreeNode lhs, BinaryTreeNode rhs)
		{
			return lhs.data < rhs.data;
		};

		friend bool operator == (BinaryTreeNode lhs, BinaryTreeNode rhs)
		{
			return lhs.data == rhs.data;
		};
	};

#pragma once
class CharFreq
{
public:
	char ch;
	int freq;
	
	CharFreq()
	{
		ch = '\0';
		freq = 0;
	};
	CharFreq(char c)
	{
		ch = c;
		freq = 0;
	};
	CharFreq(char c, int f)
	{
		ch = c;
		freq = f;
	};

	friend int operator - (CharFreq lhs, CharFreq rhs)
	{
		return lhs.freq - rhs.freq;
	}

	friend bool operator > (CharFreq lhs, CharFreq rhs)
	{
		return lhs.freq > rhs.freq;
	};

	friend bool operator < (CharFreq lhs, CharFreq rhs)
	{
		return lhs.freq < rhs.freq;
	};

	friend bool operator == (CharFreq lhs, CharFreq rhs)
	{
		return lhs.freq == rhs.freq && lhs.ch == rhs.ch;
	};
};

// pch.h: This is a precompiled header file.
// Files listed below are compiled only once, improving build performance for future builds.
// This also affects IntelliSense performance, including code completion and many code browsing features.
// However, files listed here are ALL re-compiled if any one of them is updated between builds.
// Do not add files here that you will be updating frequently as this negates the performance advantage.

#ifndef PCH_H
#define PCH_H

// add headers that you want to pre-compile here
#include "BinaryTreeNode.h"
#include "CharFreq.h"
#include <iomanip>
#include <iostream>
#include <list>
#include <queue>
#include <string>
using namespace std;
#endif //PCH_H