Деревья. Основные понятия | Хранение двоичного дерева в массиве (11_68_pol) (68 часов в уч. год)

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


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



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

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

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

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

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

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

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

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

Задачи


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


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

40 - 2 * 3 - 4 * 5

Рис. 6.19

Рис. 6.19

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

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



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







Наверх