Лабораторной работе №3. Алгоритмы и структуры данных. Тема: Деревья. ЛЭТИ. 2020

Лабораторной работе №3. Алгоритмы и структуры данных.
Тема: Деревья. ЛЭТИ. 2020

Цель работы
Исследование алгоритмов для работы с двоичным деревом
Задание
В двоичном дереве сделать обратную разметку, обойти дерево в глубину и подсчитать количество левых листьев
Постановка задачи и описание решения
Для представления дерева в памяти предложен естественный способ – разветвляющийся список. Узлы дерева – объекты, связи между которыми осуществляются через указатели. Для создания дерева достаточно объявить корень, членами которого являются левый и правый указатели на узлы дерева. Для работы с деревом удобнее иметь отдельный класс “дерево”, в котором собираются данные о всем дереве и функции-члены для работы с ним, в то время как для узлов сделать отдельный класс и сделать его дружественным для класса “дерево”
В программе под левым листом понимается узел, который находится в указателе left предыдущего узла и у которого отсутствуют сыновья. То есть если у узла нет сыновей, он единственный сын предыдущего узла, но при этом он находится в указателе right, левым листом его считать нельзя!
Итак, в программе первым делом создается дерево. Функция создания дерева вызывает рекурсивную функцию создания узла.
Для создания дерева в памяти применяется прямой алгоритм обхода (для графов общего вида – обход в глубину. Для дерева эти термины эквивалентны). Первым шагом алгоритма является проверка необходимости создания узла. Если ответ положительный, узел создается, и в нем заполняются информационные поля. Далее заполняются поля указателей на каждого сына: для получения значения указателя алгоритм запускается рекурсивно. Результат – указатель на вновь созданный узел или нуль, если узел не создан
После создания дерева вызывается функция его обхода в глубину. Я решил модернизировать эту функцию, добавив в нее возможность нахождения левых листьев дерева. Для этого создается стек узлов дерева, в которое вносятся и обрабатываются необходимые узлы. Если у очередного узла у его левого сына отсутствуют сыновья, то счетчик левых листьев увеличивается на единицу.
В работе я решил не использовать перемещающий конструктор и перемещающее присваивание, поскольку в методичке написано: “сделать невозможным использование тех конструкторов, которые на самом деле не нужны”


Содержание
Введение ........................................................................................................ 3
Задание ........................................................................................................... 3
Постановка задачи и описание решения ..................................................... 3
Контрольные тесты ...................................................................................... 4
Вывод ............................................................................................................. 6
Список использованных источников........................................................... 7
Текст программы ........................................................................................... 8

2020