Huffman encoding

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.

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:

Code:

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)

Originally Posted by 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:

Code:

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

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