Алгоритмы и Структуры данных. Деревья

Задача

Написать и отладить программу для работы с деревьями по предложенному преподавателем варианту индивидуального задания (табл. П.2.2). Программа должна выводить на экран изображение дерева с разметкой его вершин, сделанной заданным способом, а под ним — последовательность меток вершин при обходе дерева и результат вычисления заданного параметра. Можно взять за основу учебный пример, убрав из него все лишнее.

2. Сделать узел дерева и дерево в целом объектами соответствующих классов, а обходы дерева — функциями-членами для класса «дерево».

3. Объявить в классе «дерево» деструктор и все конструкторы, поддерживаемые по умолчанию. Сделать невозможным использование тех конструкторов, которые на самом деле не нужны. Сделать в тексте программы временные дополнения и убедиться, что это действительно так.

Вид дерева: Двоичное

Разметка: Симметричная

Способ обхода: В ширину

Что надо вычислить: Количество вершин, имеющих не более одного потомка

План отсчёта

1. Цель работы: исследование алгоритмов для работы с двоичным (троичным) деревом.

2. Задание на работу с деревьями.

3. Обоснование выбора способа представления деревьев в памяти ЭВМ. Здесь следует сделать ссылку на выводы в отчетах по разд. 1 и 2. 

4. Результаты прогона программы с генерацией случайного дерева (скриншоты).

5. Последовательность битов, вводом которой можно построить дерево, полученное в результате генерации (например, дерево на рисунке выше может быть получено вводом последовательности «111011001001001110010 100100»). 

6. Оценки временной сложности для каждой функции обхода дерева, использованной в программе: создание дерева, обработка, вывод.

7. Выводы о результатах испытания алгоритмов обхода деревьев.

8. Список использованной литературы.

9. Приложение: исходный текст программы для работы с деревьями.

Реализация должна базироваться на методах, описанных в третьей главе методички, прикреплённой в файлах. Так же будет предоставлен пример отсчёта, по которому надо составить соответствующий документ в соответствии с планом .