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



Уроки 77 - 79
Деревья. Основные понятия
(§43. Деревья)




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

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

Деревья поиска

Обход двоичного дерева

Вычисление арифметических выражений

Использование связанных структур

Хранение двоичного дерева в массиве

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

Задачи


Хранение двоичного дерева в массиве


Двоичные деревья можно хранить в (динамическом) массиве почти так же, как и списки. Вопрос о том, как сохранить структуру (взаимосвязь узлов), решается следующим образом. Если нумерация элементов массива А начинается с 1, то сыновья элемента A[i] — это A[2*i] и A[2*i+1]. На рисунке 6.19 показан порядок расположения элементов в массиве для дерева, соответствующего выражению

40 - 2 * 3 - 4 * 5

Рис. 6.19

Рис. 6.19

Алгоритм вычисления выражения остаётся прежним, изменяется только метод хранения данных. Обратите внимание, что некоторые элементы остались пустыми, это значит, что их родитель — лист дерева.

Следующая страница Вопросы и задания



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






Наверх