Операция объединения двух символов в один использует струк-
туру бинарного дерева. Каждый узел содержит символ и частоту
вхождения. Код любого символа может быть определен просмотром де-
рева снизу вверх, начиная с листа. Каждый раз при прохождении уз-
ла приписываем слева к коду 0, если поднимаемся по левой ветви и
1, если поднимаемся по правой ветви. Как только дерево построено
код любого символа алфавита может быть определен просмотром дере-
ва снизу вверх, начиная с места, представляющего этот символ. На-
чальное значение кода пустая строка. Каждый раз, когда мы подни-
маемся по левой ветви, к коду слева приписывается ноль, если
справа - 1. Часть info узла дерева содержит частоту появления
символа представляемого этим узлом. Дерево Хаффмена строго бинар-
ное. Если в алфавите п символов, то дерево Хаффмена может быть
представлено массивом узлов размером 2п-1. Поскольку размер памя-
ти, требуемой под дерево известен, она может быть выделена зара-
нее.