СДлб5
.pdf
Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА Отчет по практической работе №5 по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
Принял:
преподаватель КИБЭВС
Д.Р. Уразаев
Томск 2022
СОДЕРЖАНИЕ
1 |
Введение .................................................................................................................. |
3 |
|
2 |
Ход работы .............................................................................................................. |
4 |
|
2.1 |
Описание класса Tree ..................................................................................... |
4 |
|
2.2 |
Описание реализации варианта .................................................................... |
6 |
|
2.3 |
Удаление элемента из дерева......................................................................... |
7 |
|
2.4 |
Демонстрация работы программы................................................................. |
8 |
|
Заключение ............................................................................................................... |
10 |
||
2
1 Введение
Целью работы является реализация бинарного дерева при помощи динамических структур. Программа будет разработана на языке программирования C#.
Задание
Реализовать бинарное дерево поиска при помощи динамических структур
(классы). Предусмотреть следующие интерфейсные методы:
1.Инициализация пустого дерева.
2.Добавление элемента в дерево.
3.Удаление элемента из дерева.
4.Очистка дерева.
5.Вывод дерева.
3
2 Ход работы
Дерево – это граф без петель и циклов. Деревья используются для организации данных в виде иерархической структуры. Первый узел дерева называется корнем. Если этот корневой узел соединен с другим узлом, тогда корень является родительским узлом, а связанный с ним узел – дочерним.
Листья – это последние узлы на дереве.
Листинг программы представлен в Приложении А.
2.1 Описание класса Tree
Для добавления элемента в дерево используется метод AddItem. Он сравнивает значение добавляемого элемента с существующим, иесли значение элемента больше существующего, выполняется проверка на наличие правого поддерева, и, если оно отсутствует, элемент записывается вправо, иначе происходит вызов функции AddItem для следующего правого элемента.
Если же добавляемый элемент меньше существующего, выполняется проверка на наличие левого поддерева, и, если оно отсутствует, элемент записывается влево, иначе происходит вызов функции AddItem для следующего левого элемента.
Рисунок 2.1.1 – Метод AddItem
После удаления и обработки текущего элемента, в очередь помещаются два его дополнительных элемента4 .
Рисунок 2.1.2-Метод LevelOrderTraversal
При выводе проверяется есть ли корневой элемент, если нет, то выводится сообщение о том что дерево пустое
Рисунок 2.1.3-Метод Print
5
2.2 Описание реализации варианта
Для нахождения самого большого элемента и теории мы должны найти самый крайний правый элемент.
Исходя из теоритических сведений приведенных выше был написан метод (Maximum), который перебирает значения до тех пор, пока не найдет самый правый лист бинарного дерева.
Рисунок 2.2 – Метод Maximum
6
2.3 Удаление элемента из дерева
Рисунок 2.3 – Метод RemoveItem
Если удаляемый элемент не содержит левого поддерева, на его место становится следующий элемент от правого поддерева.
Если же элемент имеет поддеревья с обоих сторон, на его место становится наименьший элемент из правого поддерева.
7
Рисунок 2.3.1 – Метод RemoveItem
2.4 Демонстрация работы программы
Листинг программы приведен в Приложении А
Демонстрация работы программы представлена на рисунке 2.4.
8
Рисунок 2.4– Работа программы
9
Заключение
В результате практической работы был написан алгоритм реализации бинарного дерева в соответствии с заданным условием. Также был написан метод по нахождению максимального элемента дерева.
10