0

Given a constructed a tree and all the variables needed for it to work, I simply need to understand HOW one goes about getting an encoded tree from a Huffman Tree.

More specifically, I need to return the String Encoding of a Huffman Tree. No parameters are passed to the function. It is simply a getHuffmanTreeEncoded() function that returns the encoded string of the Tree and I am not sure how I would go to that.

I don't provide code for this question because the rest of it is already done and it is very long / for school... I think I would better understand with words.

Do I need to traverse the tree? Do I need to recursively loop? I need to pass a string variable with the Huffman Tree string encoded. How would I go about that, assuming functions and structure for everything already exists (the tree, getting encoded tests, priority queue implementation ,etc.). What general steps does one take to get the string of a Huffman tree?

-Thanks

cherlie margnus
  • 13
  • 3
  • Did you double check for any specification on how the encoding is supposed to look? There are hundrets of different ways to encode a tree, if its for an assignment I'd expect at least some restictions on how it should be encoded. – MDK Oct 29 '20 at 20:34
  • Yeah there is a specification but really I am not too worried about that, I am more worried about how do you actually travel through the tree and find a value? Similar to an array where I can iteratively or recursively go through each value [i] and assign it to a variable or compare it or whatever I want. How do I traverse / read the values from a tree? – cherlie margnus Oct 29 '20 at 21:16
  • Ah, now I understand the problem. Does this answer help: https://stackoverflow.com/questions/15306452/traversing-through-all-nodes-of-a-binary-tree-in-java ? – MDK Oct 29 '20 at 21:32

1 Answers1

0

What I think you're asking is: If I have symbol, how do I use the Huffman tree to generate the code for that symbol.

You don't. That's a terrible thing to have to do for every single symbol in your message. What you would do instead is traverse the entire tree recursively once, and at each leaf, add the symbol and its code to a table. Discard the tree and use the table to do your encoding.

You don't even need to do that, because you can ignore the actual code built in to the assignments of 0's and 1's to left and right branches. However that assignment is entirely arbitrary, where any other assignment will give you the same compression. The only information you need from the Huffman tree is the code length, in bits, for each symbol. Traverse the tree recursively and generate a table of the symbols and their code lengths.

Then you can use a canonical Huffman code for encoding.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158