Encoding a Huffman Binary tree

Question

I am trying to write a function that takes in a huffman tree and a character. It should then encode the character and return it.

The code so far:

string encode(NodePtr root, char letter)
{
    string encode_str; //a string which will store the encoded string
    NodePtr tempNode = root; //Initialize a new Huffman to be used in this function
    NodePtr tempLeft = root->left;
    NodePtr tempRight = root->right;

        //A while loop that goes on until we find the letter we want
        while((tempLeft->letter != letter) || (tempRight->letter != letter))
        {
         if((tempRight->is_leaf()) && (tempRight->letter == letter)) //check if is leaf and is letter
         {
                encode_str = encode_str + '1';
         }
         else if ((tempLeft->is_leaf()) && (tempLeft->letter == letter)) //check if is leaf and is letter
         {
             encode_str = encode_str + '0';
         }
         else if ((tempRight->is_leaf()) && (tempRight->letter != letter)) //check if is leaf and is NOT letter
         {
             tempNode = root->left;
             tempLeft = tempNode->left;
             tempRight = tempNode->right;
             encode_str = encode_str + '0';
         }
          else if ((tempLeft->is_leaf()) && (tempLeft->letter != letter)) //check if is leaf and is NOT letter
         {
             tempNode = root->right;
             tempLeft = tempNode->left;
             tempRight = tempNode->right;
             encode_str = encode_str + '1';
         }
         }    

    return encode_str;
}

This has not worked so far and debugging hasn't helped me either. Can anyone help me out here, or at least tell me if my thinking is right.

Answer 1

If neither tempLeft nor tempRight is a leaf, you've got an infinite loop:

while((tempLeft->letter != letter) || (tempRight->letter != letter))
    {
        if((tempRight->is_leaf()) &&
           (tempRight->letter == letter)) 
        {
            // no
        }
        else if ((tempLeft->is_leaf()) &&
                 (tempLeft->letter == letter)) 
        {
            // no
        }
        else if ((tempRight->is_leaf()) && 
                 (tempRight->letter != letter)) 
        {
            // no
        }
        else if ((tempLeft->is_leaf()) && 
                 (tempLeft->letter != letter))
        {
            // no
        }
     }

There must be something you intend to do in the case where the nodes are not leaves. Maybe recurse?

(Per comments) You might be working with a variant of Huffman trees in which you can guarantee that every node is either a leaf or has one leaf child. If you can guarantee that, then the above does not matter (it would be good to throw an exception if it occurs). However, real-world Huffman trees do not have this property.

---

When one child is a leaf and the other is not your target letter, you attempt to set a new tempNode, tempLeft and tempRight for the next go around the loop.

    else if ((tempRight->is_leaf()) && 
             (tempRight->letter != letter)) 
     {
         tempNode = root->left;
         tempLeft = tempNode->left;
         tempRight = tempNode->right;
         encode_str = encode_str + '0';
     } 

However, since you never modify root, tempNode = root->left will always set tempNode to the same node.

You probably want tempNode = tempNode->left.

---

To avoid repetition of code, you can move

tempLeft = tempNode->left;
tempRight = tempNode->right;

... to be the first thing that happens in the while() loop.

---

You say that debugging hasn't helped. Have you actually run it in a debugger?

Write a unit test that sets up your tree; validates that the tree actually contains what you intend it to; and calls this function with one letter. Decide how you think execution should proceed. Now run the code in a debugger, stepping through it. When it stops doing what you think it should, you'll be able to reason about why.

---

A common way to implement Huffman Encoding is to have an array of leaf nodes, so you can reach the node through simple array access:

    NodePtr nodeA = nodes[0];

... and have a pointer to the parent in each node, and a field indicating whether it's the left or right child, so that you can easily traverse the tree backwards, from leaf to root, building up a code (in reverse):

    string code = "";
    NodePtr node = nodeA;
    while(node->parent != NULL) {
        code = node->code + code; 
        node = node->parent;
    }