Hi guys,
Alright ya'll I need your help with a project that I am developing at school for one of my classes. I need to do a Huffman encoder. Basically my program reads a text file that analyzes the frequency of each character. and places them into STL maps as nodes. It then constructs a binary tree with the assistance of a heap(with a vector as its container). At the end, I have to traverse this tree that I have constructed. At this point, I have no idea have to traverse the tree and all the resources only give me object based implementations. The poscondition of the binary tree construction is that I have the pointer to the parent node and its children nodes. I was thinking about recursive functions but I do not know where to begin. Any feedback would be much appreciated. Here's what I have so far:
If you guys have any questions, please let me know. Thank you so much for your help.Code:.... // Huffman Encoding scheme while(!v.empty()){ // 1) Read and then pop the two lowest nodes in the vector(heap) lchild = v.front(); pop_heap(v.begin(), v.end(), lt); v.pop_back(); // NOTE: if vector is not empty at this point // pop the rchild and set the parent num to both // numbers, else if vector is empty, pop the vector // and set that pointer as the rchild rchild = v.front(); pop_heap(v.begin(), v.end(), lt); v.pop_back(); cout << "lchild value: " << *lchild << endl; cout << "rchild value: " << *rchild << endl; // 2) Create a new node which is the parent of the two lowest probability nodes. parent = new Node(lchild->getNum() + rchild->getNum()); parent->set_lchild(lchild); parent->set_rchild(rchild); cout << "parent: " << *parent << endl; // 3) Assign the new node the sum of its children and push the parent node into the heap v.push_back(parent); push_heap(v.begin(),v.end(), lt); } // end while.huffman // Postcondition: We have emptied out the vector v and have the // pointer to the root of our newly constructed binary tree!! Yay!! cout << "Final Parent Value: " << *parent << endl; cout << "Node of lchild: " << *parent->get_lchild() << endl; cout << "Node of rchild: " << *parent->get_rchild() << endl; ....