Основы программирования — второй семестр 08-09; Михалкович С.С.; IV часть — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Admin (обсуждение | вклад) (→Задачи на бинарные деревья) |
Admin (обсуждение | вклад) (→Бинарные деревья поиска) |
||
| Строка 36: | Строка 36: | ||
Определение БДП. | Определение БДП. | ||
| − | Добавление в БДП. Оценка количества операций при добавлении. Худший случай. | + | Добавление в БДП. Инвариантность БДП относительно операции добавления. |
| + | |||
| + | Оценка количества операций при добавлении. Худший случай. | ||
Поиск элемента в БДП. | Поиск элемента в БДП. | ||
Версия 00:04, 25 марта 2009
Содержание
Деревья
Дерево как совокупность узлов, связанных ребрами (ветвями). Корень, листья дерева.
Примеры: главы и пункты книги, дерево разбора выражений.
Рекурсивное определение дерева
Бинарные деревья. Идеально сбалансированное, полное бинарное дерево.
Порядки обхода деревьев
- Инфиксный (левое, корень, правое)
- Префиксный (корень, левое, правое)
- Постфиксный (левое, правое, корень)
Задачи на бинарные деревья
Класс TreeNode<T>
Создание идеально сбалансированного дерева.
Вывод узлов дерева в инфиксном, префиксном, постфиксном порядке.
Связь деревьев и рекурсии.
Определение глубины дерева.
Количество листов в дереве.
Поиск элемента в дереве.
Бинарные деревья поиска
Определение БДП.
Добавление в БДП. Инвариантность БДП относительно операции добавления.
Оценка количества операций при добавлении. Худший случай.
Поиск элемента в БДП.
