Hello everyone!

I have a Huffman algorithm that is going along really smoothly and I've gotten to the part where I have store the paths to nodes in an array from a tree.

This is what I have so far:

``````/***************************************************************
*                   huffTraverse							     *
****************************************************************
* huffTraverse() reads in a tree, a level, an empty String Array, *
*  and a empty String variable and then stores the path to
specific nodes into an array									*
****************************************************************/
void huffTraverse(Node* t, int level, String* huffStore, String prefix)
{
string leftprefix = prefix + "0";
string rightprefix = prefix + "1";
if((t->left == NULL) && (r->right == NULL))
{
huffStore[level] = "0";
//strdup function
}
else
{
huffStore[level] = "0";
huffTraverse(t->left, level+1, huffStore, ???)
huffStore[level] = "1";
huffTraverse(t->right, level+1, huffStore, ???)

}
}``````

I know the function has to be recursive, but my professor has thrown us a curveball because he wants us to store the paths as strings into the array.

The leftprefix and rightprefix are variables he told me to create to add "0" and "1" to prefix when I have to go either left or right depending on what node I'm on.

Prefix is initialized to an emptystring in main and huffStore is initialized to 256 spots.

I also have to use the strdup function at the initial node I believe.

2
Contributors
1
2
Views
9 Years
Discussion Span
Last Post by monkey_king

HI,
a huffman tree is essentially a funky binary tree.
So you can use all the tricks from the binary tree.
Check wiki
http://en.wikipedia.org/wiki/Tree_traversal

I think you should be looking into the preorder traversel

good luck

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.