Huffman Tree Example

// C program 
// Huffman Tree Example 
#include <stdio.h>

#include <stdlib.h>

// Tree node 
struct TreeNode
{
    // Character element
    char element;
    // Element frequency
    int freq;
    // Left subtree
    struct TreeNode *left;
    // Right subtree
    struct TreeNode *right;
};
// Min heap
struct MinHeap
{
    int size;
    int capacity;
    // Use to collect record
    struct TreeNode **record;
};
// Huffman Tree
struct HuffmanTree
{
    struct TreeNode *root;
};
// Create and return new tree
struct HuffmanTree *newTree()
{
    // Create a dynamic tree
    struct HuffmanTree *tree = (struct HuffmanTree *) malloc(sizeof(struct HuffmanTree));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
        exit(0);
    }
    // Return new tree
    return tree;
}
// Create new tree node
struct TreeNode *newNode(char element, int freq)
{
    // Allocate memory of new nodes
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node == NULL)
    {
        printf("Memory Overflow to Create tree node\n");
        exit(0);
    }
    node->element = element;
    node->freq = freq;
    // set node child
    node->left = NULL;
    node->right = NULL;
    return node;
}
struct MinHeap *createMinHeap(int capacity)
{
    struct MinHeap *heap = (struct MinHeap *) malloc(sizeof(struct MinHeap));
    if (heap == NULL)
    {
        printf("Memory Overflow to create Min Heap \n");
        exit(0);
    }
    // Initial number of element
    heap->size = 0;
    // Allocate the memory of record element
    heap->record = (struct TreeNode **) malloc(capacity *sizeof(struct TreeNode *));
    // Set heap capacity
    heap->capacity = capacity;
    return heap;
}
void minHeapify(struct MinHeap *minHeap, int idx)
{
    int smallest = idx;
    // Left child
    int left = 2 *idx + 1;
    // Right child
    int right = 2 *idx + 2;
    if (left < minHeap->size && minHeap->record[left]->freq < minHeap->record[smallest]->freq)
    {
        smallest = left;
    }
    if (right < minHeap->size && minHeap->record[right]->freq < minHeap->record[smallest]->freq)
    {
        smallest = right;
    }
    if (smallest != idx)
    {
        struct TreeNode *temp = minHeap->record[smallest];
        minHeap->record[smallest] = minHeap->record[idx];
        minHeap->record[idx] = temp;
        minHeapify(minHeap, smallest);
    }
}
struct TreeNode *extractMin(struct MinHeap *minHeap)
{
    struct TreeNode *temp = minHeap->record[0];
    minHeap->record[0] = minHeap->record[minHeap->size - 1];
    minHeap->size = minHeap->size - 1;
    minHeapify(minHeap, 0);
    return temp;
}
void insertMinHeap(struct MinHeap *minHeap, struct TreeNode *minHeapNode)
{
    int i = minHeap->size;
    minHeap->size = minHeap->size + 1;
    while (i != 0 && minHeapNode->freq < minHeap->record[(i - 1) / 2]->freq)
    {
        minHeap->record[i] = minHeap->record[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->record[i] = minHeapNode;
}
void buildMinHeap(struct MinHeap *minHeap)
{
    int n = minHeap->size - 1;
    for (int i = (n - 1) / 2; i >= 0; --i)
    {
        minHeapify(minHeap, i);
    }
}

struct MinHeap *createAndBuildMinHeap(char element[], int freq[], int size)
{
    struct MinHeap *minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
    {
        minHeap->record[i] = newNode(element[i], freq[i]);
    }
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}
struct TreeNode *buildHuffmanTree(char element[], int freq[], int size)
{
    struct TreeNode *left = NULL;
    struct TreeNode *right = NULL;
    struct TreeNode *top = NULL;

    struct MinHeap *minHeap = createAndBuildMinHeap(element, freq, size);

    while (minHeap->size != 1)
    {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        // # indicates internal node 
        top = newNode('#', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

// Calculate height of tree
int treeHeight(struct TreeNode *node)
{
    if (node != NULL)
    {
        // Find height of subtree using recursion
        int a = treeHeight(node->left);
        int b = treeHeight(node->right);
        // Returns the height of largest subtree 
        if (a > b)
        {
            return a + 1;
        }
        else
        {
            return b + 1;
        }
    }
    else
    {
        return 0;
    }
}

void printData(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d", arr[i]);
    }
    printf("\n");
}

//  Find huffman code using recursion
void printCodes(struct TreeNode *root, int record[], int top)
{
    if (root->left != NULL)
    {
        // visit left
        record[top] = 0;
        printCodes(root->left, record, top + 1);
    }
    if (root->right != NULL)
    {
        // visit right
        record[top] = 1;
        printCodes(root->right, record, top + 1);
    }
    if (root->left == NULL && root->right == NULL)
    {
        // When get leaf node
        printf("%c : ", root->element);
        printData(record, top);
    }
}

// Handles the request of printing huffman code
void huffmanCodes(struct TreeNode *root)
{
    if (root == NULL)
    {
        return;
    }
    // Find height of tree
    int height = treeHeight(root);

    // This is used to collect human code
    int record[height];

    // print huffman codes
    printCodes(root, record, 0);
}
int main()
{
    char element[] = {
        'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
    };
    int frequency[] = {
        16 , 8 , 19 , 32 , 21 , 10 , 5
    };
    // Get the number of element
    int size = sizeof(element) / sizeof(element[0]);
    // Create tree
    struct HuffmanTree *tree = newTree();
    // Construct tree
    tree->root = buildHuffmanTree(element, frequency, size);
    huffmanCodes(tree->root);
    return 0;
}

input

e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111