§16. Списки и деревья | Дерево для двоичного кода (informatika_09_34_pol)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, базовый уровень)


Урок 12
§16. Списки и деревья



Содержание урока

Списки

Что такое дерево?

Из чего состоит дерево?

Где используются деревья?

Перебор вариантов

Дерево для двоичного кода

Выводы. Интеллект-карта

Вопросы и задания


Дерево для двоичного кода


Для двоичного кода тоже можно построить дерево.

А Б В Г Д
0 11 101 110 111

Например, для кода дерево выглядит так (рис. 3.15).

Рис. 3.15

Рис. 3.15

Из каждого узла выходят две ветви — при движении по левой ветви мы выбираем 0, при движении по правой — 1. В некоторых узлах записаны буквы, остальные обозначены точками. Участки ветвей, соединяющие два узла, называются рёбрами. Чтобы получить код буквы, нужно пройти по ветвям от корня к узлу, в котором записана эта буква, и выписать коды всех пройденных рёбер.

Проверьте, выполняется ли для этого кода условие Фано: ни одно из кодовых слов не совпадёт с началом другого кодового слова.

Как сразу определить это по дереву? Где должны располагаться узлы с буквами, чтобы условие Фано выполнялось?

Постройте дерево для следующего кода:

А Б В Г
00 100 101 01

Выполняется ли для него условие Фано? Сколько букв можно добавить в кодовую таблицу, чтобы все коды были не длиннее трёх символов и выполнялось условие Фано?

Следующая страница Выводы. Интеллект-карта



Cкачать материалы урока







Наверх