Huffman encoding

[sigur47]

I am working on huffman encoding and i am a little confused on how to transverse a tree to encode string of bits for a particular character.I already have my tree built.

[brewbuck]

To encode, start at the leaf which corresponds to the symbol you are going to encode. Then walk the tree upward to the root, keeping track of whether each child is a left child (zero bit) or a right child (one bit) of its parent. This will produce a bit string, which you must reverse the order of to give the Huffman code.

The problem is how to locate the correct leaf, given a symbol. You can store that in some kind of map, but it's actually easier to walk the tree top-down, building an encoding table as you go, then use the table during the actual encoding. In pseudocode it might look like this:

BuildHuffmanEncodingTable(root, code = ''):
    if root.HasChildren:
        BuildHuffmanEncodingTable(root.Left, code + '0')
        BuildHuffmanEncodingTable(root.Right, code + '1')
    else:
        # Reached a leaf, which means 'code' contains the actual code for this symbol
        InsertHuffmanCodeIntoTable(root.Symbol, code)

[sigur47]

To encode, start at the leaf which corresponds to the symbol you are going to encode. Then walk the tree upward to the root, keeping track of whether each child is a left child (zero bit) or a right child (one bit) of its parent. This will produce a bit string, which you must reverse the order of to give the Huffman code.

The problem is how to locate the correct leaf, given a symbol. You can store that in some kind of map, but it's actually easier to walk the tree top-down, building an encoding table as you go, then use the table during the actual encoding. In pseudocode it might look like this:

BuildHuffmanEncodingTable(root, code = ''):
    if root.HasChildren:
        BuildHuffmanEncodingTable(root.Left, code + '0')
        BuildHuffmanEncodingTable(root.Right, code + '1')
    else:
        # Reached a leaf, which means 'code' contains the actual code for this symbol
        InsertHuffmanCodeIntoTable(root.Symbol, code)

Hi i am a little bit confused.Do you mind explaining further

[oogabooga]

What exactly confuses you?
Put in some effort, man!
You could post your code, too.