Курсовая работа бинарное дерево

Исследование задач поиска по дереву

Рассмотрение базовых операций с наиболее распространенными типами структуры данных «Дерево». Разработка программы «Tree Modeler» для работы с бинарным и общим деревом поиска. Последовательности посещений узлов при прямом, внутреннем и обратном обходах.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://allbest.ru

МИНИСТЕРСТВО СЕЛЬСКОГОХОЗЯЙСТВА РФ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Кубанский государственный аграрный университет

Факультет: Прикладная информатика

Кафедра компьютерных технологий и систем

Исследование задач поиска по дереву

Направление подготовки информационные системы и технологии

Направленность создание, модификация и сопровождение информационных систем, администрирование баз данных

Выполнил: Коблянский Владимир Сергеевич

Руководитель: Параскевов Александр Владимирович

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

Объект работы — структура данных «Дерево»

Предмет работы — задачи поиска по дереву.

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

Ключевые слова: ЗАДАЧИ ПОИСКА ПО ДЕРЕВУ, ПОИСК, АЛГОРИТМЫ, СТРУКТУРЫ ДАННЫХ.

11 табл., 12 рис., 5 библ., 6 прил.

1. Рассмотрение предметной области

1.1 Структура данных «Дерево»

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

1.3 Бинарное дерево поиска

1.3.1 Поиск элемента по ключу (FIND )

1.3.2 Удаление узла по ключу (REMOVE )

1.3.3 Вставка нового узла (INSERT)

1.4 Обход дерева

1.5 Постановка задачи

2. Технология разработки приложения

2.1 Макет приложения

2.2 Описание программной части приложения

2.3 Руководство для пользователя

3 Области применения

Список литературы

Приложения

Тема данной курсовой работы — «Исследование задач поиска по дереву». Она подразумевает рассмотрение базовых операций с наиболее распространенными типами структуры данных «Дерево», в особенности связанных с поиском. Актуальность данной темы обусловлена огромной сферой использования деревьев как способа хранения информации в самых разных областях науки. Но особенно важную роль деревья играют в информационных технологиях, так как в некоторых случаях они предоставляют более эффективные механизмы работы с данными, нежели в других структурах.

В процессе выполнения данной курсовой работы будет:

· изложен базовый теоретический материал, связанный с задачами поиска по дереву

· выполнена реализация решений базовых задач поиска по дереву в виде готового программного продукта

· описаны сферы применения деревьев и задач поиска, их преимущества и недостатки

Цель данной курсовой работы — изучить основные теоретические понятия, связанные со структурой данных «Дерево» и методами поиска по ней, описать сферу применения и программно их реализовать. Объектом данной курсовой работы является структура данных «Дерево», а предметом — задачи поиска по дереву.

1 Рассмотрение предметной области

Нелинейные структуры данных выражают более сложные отношения порядка между объектами, чем отношения предшествования и следования. Наиболее важным видом нелинейных структур являются деревья. В данной курсовой работе будут рассмотрены деревья общего вида, бинарные деревья и бинарные деревья поиска, но особое внимание будет уделено последнему типу.

Дерево (непустое) — это конечное множество объектов T, состоящее из одного или более узлов, для которых выполняются следующие условия:

· Имеется один специально выделенный узел, называемый корнем дерева

· Остальные узлы (исключая корень) содержатся в m попарно непересекающихся множествах T1, …,Tm, каждое из которых, в свою очередь, является деревом. Деревья T1, …,Tm называются поддеревьями данного корня. Пример дерева общего вида представлен на рисунке 1.1:

Рисунок 1.1 — Пример дерева общего вида

Узел дерева, как правило, включает в себя ссылку на родителя, значение (ключ) и ссылки на дочерние узлы.

Пустым называется дерево, которое не содержит узлов.

Число поддеревьев данного узла называется степенью этого узла. Максимальная степень всех узлов дерева называется степенью дерева (обозначим как d). Узел с нулевой степенью называется листом или терминальным узлом.

