Help w/ Traversing a Huffman Tree

[neodregan]

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.

Any help please? Thanks

[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