Recursive Huffman Tree Encoder

[xtinab]

Hello all,

I'm having trouble writing a recursive algorithm to traverse a Huffman tree to encode a message. I'm sure you all know what they are.

Here's my algorithm:

string HuffmanCode(const char& symbol, const TreeNode<SymbolPriority>* huffman, string &code)
{
    //Base case: you are in a leaf; if the leaf contains the character 
    //you are looking for then return the code (third argument) 
    //else return an empty string (which means ‘wrong leaf’).
    if(huffman->IsLeaf())
    {
        if(huffman->Value.Symbol == symbol)
            return code;
        else
            return "";
    }

    /*always start by going to the left and adding ‘0’ to the code 
    (code + ‘0’); check the return value against the empty string: 
    if the return value is not empty then return it without going 
    to the right else return the result of going to the right 
    (do not forget to add ‘1’ to the code).*/

    else
    {
        HuffmanCode(symbol, huffman->Left, code+'0');
        HuffmanCode(symbol, huffman->Right, code+'1');
    }
}

The problem is that when I traverse the tree and it exits when it sees that the symbol in the leaf doesn't match the symbol being looked for, it exits and goes into the right tree. Even if it finds it, it'll return and go back into the left sub tree.

Any help will be appreciated!

[histrungalot]

This works in my head, can't check it unless I code it up or some simple binary tree. At the end the value return by HuffmanCode will have the encoded value not code (third arg).

int main() {
   // etc...

   someChar  = 'n';
   wrkingTmp = "";  // <--- Will not hold the result
   encoding = HuffmanCode(someChar, root, wrkingTmp);
   cout << "Encoding for " << someChar << " is " << encoding << endl;

   // etc...
}

string HuffmanCode(const char& symbol, const TreeNode<SymbolPriority>* huffman, string &code)
{
    // Init the return value
    string ret("");
    if(huffman->IsLeaf()){
        if(huffman->Value.Symbol == symbol){
            // Set the return to the encoded value
            ret = code;
        }
    }
    else
    {
      // Go to the left, if empty string is returned, go to the right
      if ( (ret = HuffmanCode(symbol, huffman->Left, code+'0')) == "" ){
         // Go to the right
         ret = HuffmanCode(symbol, huffman->Right, code+'1'); 
      }
    }
    // Always return something
    return ret;
}