Question
The code is having some errors. Unable to track the record of Left and Right Child. Need to create a Huffman tree from the min
The code is having some errors. Unable to track the record of Left and Right Child. Need to create a Huffman tree from the min heap values. So that eaxh charachter can be used to obtain the encoded values of each letter. Data.txt is the file which consists of
data.txt
hello
welcome to my galaxy
#include
struct Item { char charachter; int frequency; Item* Left_Ch; Item* Right_Ch;
Item(char charachter, int frequency) { this->charachter = charachter; this->frequency = frequency; Left_Ch = nullptr; Right_Ch = nullptr; }
Item() { Left_Ch = nullptr; Right_Ch = nullptr; } };
class MinHeap { public: Item* arr; int total; int capacity;
void doubleCapacity() { Item* newArr = new Item[this->capacity * 2]; this->capacity *= 2;
for (int i = 0; i < this->total; i++) { newArr[i] = this->arr[i]; }
delete[]this->arr; this->arr = newArr; }
public: MinHeap() { this->arr = new Item[1]; this->total = 0; this->capacity = 1; }
MinHeap(int _capacity) { if (capacity > 0) { this->arr = new Item[_capacity]; this->total = 0; this->capacity = _capacity; } }
void insert(char charachter, int frequency) { if (this->total == this->capacity) this->doubleCapacity();
arr[this->total].charachter = charachter; arr[this->total].frequency = frequency;
shiftUp(this->total); this->total++; }
void shiftUp(int index) { int parent = (index - 1) / 2;
if (this->arr[index].charachter < this->arr[parent].charachter) { swap(this->arr[index], this->arr[parent]); }
else { return; }
if (parent > 0) { shiftUp(parent); } }
void deleteMin() { if (this->total == 0) { return; } swap(this->arr[total - 1], this->arr[0]); this->total--; shiftDown(0); }
void shiftDown(int index) { int Left_Ch = index * 2 + 1; int Right_Ch = index * 2 + 2; int min = index;
if (Left_Ch < this->total && this->arr[Left_Ch].charachter < this->arr[min].charachter) { min = Left_Ch; }
if (Right_Ch < this->total && this->arr[Right_Ch].charachter < this->arr[min].charachter) { min = Right_Ch; }
if (min == index) { return; }
swap(this->arr[min], this->arr[index]); shiftDown(min); }
void getMin(char& charachtery, int& val) { if (total > 0) { val = arr[0].frequency; charachtery = arr[0].charachter; } deleteMin(); }
~MinHeap() { delete[]this->arr; } };
class HuffMan { public: void build_Huffman(string fileName) {
string temp; unordered_map map;
ifstream infile; infile.open(fileName);
while (getline(infile, temp)) {
for (int i = 0; temp[i]; i++) {
if (map.find(temp[i]) == map.end()) { map.insert(make_pair(temp[i], 1)); }
else { map[temp[i]]++; } } }
MinHeap temp_heap; unordered_map::iterator i; for (i = map.begin(); i != map.end(); i++) { temp_heap.insert(i->first, i->second); }
//////////////////////////////////////////////////// // Create Huffman Tree // //////////////////////////////////////////////////// print_encoding(this->root,""); }
void print_encoding(Item* root, string code) { if (root == nullptr) { return; }
if (root->charachter != '@') { cout << root->charachter << " , " << root->frequency << " , " << code << endl; }
print_encoding(root->Left_Ch, code + "0"); print_encoding(root->Right_Ch, code + "1"); }
};
int main() {
HuffMan h; string file_name="data.txt"; h.build_Huffman(file_name);
system("pause"); return 0; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started