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

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

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

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

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

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

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

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

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

Задачи

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

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

40 - 2 * 3 - 4 * 5

Рис. 6.19

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

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

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