Уроки 25 - 26
§16. Списки и деревья
Содержание урока
Дерево для двоичного кода
Дерево для двоичного кода
Для двоичного кода тоже можно построить дерево.
| А | Б | В | Г | Д |
| 0 | 11 | 101 | 110 | 111 |
Например, для кода дерево выглядит так (рис. 3.15).
Рис. 3.15
Из каждого узла выходят две ветви — при движении по левой ветви мы выбираем 0, при движении по правой — 1. В некоторых узлах записаны буквы, остальные обозначены точками. Участки ветвей, соединяющие два узла, называются рёбрами. Чтобы получить код буквы, нужно пройти по ветвям от корня к узлу, в котором записана эта буква, и выписать коды всех пройденных рёбер.
Проверьте, выполняется ли для этого кода условие Фано: ни одно из кодовых слов не совпадёт с началом другого кодового слова.
Как сразу определить это по дереву? Где должны располагаться узлы с буквами, чтобы условие Фано выполнялось?
Постройте дерево для следующего кода:
| А | Б | В | Г |
| 00 | 100 | 101 | 01 |
Выполняется ли для него условие Фано? Сколько букв можно добавить в кодовую таблицу, чтобы все коды были не длиннее трёх символов и выполнялось условие Фано?
Следующая страница 
Выводы. Интеллект-карта
Cкачать материалы урока
