Постройте дерево Хаффмана для данных фраз: 1) МАМА МЫЛА РАМУ 2) ШЛА САША ПО ШОССЕ 3) ТКЁТ ТКАЧ ТКАНИ 4) КАРЛ У КЛАРЫ

Для построения дерева Хаффмана для данных фраз необходимо выполнить следующие шаги:
1) Определить частоту появления каждого символа в каждой фразе.
2) Создать узлы для каждого символа, установить их частоту появления и поместить их в приоритетную очередь (Priority Queue).
3) Выполнить следующие шаги, пока в очереди не останется только один узел:
a) Извлечь два узла с наименьшей частотой появления из очереди.
b) Создать новый узел, поместить в него эти два узла как дочерние, и установить его частоту как сумму частот дочерних узлов.
c) Поместить новый узел обратно в очередь.
4) После завершения цикла, последний оставшийся узел в очереди будет корневым узлом дерева Хаффмана.
5) Продолжить рекурсивно обходить дерево, начиная с корневого узла, помечая каждое ребро либо нулем, либо единицей.
6) Назначить каждому символу код Хаффмана, пройдя путь от корневого узла до листового узла, где каждая ветвь представляет бит 0 или 1.
7) Закодировать каждую фразу, заменив каждый символ его соответствующим кодом Хаффмана.

Давайте рассмотрим каждую фразу по очереди.

1) МАМА МЫЛА РАМУ:
Частота появления каждого символа в этой фразе:
М — 2
А — 4
Ы — 1
Л — 1
Р — 1
У — 1
Создадим узлы и поместим их в приоритетную очередь:

Узел 1: Частота — 2, Символ — М
Узел 2: Частота — 4, Символ — А
Узел 3: Частота — 1, Символ — Ы
Узел 4: Частота — 1, Символ — Л
Узел 5: Частота — 1, Символ — Р
Узел 6: Частота — 1, Символ — У

Выполним следующие шаги:

a) Извлекаем два узла с наименьшей частотой появления:
Узел 3: Частота — 1, Символ — Ы
Узел 4: Частота — 1, Символ — Л

b) Создаем новый узел и помещаем в него эти два узла как дочерние:
Узел 7: Частота — 2, Дочерние узлы: Ы, Л

c) Помещаем узел 7 обратно в очередь:

Узел 1: Частота — 2, Символ — М
Узел 2: Частота — 4, Символ — А
Узел 7: Частота — 2, Дочерние узлы: Ы, Л
Узел 5: Частота — 1, Символ — Р
Узел 6: Частота — 1, Символ — У

Повторяем шаги еще несколько раз:

a) Извлекаем два узла с наименьшей частотой появления:
Узел 5: Частота — 1, Символ — Р
Узел 6: Частота — 1, Символ — У

b) Создаем новый узел и помещаем в него эти два узла как дочерние:
Узел 8: Частота — 2, Дочерние узлы: Р, У

c) Помещаем узел 8 обратно в очередь:

Узел 1: Частота — 2, Символ — М
Узел 2: Частота — 4, Символ — А
Узел 7: Частота — 2, Дочерние узлы: Ы, Л
Узел 8: Частота — 2, Дочерние узлы: Р, У

a) Извлекаем два узла с наименьшей частотой появления:
Узел 1: Частота — 2, Символ — М
Узел 7: Частота — 2, Дочерние узлы: Ы, Л

b) Создаем новый узел и помещаем в него эти два узла как дочерние:
Узел 9: Частота — 4, Дочерние узлы: М, Узел 7 (Дочерние узлы: Ы, Л)

c) Помещаем узел 9 обратно в очередь:

Узел 9: Частота — 4, Дочерние узлы: М, Узел 7 (Дочерние узлы: Ы, Л)
Узел 2: Частота — 4, Символ — А
Узел 8: Частота — 2, Дочерние узлы: Р, У

a) Извлекаем два узла с наименьшей частотой появления:
Узел 9: Частота — 4, Дочерние узлы: М, Узел 7 (Дочерние узлы: Ы, Л)
Узел 8: Частота — 2, Дочерние узлы: Р, У

b) Создаем новый узел и помещаем в него эти два узла как дочерние:
Узел 10: Частота — 6, Дочерние узлы: Узел 9 (Дочерние узлы: М, Узел 7 (Дочерние узлы: Ы, Л)), Узел 8 (Дочерние узлы: Р, У)

c) Помещаем узел 10 обратно в очередь:

Узел 10: Частота — 6, Дочерние узлы: Узел 9 (Дочерние узлы: М, Узел 7 (Дочерние узлы: Ы, Л)), Узел 8 (Дочерние узлы: Р, У)
Продолжаем рекурсивно обходить дерево, назначая каждому символу код Хаффмана. Прохождение дерева дает нам следующие коды Хаффмана:

М — 0
А — 10
Ы — 110
Л — 1110
Р — 1111
У — 110

Назначим каждому символу его код Хаффмана:
М — 0
А — 10
Ы — 110
Л — 1110
Р — 1111
У — 110

Закодируем фразу МАМА МЫЛА РАМУ:
0 10 0 10 110 0 1110 1111 110 0 1111 10 110 1110

2) ШЛА САША ПО ШОССЕ:
Частота появления каждого символа в этой фразе:
Ш — 2
Л — 1
А — 4
С — 1
П — 1
О — 2
Е — 1
Выполним аналогичные шаги как и в предыдущем примере.

3) ТКЁТ ТКАЧ ТКАНИ:
Частота появления каждого символа в этой фразе:
Т — 4
К — 2
Ё — 1
Ч — 1
А — 1
Н — 1
И — 1
Выполним аналогичные шаги как и в предыдущих примерах.

4) КАРЛ У КЛАРЫ УКРАЛ КОРАЛЛЫ:
Частота появления каждого символа в этой фразе:
К — 3
А — 4
Р — 3
Л — 3
У — 2
Ы — 1
М — 1
О — 1

Выполним аналогичные шаги как и в предыдущих примерах.

После построения деревьев Хаффмана для каждой фразы можно закодировать каждую фразу, заменив каждый символ его соответствующим кодом Хаффмана.