Searching for the path on a Huffman Tree

Question

I'm working on a Huffman tree and I'm trying to figure out how to traverse the tree to find the node that has the character that I'm looking for. While searching the tree i need to keep a string of the path that is taken to the node that I'm looking for using 1's and 0's (0 left 1 right). How can i do this?

Answer 1

Long time since i wrote a huffman engine, but i'll give it a shot.

Pseudo Code.

Assuming your Huffman Tree Node looks like this

class HuffNode
{
...
char ch;
long huffCode; //initialized to zero initially
HuffNode left,right;
}

So here's recursive function (converting it to iterative should be easy)

void buildCodes(HuffNode currentNode, long currentCode)
{
currentNode->huffCode =  currentCode;
if(currentNode->left != null) buildCodes(currentNode->left, currentCode << 1);
if(currentNode->right != null) buildCodes(currentNode->right, (currentCode << 1) | 1);
}

call it this way

buildCodes(rootHuffNode,0);