Method to create binary tree for huffman coding from the given input character sequence .......

                                                               csl210_lab3.h 

/**

 * Lab assignment 3

 * CSL 210 2021

 * Deadline: Friday Oct 29 11pm.

 * Submit the c implementation file for this header file

 * Filename should be of format YourEnrollmentNumber_lab3.c (lower case); e.g., bt20cse999_lab3.c

 *

 * 

 * Compilation error = 0

 * Late submission = 0

 * Presence of uncommented main function in the submission file = 0

 * Cheating/plagiarism = 0

 * */

#define EMPTYNODE 0

struct btNode{

    unsigned short frequency;

    char value;

    struct btNode* left;

    struct btNode* right;

};

typedef struct btNode btNode_t;

/**

 * Method to create binary tree for huffman coding from the given input character sequence  

 * Input will be an array of characters. Size of the input array is the second parameter.

 * The input will consist of lower case letters from the English alphabet.   

 * Your function will calculate frequency of individual characters in the input array.

 * For example 'qwertyqqwfrtggggbryyyyyyyeeeeqqqqqqq' will be the input array.

 * Your implementation will calculate the frequency of occurrence of individual characters ('q', 'w', 'e', 'r' etc.). 

 * Based on the frequency of individual characters, you will build the binary tree for huffman coding.

 * 

 * Return the root node of the huffman tree

 * */

btNode_t* createHuffmanTree(char input[], unsigned short sz);

                                                         MAIN.c

#include <stdio.h>

#include <stdlib.h>

#include "csl210_lab3.h"

#define MAX_TREE_HT 50

struct MinHeap

{

  unsigned short size;

  unsigned short capacity;

  struct btNode **array;

};

void print_Array(short arr[], short k)

{

  short m;

  for (m = 0; m < k; ++m)

    printf("%d", arr[m]);

  printf("\n");

}

struct btNode *newNode(char val, unsigned short frequency)

{

  struct btNode *temp = (struct btNode *)malloc(sizeof(struct btNode));

  temp->left = temp->right = NULL;

  temp->value = val;

  temp->frequency = frequency;

  return temp;

}

struct MinHeap *create_MinHe(unsigned short capacity)

{

  struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));

  minHeap->size = 0;

  minHeap->capacity = capacity;

  minHeap->array = (struct btNode **)malloc(minHeap->capacity * sizeof(struct btNode *));

  return minHeap;

}

void swap(struct btNode **g, struct btNode **h)

{

  struct btNode *temp = *g;

  *g = *h;

  *h = temp;

}

void minHeapify(struct MinHeap *minHeap, short index)

{

  short smallest = index;

  short left = 2 * index + 1;

  short right = 2 * index + 2;

  if (left < minHeap->size && minHeap->array[left]->frequency < minHeap->array[smallest]->frequency)

    smallest = left;

  if (right < minHeap->size && minHeap->array[right]->frequency < minHeap->array[smallest]->frequency)

    smallest = right;

  if (smallest != index)

  {

    swap(&minHeap->array[smallest], &minHeap->array[index]);

    minHeapify(minHeap, smallest);

  }

}

short check_size(struct MinHeap *minHeap)

{

  return (minHeap->size == 1);

}

struct btNode *extract_Min(struct MinHeap *minHeap)

{

  struct btNode *temp = minHeap->array[0];

  minHeap->array[0] = minHeap->array[minHeap->size - 1];

  --minHeap->size;

  minHeapify(minHeap, 0);

  return temp;

}

void insert_MinHeap(struct MinHeap *minHeap, struct btNode *minHeapNode)

{

  ++minHeap->size;

  short i = minHeap->size - 1;

  while (i && minHeapNode->frequency < minHeap->array[(i - 1) / 2]->frequency)

  {

    minHeap->array[i] = minHeap->array[(i - 1) / 2];

    i = (i - 1) / 2;

  }

  minHeap->array[i] = minHeapNode;

}

void buildMinHeap(struct MinHeap *minHeap)

{

  short n = minHeap->size - 1;

  short i;

  for (i = (n - 1) / 2; i >= 0; --i)

    minHeapify(minHeap, i);

}

short isLeaf(struct btNode *root)

{

  return !(root->left) && !(root->right);

}

struct MinHeap *Create_Heap(char value[], short frequency[], short size)

{

  struct MinHeap *minHeap = create_MinHe(size);

  for (short l = 0; l < size; ++l)

    minHeap->array[l] = newNode(value[l], frequency[l]);

  minHeap->size = size;

  buildMinHeap(minHeap);

  return minHeap;

}

struct btNode *buildTree(char value[], short frequency[], short size)

{

  struct btNode *left, *right, *top;

  struct MinHeap *minHeap = Create_Heap(value, frequency, size);

  while (!check_size(minHeap))

  {

    left = extract_Min(minHeap);

    right = extract_Min(minHeap);

    top = newNode('$', left->frequency + right->frequency);

    top->left = left;

    top->right = right;

    insert_MinHeap(minHeap, top);

  }

  return extract_Min(minHeap);

}

void printHCodes(struct btNode *root, short arr[], short top)

{

  if (root->left)

  {

    arr[top] = 0;

    printHCodes(root->left, arr, top + 1);

  }

  if (root->right)

  {

    arr[top] = 1;

    printHCodes(root->right, arr, top + 1);

  }

  if (isLeaf(root))

  {

    printf("  %c   | ", root->value);

    print_Array(arr, top);

  }

}

short freq_q(char *arr[])

{

  short freq[256] = {0};

  for (short i = 0; *(arr[i]) != '\0'; i++)

  {

    freq[*(arr[i])]++;

  }

}

btNode_t *createHuffmanTree(char input[], unsigned short sz)

{

  short arr[sz];

  struct btNode *root = buildTree(input, arr, sz);

  short arr1[MAX_TREE_HT], top = 0;

  printHCodes(root, arr1, top);

}