Implement a Huffman Coding Tree based off a design of a flexible tree structure
ID: 3848579 • Letter: I
Question
Implement a Huffman Coding Tree based off a design of a flexible tree structure (design one).
(a) Your tree should build itself using https://users.encs.concordia.ca/~sthiel/comp352/Jabberwock.txt
(b) Include the characters for spacing as well as all punctuation, but not line breaks.
https://fis.encs.concordia.ca/eas/
(c) You should not make encoding for characters not found in the source text, and I will not use any such characters while testing your code.
(d) When Two characters with the same weight are merged into one subtree, your program should choose for the left child, the element that came first in the source material.
(e) When two subtrees with the same weight are merged into one subtree, your program should choose for the left child, the element that came first in the priority queue or ordered list you were using to build the tree.
(f) Using the command line, your program should be called as java Huffman <source>
(g) <source> will be the name of the local file to be loaded to built your Huffman Tree
(h) Upon starting, a frequency table will be built. Your program should listen to stdin (you may use Scanner) and encode any line entered (terminated by a line break) and output the encoded version using 1s and 0s (vs. padded ASCII).
(i) Your program should multiple lines to be entered, encoding each one as it is entered.
Explanation / Answer
a)
#include <stdio.h>
#include <stdlib.h>
struct MinHeapNode
{
char data;
unsigned freq;
struct MinHeapNode *left, *right;
}
struct MinHeapNode* newNode(char data, unsigned freq)
{
struct MinHeapNode* temp = (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
struct MinHeap* createMinHeap(unsigned capacity)
{
struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
while (!isSizeOne(minHeap))
{
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
void printCodes(struct MinHeapNode* root, int arr[], int top)
{
if (root->left)
{
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right)
{
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (isLeaf(root))
{
printf("%c: ", root->data);
printArr(arr, top);
}
}
void HuffmanCodes(char data[], int freq[], int size)
{
struct MinHeapNode* root = buildHuffmanTree(data, freq, size);
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.