Принцип построения дерева Хаффмана заключается в следующем: 12

1. Символы входного алфавита образуют список свободных узлов. 1 Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение. 1
2. Выбираются два свободных узла дерева с наименьшими весами. 1
3. Создаётся их родитель с весом, равным их суммарному весу. 1
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка. 1
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0. 1
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. 1 Он и будет считаться корнем дерева. 1

Идея алгоритма состоит в том, что, зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. 1 Символам с большей вероятностью ставятся в соответствие более короткие коды. 1