How to reconstruct a Huffman tree by reading in bits?


#1

Hello,
So I am trying to reconstruct a Huffman tree by reading in bits from a compressed file, based on the following description:

  • TreeLeafEndMEssage is represented by the two bits 00

  • TreeLeaf is represented by the two bits 01, followed by 8 bits for the symbol at that leaf which will be in the range 0-255.

  • TreeBranch is represented by the single bit 1, followed by a description of the left subtree and then the right subtree.

If I have the following bit sequence as a header on the compressed file then the first 1 represents the left branch of the node, the second 1 represents the right branch of the node, then the 01 represents the TreeLeaf, and the value at the leaf would be the 01000001, which is 'A', and so on: 110101000001000101000010

So how would I reconstruct the huffman tree for decoding, using this string of bits? I know it needs to be done recursively but I don't know how to start.
Thank you.


#2

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.