Derive the Huffman tree using Huffmans algorithm for the alp

Derive the Huffman tree using Huffman’s algorithm for the alphabet A = {a, b, c, d}, when the frequencies are given by f(a) = 1000, f(b) = 3000, f(c) = 2000, and f(d) = 5000. The minimum priority queue Q has initially the state 1) and after each iteration of Huffman’s algorithm the states 2), 3), and 4).

1) Q =

2) Q =

3) Q =

4) Q =

Solution

C++ CODE IMPLEMENTATION

#include <stdio.h>
#include <stdlib.h>

#define maximum_Tree_Height 100

struct Queue_Node
{
   char info;
   unsigned frequency;
   struct Queue_Node *left_child, *right_child;
};

struct Queue
{
   int FRONT, REAR;
   int Full_capacity;
   struct Queue_Node **Array_Queue;
};

struct Queue_Node* CreateNode(char info, unsigned frequency)
{
   struct Queue_Node* tmp =
   (struct Queue_Node*) malloc(sizeof(struct Queue_Node));
   tmp->left_child = tmp->right_child = NULL;
   tmp->info = info;
   tmp->frequency = frequency;
   return tmp;
}

struct Queue* Queue_creation(int Full_capacity)
{
   struct Queue* queue_var = (struct Queue*) malloc(sizeof(struct Queue));
   queue_var->FRONT = queue_var->REAR = -1;
   queue_var->Full_capacity = Full_capacity;
   queue_var->Array_Queue =
   (struct Queue_Node**) malloc(queue_var->Full_capacity * sizeof(struct Queue_Node*));
   return queue_var;
}

int Is_Size_One_Queue(struct Queue* queue_var)
{
   return queue_var->FRONT == queue_var->REAR && queue_var->FRONT != -1;
}

int is_Queue_Empty(struct Queue* queue_var)
{
   return queue_var->FRONT == -1;
}

int Is_queue_FULL(struct Queue* queue_var)
{
   return queue_var->REAR == queue_var->Full_capacity - 1;
}

void En_queue(struct Queue* queue_var, struct Queue_Node* item)
{
   if (Is_queue_FULL(queue_var))
       return;
   queue_var->Array_Queue[++queue_var->REAR] = item;
   if (queue_var->FRONT == -1)
       ++queue_var->FRONT;
}

struct Queue_Node* De_queue(struct Queue* queue_var)
{
   if (is_Queue_Empty(queue_var))
       return NULL;
   struct Queue_Node* tmp = queue_var->Array_Queue[queue_var->FRONT];
   if (queue_var->FRONT == queue_var->REAR)
       queue_var->FRONT = queue_var->REAR = -1;
   else
       ++queue_var->FRONT;
   return tmp;
}

struct Queue_Node* Get_front_node(struct Queue* queue_var)
{
   if (is_Queue_Empty(queue_var))
       return NULL;
   return queue_var->Array_Queue[queue_var->FRONT];
}

struct Queue_Node* Find_Min_node(struct Queue* Fisrt_Queue, struct Queue* Second_Queue)
{
   if (is_Queue_Empty(Fisrt_Queue))
       return De_queue(Second_Queue);

   if (is_Queue_Empty(Second_Queue))
       return De_queue(Fisrt_Queue);

   if (Get_front_node(Fisrt_Queue)->frequency < Get_front_node(Second_Queue)->frequency)
       return De_queue(Fisrt_Queue);

   return De_queue(Second_Queue);
}

int is_leafNode(struct Queue_Node* RootNode)
{
   return !(RootNode->left_child) && !(RootNode->right_child) ;
}
void Print_ARRAY(int arr[], int n)
{
   int i;
   for (i = 0; i < n; ++i)
       printf(\"%d\", arr[i]);
   printf(\"\ \");
}

struct Queue_Node* Build_Huffman_tree(char info[], int frequency[], int size)
{
   struct Queue_Node *left_child, *right_child, *top;

   struct Queue* Fisrt_Queue = Queue_creation(size);
   struct Queue* Second_Queue = Queue_creation(size);

   for (int i = 0; i < size; ++i)
       En_queue(Fisrt_Queue, CreateNode(info[i], frequency[i]));

   while (!(is_Queue_Empty(Fisrt_Queue) && Is_Size_One_Queue(Second_Queue)))
   {

       left_child = Find_Min_node(Fisrt_Queue, Second_Queue);
       right_child = Find_Min_node(Fisrt_Queue, Second_Queue);

       top = CreateNode(\'$\' , left_child->frequency + right_child->frequency);
       top->left_child = left_child;
       top->right_child = right_child;
       En_queue(Second_Queue, top);
   }

   return De_queue(Second_Queue);
}

void Print_Huffman_codes(struct Queue_Node* RootNode, int arr[], int top)
{

   if (RootNode->left_child)
   {
       arr[top] = 0;
       Print_Huffman_codes(RootNode->left_child, arr, top + 1);
   }
if (RootNode->right_child)
   {
       arr[top] = 1;
       Print_Huffman_codes(RootNode->right_child, arr, top + 1);
   }

   if (is_leafNode(RootNode))
   {
       printf(\"%c: \", RootNode->info);
       Print_ARRAY(arr, top);
   }
}

void Huffman_codes(char info[], int frequency[], int size)
{

struct Queue_Node* RootNode = Build_Huffman_tree(info, frequency, size);

int arr[maximum_Tree_Height], top = 0;
Print_Huffman_codes(RootNode, arr, top);
}

int main()
{
   char arr[] = {\'a\', \'b\', \'c\', \'d\'};
   int frequency[] = {1000, 3000, 2000,5000};
   int size = sizeof(arr)/sizeof(arr[0]);
   Huffman_codes(arr, frequency, size);
   return 0;
}

OUTPUT:-------------------------->>>>>>>>>>>>>>>>>>>>>>

d: 0
c: 10
a: 110
b: 111