Уровень узла — выраженная в числе ребер длина пути, ведущего из узла в корень дерева, плюс единица. Если некоторый узел A располагается на уровне i, то находящийся непосредственно ниже его на уровне i + 1 узел B называется непосредственным потомком узла A, а узел A называется непосредственным потомком узла B.

Максимальный уровень всех узлов дерева называется высотой или глубиной дерева (обозначим как h). Высота пустого дерева равна нулю, высота дерева, состоящего из одного корня, равна единице. Дерево, содержащее максимальное число узлов называется полным. В полном дереве у всех узлов, за исключением терминальных, число непосредственных потомков равно степени дерева. Количество узлов в полном дереве степени d высотой h вычисляется по формуле (1):

Основные свойства деревьев общего вида:

· Каждый узел, за исключением корня, имеет только одного предка

· Каждый узел связан с корнем единственным путем, то есть в деревьях отсутствуют замкнутые контуры (циклы)

Дерево называется упорядоченным, если в его определении имеет значение относительный порядок поддеревьев T1,…,Tm.

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

На практике наиболее часто применяют упорядоченные деревья второй степени, которые ещё называют бинарными деревьями.

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

Пример бинарного дерева приведен на рисунке 1.2:

Рисунок 1.2 — пример бинарного дерева

Максимальное число узлов в бинарном дереве высотой h вычисляется по формуле (2):

Максимальное число узлов на уровне i в бинарном дереве находят по формуле (3):

1.3 Бинарное дерево поиска

Бинарное дерево поиска (БДП) — это бинарное дерево, для которого выполняются следующие условия:

· Оба поддерева являются двоичными деревьями поиска

· У всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X

· У всех узлов правого поддерева произвольного узла X значения данных больше либо равны, нежели значение самого узла X

Основные операции с бинарным деревом поиска:

1.3.1 Поиск элемента по ключу (FIND)

Дано: дерево T и ключ K

Задача: проверить, содержит ли дерево T узел с ключом K, и если да, вернуть ссылку на этот узел.

Алгоритм:

· Если дерево пустое, сообщить, что узел не найден, и остановиться

· Иначе сравнить K со значением ключа корня X

· Если K = X, вернуть ссылку на этот узел и остановиться

· Если K > X, рекурсивно искать узел с ключом K в правом поддереве T

1.3.2 Удаление узла по ключу (REMOVE)

Дано: дерево T и ключ K

Задача: удалить из дерева T узел с ключом K, если он в нем содержится, и так, чтобы дерево осталось упорядоченным

Алгоритм:

· Если дерево пустое, остановиться

· Иначе сравнить K со значением ключа корня X

· Если K > X, рекурсивно удалить узел с ключом K из правого поддерева T

· Если обоих детей нет, удаляем текущий узел и обнуляем ссылку на него у узла-родителя

· Если одного из детей нет, то значения полей ребенка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m

· Если оба ребенка присутствуют, то

· Если самый левый элемент правого поддерева m не имеет детей

· Копируем значение ключа m в удаляемый элемент

· Если m имеет правое поддерево:

· Копируем значение ключа m в удаляемый элемент

· Заменяем у родительского узла ссылку на m ссылкой на правое поддерево m

Дано: дерево T и узел с ключом K

Задача: вставить узел с ключом K в дерево так, чтобы оно осталось упорядоченным

Алгоритм:

· Если дерево пустое, заменить его на дерево с одним корневым узлом с ключом K

· Иначе сравнить K со значением ключа корня X

· Если K = X, рекурсивно вставить узел с ключом K в правое поддерево T

· Если K > X, рекурсивно вставить узел с ключом K в правое поддерево T

1.4 Обход дерева

Наиболее типичная операция, выполняемая над деревьями, — обход дерева. Обход — это операция, при выполнении которой каждый узел обрабатывается ровно один раз одинаковым образом. Обход дерева заключается в разбиении на дерева на корень, левое и правое поддеревья (в случае с бинарными деревьями) и применении к каждому из поддеревьев соответствующей операции обработки до тех пор, пока в процессе разбиения не будет получено пустое дерево.

