Лабораторная работа №3
Введение
Задание будет состоять из нескольких частей, поэтому не затягивайте со сдачей. Все структуры, необходимые для реализации описанных ниже заданий должны быть взяты из предыдущих лабораторных работ.
Задание
-
Необходимо реализовать обычное двоичное дерево (не поиска и не балансирующее) с реализацией обхода этого дерева в глубину (направление обхода не важно, обход через рекурсию) -
Необходимо реализовать алгоритм для парсинга скобочной записи дерева. Пример: (8 (9 (5)) (1)) - корень 8, левый сын 9, правый 1, левый сын узла 9 – 5. Входные данные должны быть получены путем чтения из файла. -
Реализовать АВЛ дерево (усложненный вариант — красно-черное дерево) с реализацией алгоритмов вставки, удаления, поиска, обхода в ширину, обхода в глубину (все 3 вида и использовать итеративный вариант).
Для защиты
-
Чтение скобочной записи (путем чтения из файла) -
Шаг 1 или создает двоичное дерево или сообщает об ошибке (неправильные символы, неправильно расставлены скобки, не двоичное дерево вообще и тп) -
Обойти полученное дерево и создать АВЛ (или КЧ) дерево. -
Продемонстрировать вывод всех узлов 4 способами: в ширину и 3 в глубину.
Edited by Петров Иван Рюрикович