Лабораторная работа №3

Введение

Задание будет состоять из нескольких частей, поэтому не затягивайте со сдачей. Все структуры, необходимые для реализации описанных ниже заданий должны быть взяты из предыдущих лабораторных работ.

Задание

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

Для защиты

• Чтение скобочной записи (путем чтения из файла)
• Шаг 1 или создает двоичное дерево или сообщает об ошибке (неправильные символы, неправильно расставлены скобки, не двоичное дерево вообще и тп)
• Обойти полученное дерево и создать АВЛ (или КЧ) дерево.
• Продемонстрировать вывод всех узлов 4 способами: в ширину и 3 в глубину.