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

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

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

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

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

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

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

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

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

Задачи

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

1. Дайте определение понятий «дерево», «корень», «лист», «родитель», «сын», потомок», «предок», «высота дерева».
2. Где используются структуры типа «дерево» в информатике и в других областях?
3. Объясните рекурсивное определение дерева.
4. Можно ли считать, что линейный список — это частный случай дерева?
5. Какими свойствами обладает дерево поиска?
6. Подумайте, как можно построить дерево поиска из массива данных.
7. Какие преимущества имеет поиск с помощью дерева?
8. Что такое обход дерева?
9. Какие способы обхода дерева вы знаете? Придумайте другие способы обхода.
10. Как строится дерево для вычисления арифметического выражения?
11. Как можно представить дерево в программе на Паскале?
12. Как указать, что узел дерева не имеет левого (правого) сына?
13. Как выделяется память под новый узел?
14. Как вы думаете, почему рекурсивные алгоритмы работы с деревьями получаются проще, чем нерекурсивные?
15. Как хранить двоичное дерево в массиве? Можно ли использовать такой приём для хранения деревьев, в которых узлы могут иметь больше двух сыновей? Приведите пример.

Подготовьте сообщение

а) «Деревья в языке Си»
б) «Деревья в языке Python»
в) «Диграммы связей (mind maps)»

Следующая страница Задачи

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