I have to make a following genHuffmanTree function and my header file is given b
ID: 3692903 • Letter: I
Question
I have to make a following genHuffmanTree function and my header file is given below this function. Can someone help me in how to write the function?
HuffmanNode *genHuffmanTree(HuffmanNode **nodes, int length)
{
// TODO
}
_____________________________________________Header_______________________________________________
#ifndef HUFFMAN_H_
#define HUFFMAN_H_
// ---------------------------------------------------------------------------------------------
// Huffman code related
// ---------------------------------------------------------------------------------------------
// The Huffman node struct
struct HuffmanNode {
char character;
int frequency;
bool isLeaf;
HuffmanNode *left;
HuffmanNode *right;
// Constructor for leaf nodes
HuffmanNode(char, int);
// Constructor for internal nodes
HuffmanNode(int, HuffmanNode *, HuffmanNode *);
// Overloaded comparison operators
inline bool operator<(HuffmanNode &rhsNode) {
return frequency < rhsNode.frequency;
}
inline bool operator>(HuffmanNode &rhsNode) {
return rhsNode < *this;
}
};
// Huffman code functions
HuffmanNode **genHuffmanNodes(char *, int *, int);
HuffmanNode *genHuffmanTree(HuffmanNode **, int);
// ---------------------------------------------------------------------------------------------
// Min heap related
// ---------------------------------------------------------------------------------------------
// The MinHeap struct
struct MinHeap {
int heapSize;
HuffmanNode **heapNodes;
// Constructor
MinHeap(HuffmanNode **, int);
// Min heap methods
void exchange(int, int);
void minHeapify(int);
void buildMinHeap();
// Min priority queue methods
HuffmanNode *extractMin();
void insert(HuffmanNode *);
};
#endif /* HUFFMAN_H_ */
Explanation / Answer
Answer:
#include <stdio.h>
#include <stdlib.h>
#define MAXIMUM_HEIGHT_TREE 100
struct HuffmanNode
{
char info;
unsigned frequency;
struct HuffmanNode *left, *right;
};
struct MinHeap
{
unsigned size;
unsigned space;
struct HuffmanNode **array;
};
struct HuffmanNode* newNode(char info, unsigned frequency)
{
struct HuffmanNode* support =
(struct HuffmanNode*) malloc(sizeof(struct HuffmanNode));
support->left = support->right = NULL;
support->info = info;
support->frequency = frequency;
return support;
}
struct MinHeap*generateMinHeap(unsigned space)
{
struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->space = space;
minHeap->array =
(struct HuffmanNode**)malloc(minHeap->space * sizeof(struct HuffmanNode*));
return minHeap;
}
void exchange(struct HuffmanNode** a, struct HuffmanNode** b)
{
struct HuffmanNode* t = *a;
*a = *b;
*b = t;
}
void minHeapify(struct MinHeap* minHeap, int indicator)
{
int smallest = indicator;
int left = 2 * indicator + 1;
int right = 2 * indicator + 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 != indicator)
{
exchange(&minHeap->array[smallest], &minHeap->array[indicator]);
minHeapify(minHeap, smallest);
}
}
int checksizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}
struct HuffmanNode* extractMin(struct MinHeap* minHeap)
{
struct HuffmanNode* support = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return support;
}
void insert(struct MinHeap* minHeap, struct HuffmanNode* HuffmanNode)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i && HuffmanNode->frequency < minHeap->array[(i - 1)/2]->frequency)
{
minHeap->array[i] = minHeap->array[(i - 1)/2];
i = (i - 1)/2;
}
minHeap->array[i] = HuffmanNode;
}
void buildMinHeap(struct MinHeap* minHeap)
{
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
int checkEnd(struct HuffmanNode* root)
{
return !(root->left) && !(root->right) ;
}
struct HuffmanNode* genHuffmanTree(char info[], int frequency[], int size)
{
struct HuffmanNode *left, *right, *top;
struct MinHeap* minHeap = generateandBuildMinHeap(info, frequency, size);
while (!checksizeOne(minHeap))
{
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->frequency + right->frequency);
top->left = left;
top->right = right;
insert(minHeap, top);
}
return extractMin(minHeap);
}
void displayCodes(struct HuffmanNode* root, int arr[], int top)
{
if (root->left)
{
arr[top] = 0;
displayCodes(root->left, arr, top + 1);
}
if (root->right)
{
arr[top] = 1;
displayCodes(root->right, arr, top + 1);
}
if (checkEnd(root))
{
printf("%c: ", root->info);
printArr(arr, top);
}
}
void genHuffmanNodes(char info[], int frequency[], int size)
{
struct HuffmanNode* root = genHuffmanTree(info, frequency, size);
int arr[MAXIMUM_HEIGHT_TREE], top = 0;
displayCodes(root, arr, top);
}