Обходы бинарных деревьев имеют вполне практические приложения. В силу двоичности выделяют три возможных алгоритма обхода. Все три алгоритма являются рекурсивными.

3. Обойти правое поддерево

Обратный порядок обхода:

2. Обойти правое поддерево

Внутренний порядок обхода:

3. Обойти правое поддерево

Пример обхода бинарного дерева:

Рисунок 1.3 — примеры обхода дерева тремя способами

На рисунке 1.3 изображены последовательности посещений узлов при прямом (1), внутреннем (2) и обратном обходах бинарного дерева.

1.5 Постановка задачи

Одной из основных задач данной курсовой работы является реализация решений базовых задач поиска по дереву в виде готового программного продукта. Название разрабатываемого приложения — «Tree Modeler». На русский язык это можно перевести как «Программа для моделирования деревьев». Данное приложение должно реализовывать основные функции для построения деревьев и решения задач поиска. В соответствии с образовательной программой автора курсовой работы, данная программа будет поддерживать работу с двумя типами деревьев: деревьями общего типа и бинарными деревьями поиска.

При работе с бинарными деревьями поиска у пользователя будет возможность добавлять новые узлы (INSERT), искать в дереве узлы (FIND) и удалять узлы с заданным значением ключа (REMOVE). Также для удобства пользователя будут доступны дополнительные функции, такие как удаление дерева или генерация дерева с заданным количеством узлов.

При работе с деревьями общего вида будут реализованы те же основные функции, что и при работе с БДП, однако алгоритм их работы будет соответствовать принципам работы с деревьями общего вида.

Для реализации поставленной задачи в качестве языка разработки был выбран C#, а в качестве среды разработки — Microsoft Visual Studio Enterprise 2019. В основном этот выбор связан с учебной программой автора данной курсовой работы.

Оборудование, используемое для выполнения курсовой работы: персональный компьютер с установленными на него программами Microsoft Word 2007 и Microsoft Visual Studio Enterprise 2019 со всеми расширениями, необходимыми для разработки программного обеспечения на языке программирования C#.

2. Технология разработки приложения

2.1 Макет приложения

С точки зрения графической составляющей, приложение состоит из трех основных частей.

Это форма главного меню, форма для работы с бинарным деревом поиска и форма для работы с деревом общего вида. Макет формы главного меню приведен на рисунке 2.1

Рисунок 2.1 — Макет формы главного меню

Описание структурных элементов формы главного меню приведено в таблице 2.1

Таблица 2.1 — Описание структурных элементов формы главного меню

Отображает название приложение.

Открывает форму для работы с бинарным деревом поиска.

Открывает форму для работы с деревом общего вида.

Макет формы для работы с бинарным деревом поиска изображен на рисунке 2.2

Рисунок 2.2 — макет формы для работы с бинарным деревом поиска

Описание структурных элементов формы для работы с бинарным деревом поиска приведено в таблице 2.2:

Таблица 2.2 — Описание структурных элементов формы для работы с БДП

Объединяет элементы управления деревом.

Используется как контейнер для pictureBox1.

Элемент вывода изображения (pictureBox)

Отображает дерево в его текущем состоянии графически.

Регулятор числовых значений (numericUpDown)

Позволяет ввести или выбрать значение ключа для добавляемого узла.

Регулятор числовых значений (numericUpDown)

Позволяет ввести или выбрать значение ключа для поиска узла.

Регулятор числовых значений (numericUpDown)

Позволяет ввести или выбрать значение ключа для удаления узла.

При нажатии создает дерево с количеством случайных узлов, указанном в numericUpDown4.

Регулятор числовых значений (numericUpDown)

Позволяет ввести или выбрать количество узлов для создания случайного дерева.

Макет формы для работы с деревом общего вида изображен на рисунке 2.3:

Рисунок 2.3 — Макет формы для работы с деревом общего вида

Описание структурных элементов формы для работы с бинарным деревом поиска приведено в таблице 2.3:

Таблица 2.3 — Описание элементов формы для работы с БДП

Источник