Заданы буквы и их частоты а) построить дерево Хаффмана

Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.
Дерево Хаффмана – это бинарное дерево, у которого листья помечены символами, для которых разрабатывается кодировка; узлы (в том числе корень) помечены суммой вероятностей появления всех символов, соответствующих листьям поддерева, корнем которого является соответствующий узел.
Метод Хаффмана на входе получает таблицу частот встречаемости символов в исходном тексте. Далее на основании этой таблицы строится дерево кодирования Хаффмана.
а) строим дерево по алгоритму Хаффмана
Располагаем частоты в возрастающем порядке.
ш
ф
о т к а
2 3 4 7 8 12
Формируем бинарное дерево, где «ш» - левый лист, «ф» - правый; частота родителя 2+3=5; приписываем левому листу 0, правому 1; обозначаем дерево G1.
В списке частот заменяем значения двух наименьших частот их суммой и снова располагаем по возрастанию в новой таблице.
о G1
т к а
4 5 7 8 12
Формируем бинарное дерево, где «о» - левый лист, «G1» - правый; частота родителя 4+5=9; приписываем левому листу 0, правому 1; обозначаем дерево G2.
В списке частот заменяем значения двух наименьших частот их суммой и снова располагаем по возрастанию в новой таблице.
т к G2
а
7 8 9 12
Формируем бинарное дерево, где «т» - левый лист, «к» - правый; частота родителя 7+8=15; приписываем левому листу 0, правому 1; обозначаем дерево G3.
В списке частот заменяем значения двух наименьших частот их суммой и снова располагаем по возрастанию в новой таблице.
G2
а G3
9 12 15
Формируем бинарное дерево, где «G2» - левый лист, «а» - правый; частота родителя 9+12=21; приписываем левому листу 0, правому 1; обозначаем дерево G4.
В списке частот заменяем значения двух наименьших частот их суммой и снова располагаем по возрастанию в новой таблице.
G3
G4
15 21
Формируем бинарное дерево, где «G3» - левый лист, «G4» - правый; частота родителя 15+21=36; приписываем левому листу 0, правому 1.
Последнее дерево и будет являться деревом Хаффмана
б) к каждому листу (букве) дерева Хаффмана ведет единственный путь, состоящий из 0 и 1; строки из 0 и 1 каждой буквы - это ее путевой или элементарный код; путевые коды, соответствующие всем буквам дерева Хаффмана, образуют префиксное, оптимальное множество кодов