Traversing a binary tree with pointers
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:
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;
....
If you guys have any questions, please let me know. Thank you so much for your help.