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.

slim · Accepted Answer · 2014-02-19 17:41:25Z

2

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;
    }

edited Feb 19, 2014 at 17:41

answered Feb 19, 2014 at 16:57

slim

41.5k14 gold badges101 silver badges131 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user3265963 Over a year ago

I thought root->left or root->right was always a leaf? I based it on that. So my plan was to check if it was leaf and see if the letter matched. If not it "goes down the path" of not leaf and tries again. Maybe add encode(tempNode,letter) if != letter?

slim Over a year ago

Examples e.g. on Wikipedia show nodes with two non-leaf children: en.wikipedia.org/wiki/File:Huffman_tree_2.svg -- but you may have created a tree with the special properties you describe; in which case follow the debugging steps I described.

user3265963 Over a year ago

I thought I was traversing down the tree with tempNode = root->right; . Then the new tempnode would be one node lower than previous.

slim Over a year ago

See addition. root->left never changes.

rcgldr Over a year ago

"a common way ... array of leaf nodes" - If an array is going to be used, then it's much quicker to simply have an array or vector of code length and code value, indexed by letter. I think the goal here is to use a Huffman tree, not to implement an efficient encoder.

Collectives™ on Stack Overflow

Encoding a Huffman Binary tree

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related