C++ DFS Hi, I have to implement a member function in a class HuffmanHeap : Heap<
ID: 3687103 • Letter: C
Question
C++ DFS
Hi,
I have to implement a member function in a class HuffmanHeap : Heap<TreeNode *> called void dfs(HuffmanCode& hc, TreeNode *tn, string &s){}; which is called by another member function
HuffmanCode getCode() {}; (I'll post the codes at the bottom) and I don't really know how to implement it. This function go through a tree of nodes using the Depth First Search and outputs hc <- a map<string,string> thingie .(can use recursion to do this)
Ill explain the inputs of this member function void dfs(HuffmanCode& hc, TreeNode *tn, string &s) that I need to implement:
- The class HuffmanCode has the base class of a map (class HuffmanCode : public map<string,string> ), hc stores the word related to the TreeNode and the code( which I'll explain what code is later) like hc.insert ( std::pair<string,string>(*(children[0]->word),code) ).
for(auto entry : hc) {
cout << entry.first << " " << entry.second << endl;// first is the <word>, second is the <code>
}
outpust should look like "LedZeppelin 01 Nirvana 000 Queen 001 TheBeatles 1"
- tn is the Treenode at the root of the tree, the tree looks like the following:
-s is the string to store the code. The code is made up of the pathway of the banches, for example:
the code for Nirvana would be 000 (tn->children[0]->children[0]->chlidren[0])
the code for Queen would be 001 (tn->children[0]->children[0]->chlidren[1])
LedZeppelin 01
TheBeatles 1
The classes for the codes are in different header files, but I copied and pasted the ones that are relevant so it my help you understand my question:
class HuffmanTree {
private:
// ----- TreeNode ------
// A node in the Huffman Tree
struct TreeNode {
// ---------
// links to children. these are nullptr is any of the children is non-existent
TreeNode* children[2];
// ---------
// link to the string representation of the word
string *word;
// ---------
// --------- TreeNode() --------
// default constructor : all links are nullptr
TreeNode() {
children[0] = children[1] = nullptr;
word = nullptr;
}
}
// Other members......
}
class HuffmanCode : public map<string,string> {
public:
HuffmanCode() {}
}
class HuffmanHeap : Heap<TreeNode *> {
public:
TreeNode *root; //the root of the tree
public:
//.....Some public members
// ----
// ---- dfs(HuffmanCode& hc, TreeNode *tn, string &s) ----
// performs dfs starting at node tn. The string keeps track of the branches one has
// to follow from the root to this node. It adds to hc all leaf nodes
//
void dfs(HuffmanCode& hc, TreeNode *tn, string &s);//TODO!!
// ----
// ---- getCode() ----
// returns a HuffmanCode corersponding to the current HuffmanTree
HuffmanCode getCode() {
HuffmanCode toRet;
string ss("");
dfs(toRet, root, ss);
return toRet;
}
};
}
//Just in case you want to know how the Heap class looks like
template <class T>
class Heap {
protected:
// ----
// Nodes
struct Node {
unsigned int priority;
const T *data;// Would be TreeNodes in this case
};
// ----
// Content -> pointers to nodes
vector<Node *> content;
//Other member functions......
}
int main() {
//This is for the testing
// test the dfs method
string simple = "TheBeatles TheBeatles LedZeppelin LedZeppelin Queen TheBeatles LedZeppelin TheBeatles TheBeatles LedZeppelin TheBeatles TheBeatles TheBeatles Nirvana Queen";
istringstream syrup(simple);
cout << "-------------------------------" << endl;
cout << "- Testing dfs... -" << endl;
cout << "-------------------------------" << endl;
HuffmanTree htSimple(syrup);// this creates the tree
HuffmanCode hcDFS = htSimple.getCode();//TODO .getCode()
for(auto entry : hcDFS) {
cout << entry.first << " " << entry.second << endl;// first is the <word>, second is the <code>
}
cout << "- The output should be the following, or the negative (0s replaced with ones)-" << endl;
cout << "LedZeppelin 01 Nirvana 000 Queen 001 TheBeatles 1" << endl;
}
_______________________________________________________end of the question! Thanks a lot!__________________________________________
Explanation / Answer
Hi below i have given a copmplete sample code for HuffmanHeap for your reference using C++, Hope you find the solution for your reference,
#include <bits/stdc++.h>
using namespace std;
// A Huffman tree node
struct MinHeapNode
{
char data; // One of the input characters
unsigned freq; // Frequency of the character
MinHeapNode *left, *right; // Left and right child
MinHeapNode(char data, unsigned freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};
// For comparison of two heap nodes (needed in min heap)
struct compare
{
bool operator()(MinHeapNode* l, MinHeapNode* r)
{
return (l->freq > r->freq);
}
};
// Prints huffman codes from the root of Huffman Tree.
void printCodes(struct MinHeapNode* root, string str)
{
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << " ";
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
// Create a min heap & inserts all characters of data[]
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new MinHeapNode(data[i], freq[i]));
// Iterate while size of heap doesn't become 1
while (minHeap.size() != 1)
{
// Extract the two minimum freq items from min heap
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
// Create a new internal node with frequency equal to the
// sum of the two nodes frequencies. Make the two extracted
// node as left and right children of this new node. Add
// this node to the min heap
// '$' is a special value for internal nodes, not used
top = new MinHeapNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
// Print Huffman codes using the Huffman tree built above
printCodes(minHeap.top(), "");
}
// Driver program to test above functions
int main()
{
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.