Do not use Structs in your code. Do not use a min or max heap class. You should only have Huffman Tree and Huffman Tree Node classes, and you are expected to use the relevant template classes in the...

2 answer below »
Do not use Structs in your code. Do not use a min or max heap class. You should only have Huffman Tree and Huffman Tree Node classes, and you are expected to use the relevant template classes in the STL. For example, the STL Pair, Map and Priority Queue containers. You are required to carry out the tasks below to develop an optimal Huffman Tree with which to compress a file of ASCII text. You should aim to complete the first section of this problem (i.e., the steps 1 through 5 below). Once you have completed tasks 1-5, then complete 6 & 7, and finally 8. Section A (40 Marks) The first 5 tasks will encode and decode the file into a string of 0's and 1's using a Huffman tree. 1. Given a text file, determine the frequency of each character in the text (map of character and frequency). 2. Build an optimal Huffman tree to represent these characters with these frequencies (maintain a priority queue of trees, removing and joining trees until only one tree remains – the final Huffman tree required) Hint: each Hoffman Tree should have a weight data member, as well as a pointer to its root node. 3. Use the tree to map each character to the string of 0's and 1's needed to encode it (preorder traversal of tree, store results in a map of character and string). 4. Use the map to encode the text to a string of 0's and 1's and write to an encoded file 5. Use the Huffman Tree to decode the text and write to another file. Section B (20 Marks) Tasks 6 and 7 compress and un-compress the file: 6. To compress: break up the string of 0's and 1's into 8-bit chunks, and write the character represented by each chunk to the compressed file. 7. Un-compress by replacing each character with the 8 bits needed to represent it. Section C (30 marks) Task 8: 8. Embed the Huffman Tree used for the encryption as the first bytes of the compressed file and retrieve it as part of the decompression process. 10 marks for good programming practice. Marks may be deducted for bad programming practice [-80 Marks] For example, mixing implementation and declaration, including .cpp, files, global variables, etc, etc
Answered 5 days AfterApr 18, 2021

Answer To: Do not use Structs in your code. Do not use a min or max heap class. You should only have Huffman...

Pulkit answered on Apr 24 2021
123 Votes
code_for_huffman_tree/Compressed.txt
10001111011110000111100011101111100100101111101100111010101010100100101011101011000
code_for_huffman_tree/huf
fman_tree_code.cpp
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define EMPTY_STRING ""
class HuffmanTreeNode{ // define HuffmanTreeNode class
public:
char data; // datapoint
int fre; // frequency of occurence
HuffmanTreeNode *left, *right; // pointers of tree
};
HuffmanTreeNode* createNode(char data, int fre, HuffmanTreeNode* left, HuffmanTreeNode* right){ // create new node function
HuffmanTreeNode* node = new HuffmanTreeNode(); // memory allocation
node->data = data;
node->fre = fre;
node->left = left;
node->right = right;
return node;
}
void createfile(string filename,string content){ // for creating file
ofstream out_data;
out_data.open(filename);
if( !out_data ) {
cout << " file could not be opened" << endl;
exit(1);
}
out_data << content << endl;
out_data.close();
}
class comp{ // declaring comparision class
public:
bool operator()(const HuffmanTreeNode* l, const HuffmanTreeNode* r) const{
return l->fre > r->fre; // comparision
}
};
bool isLeafNode(HuffmanTreeNode* root) { ...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here