Лабораторная работа по "Программированию"

Лабораторная работа № 5 по дисциплине «Программирование» (весенний семестр)

Цель задания: приобрести практические навыки разработки программ с применением динамических структур типа «дерево».

Порядок выполнения лабораторной работы:

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

1. создания элементов дерева заданного типа в динамической памяти (ввод значений дерева с клавиатуры);

2. вставка созданного в п.1 элемента в дерево и установка связей между элементами;

Примечание: для дерева типа В – правило вставки в первое свободное место одного уровня, при заполнении всех полей одного уровня, создается следующий и т.д.; для дерева типа Г – правило вставки установите самостоятельно (произвольно).

3. обход дерева (вывод значений на дисплей) в заданном порядке.

1. Оформите отчет по лабораторной работе
2. Ответьте на контрольные вопросы и защитите работу

Требования к оформлению лабораторной работы и отчета:

1. Модуль программы должен предваряться комментарием с текстом исходной задачи, имена переменных и компонентов должны быть понятны стороннему пользователю или сопровождаться комментарием, объясняющим их смысл. Имена проекта и модуля должны иметь осмысленные названия.
2. Отчет по лабораторной работе должен содержать: титульный лист, текст задания, блок-схемы алгоритмов основных функций программы, листинг самой программы с комментариями.

Примечание.

Оценка за лабораторную работу может быть повышена или понижена следующим образом:

-2        - не выполнены какие-либо требования задания,

-1        - внутри функции сделано прямое обращение (не через аргументы) к внешним для данной функции переменным,

+1        - работа защищена досрочно,

+1        - для хранения массивов (строк) использована динамическая память,

+1        - для доступа к элементам не использовались индексные переменные.

Контрольные вопросы:

1. Напишите псевдокод рекурсивной функции, которая формирует двоичное дерево .

1. Постройте дерево с семью узлами, глубина которого равна 3.

                                  Варианты заданий

Типы деревьев

Дерево типа А

Бинарное дерево

Каждая вершина дерева содержит:

- 2 указателя (на каждый альтернативный путь поиска на поддерево);

- данные – указатель на объект, содержащий данные, принадлежащие этой вершине.

Примечание: по Вашему усмотрению можете добавить вспомогательные поля;