Huffman code

[karolina]

Does anyone know how to implement a binary tree with Huffman codes?

[kuphryn]

Tell me about Huffman's algorithm.

Kuphryn

[ReorX]

Huffman's alogorithm looks like this:

A) Start with as many trees as there are symbols.
B) While there is more than one tree:

1. Find the two trees with the smallest total weight.
2. Combine the trees into one, setting one as the left child and the other as the right.

C) Now the tree contains all the symbols. A '0' represents following the left child; a '1' represents following the right child.

All you need is a function, which calculates the weight of your symbols - e.g., if you are using a text, this would be the frequency with which single letters appear!