Основы программирования — второй семестр 08-09; Михалкович С.С.; IV часть

Деревья

Дерево как совокупность узлов, связанных ребрами (ветвями). Корень, листья дерева.

Примеры: главы и пункты книги, дерево разбора выражений.

Рекурсивное определение дерева

Бинарные деревья. Идеально сбалансированное, полное бинарное дерево.

Порядки обхода деревьев

• Инфиксный (левое, корень, правое)
• Префиксный (корень, левое, правое)
• Постфиксный (левое, правое, корень)

Задачи на бинарные деревья

Класс TreeNode<T>

Создание идеально сбалансированного дерева.

Вывод узлов дерева в инфиксном, префиксном, постфиксном порядке.

Связь деревьев и рекурсии.

Определение глубины дерева.

Количество листов в дереве.

Поиск элемента в дереве.

Бинарные деревья поиска

Определение БДП.

Добавление в БДП. Инвариантность БДП относительно операции добавления.

Оценка количества операций при добавлении. Худший случай.

Сортировка деревом. Асимптотическая сложность алгоритма.

Поиск элемента в БДП.