   Please help with assigning bits in Huffman algorithm problem
  Hi, everyone!EDIT: I originally had a problem implementing the code to assign the bits, but I have solved it! As with #2 below, feel free to point out anything that might make the code look neater or more manageable. Thanks!As you may or may not know, I submitted a "mini-portfolio" to a game development school, and now I have been asked to complete a Huffman compression and decompression program. Before you read my code, please understand:1. I already have quite a bit of the code already written, so I'm not looking for a freebie or the work to be done for me. If posting source is necessary to get the point across, that cool, but a nudge in the right direction would work fine too.2. I understand that the code is messy. I was assigned this yesterday with a deadline of Saturday by Midnight Central Time, so I haven't had a whole lot of time to worry about style issues. Although I am not asking for style pointers, please feel free to point out anything that might make the code look neater or more manageable.3. I have Googled, F.A.Q.'ed, Manual'ed, and even diagram'ed to no avail, but will continue to scour these resources for tips/hints after posting this.Thanks!main.cpp:#include <iostream>#include "table.h"using std::cout;int main(){try{frequency_table test("shakespeare.txt");test.Display();system("PAUSE");system("CLS");test.Sort();test.Display();system("PAUSE");system("CLS");test.ConstructTree();test.DisplayTree();system("PAUSE");system("CLS");test.ConvertToBits();test.BitDisplay();system("PAUSE");return 0;}catch( char * str ) {cout << str << '\n';system("PAUSE");return 1;}}node.h:#include <string>class node{public:// Constructors:node(char entry, int num):symbol(entry), occurrences(num), left(0), right(0), isleft(false), isright(false){};node(char entry):symbol(entry), occurrences(1), left(0), right(0), isleft(false), isright(false){};char GetSymbol(){return symbol;};int GetOccurrences(){return occurrences;};//void operator++ (); // Overloading operator brings up strange result, but will worry about latervoid Increment(); // Using at the moment instead of operatorbool operator< (node& rhs); // Used for sort algorithmvoid SetParent(node* leaf){parent = leaf;};void SetLeft(node* leaf){left = leaf;};void SetRight(node* leaf){right = leaf;};node* GetParent(){return parent;};node* GetLeft(){return left;};node* GetRight(){return right;};void Display(); // Displays character and number of occurrencesvoid DisplayBits(); // Displays character and bit combinationvoid AddBits(std::string temp); // Places bit into vectorstd::string GetBits(){return mybits;};void SetIsLeft(bool temp){isleft = temp;};void SetIsRight(bool temp){isright = temp;};bool GetIsLeft(){return isleft;};bool GetIsRight(){return isright;};private:std::string mybits;char symbol;int occurrences;node* parent;node* left;node* right;bool isleft;bool isright;};// Used to compare values instead of addresses in < operator and sort algorithmstruct NodePtrLess{    bool operator () (node* a, node* b)    {   return *a < *b;    }};node.cpp:#include <iostream>#include "node.h"using std::cout;using std::string;//void node::operator++() // Overloading operator brings up strange result, but will worry about later//{//occurrences++;//}void node::Increment() // Using at the moment instead of operator{occurrences++;}bool node::operator< (node& rhs) // Used for sort algorithm{return (GetOccurrences() < rhs.GetOccurrences());}void node::Display() // Displays character and number of occurrences{cout << GetSymbol() << "\t \t" << GetOccurrences() << '\n';}void node::DisplayBits() // Displays character and bit combination{cout << GetSymbol() << "\t \t";for(unsigned int i = 0; i < mybits.size(); ++i){cout << mybits;}cout << '\n';}void node::AddBits(string temp) // Places bit into vector{mybits.append(temp);}table.h:#include <vector>#include "node.h"class frequency_table{public:frequency_table(std::string filename); // Loads file and counts characters~frequency_table();void Display(); // Displays each character and number of occurrences in the filevoid Sort(); // Sorts each symbol in ascending ordervoid ConstructTree();void DisplayTree(); // Displays tree in post-ordervoid DisplayTree(node* temp);void DeleteTree(){DeleteTree(root);}; // Deletes tree in post-ordervoid DeleteTree(node* temp);void ConvertToBits(node* temp); // Traverses tree, assigning bit combinations to each charactervoid ConvertToBits(){ConvertToBits(root);};void BitDisplay(); // Displays each character and corresponding bit valuevoid BitDisplay(node* temp);private:std::vector<node*> table;node* root;};table.cpp:#include <iostream>#include <fstream>#include <vector>#include <algorithm>#include "table.h"using std::ios;using std::ifstream;using std::cout;using std::string;using std::vector;frequency_table::frequency_table(string filename) // Loads file into memory and counts characters{char c;ifstream infile(filename.c_str(), ios::binary);if(infile.fail()){throw "Unable to open file for reading.";}while(!infile.eof()){c = infile.get();while(c == '\n'){c = infile.get();}bool check = false; // To check if character already exists in vectorfor(unsigned int i = 0; i < table.size(); ++i){if(c == table->GetSymbol()){table->Increment(); // Adds one to number of occurrencescheck = true;}}if(!check){table.push_back(new node (c)); // Adds character to vector if not already in vector}}infile.close();}frequency_table::~frequency_table(){DeleteTree();}void frequency_table::Display() // Shows each character and number of occurrences{cout << "Character:\tOccurrences:\n";for(unsigned int i = 0; i < table.size(); ++i){table->Display();}}void frequency_table::Sort() // Sorts vector in ascending order{std::sort(table.begin(), table.end(), NodePtrLess());}void frequency_table::ConstructTree(){node* parent;while(table.size() > 2){parent = new node(-1, table[0]->GetOccurrences() + table[1]->GetOccurrences());parent->SetLeft(table[0]);table[0]->SetIsLeft(true);table[0]->SetParent(parent);parent->SetRight(table[1]);table[1]->SetIsRight(true);table[1]->SetParent(parent);table.erase(table.begin());table.erase(table.begin());table.push_back(parent);Sort();}root = new node(-1, table[0]->GetOccurrences() + table[1]->GetOccurrences());root->SetLeft(table[0]);table[0]->SetIsLeft(true);table[0]->SetParent(root);root->SetRight(table[1]);table[1]->SetIsRight(true);table[1]->SetParent(root);table.clear();}void frequency_table::DisplayTree() // Displays nodes in tree in post-order{cout << "Character:\tOccurrences:\n";DisplayTree(root);}void frequency_table::DisplayTree(node* temp) // Used in conjunction with previous function{if(temp != 0){DisplayTree(temp->GetLeft());DisplayTree(temp->GetRight());if(temp->GetSymbol() != -1){temp->Display();}}}void frequency_table::DeleteTree(node* temp) // Deletes nodes in tree in post-order{if(temp != 0){DeleteTree(temp->GetLeft());DeleteTree(temp->GetRight());delete temp;}}void frequency_table::ConvertToBits(node* temp) // Traverses the tree and assigns a bit value to each leaf node{if(temp != 0){node* parent = temp->GetParent();if(temp->GetIsLeft()){temp->AddBits(parent->GetBits());temp->AddBits("0");}if(temp->GetIsRight()){temp->AddBits(parent->GetBits());temp->AddBits("1");}ConvertToBits(temp->GetLeft());ConvertToBits(temp->GetRight());}}void frequency_table::BitDisplay(node* temp) // Displays list of characters and assigned bit values{if(temp != 0){BitDisplay(temp->GetLeft());BitDisplay(temp->GetRight());if(temp->GetSymbol() != -1){temp->DisplayBits();}}}void frequency_table::BitDisplay() // Used in conjunction with previous function{cout << "Character:\tBits:\n";BitDisplay(root);}[Edited by - Highwind7 on June 7, 2008 12:08:08 PM]
Quote:I am having problems with the code to traverse the tree and assign bit values.And what *is* the problem?- The code crashes?- It doesn't compile?- You don't know how to manipulate bits?- ???   ;  EDITED: Just solved the problem. Please feel free to critique the code. Thanks!The problem isn't with the program crashing or anything like that. I am just trying to figure out how to implement the tree traversal while collecting the bits.[Edited by - Highwind7 on June 7, 2008 12:17:42 PM]