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!

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){
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;
}
``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.