Размещено на 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 Рассмотрение предметной области

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

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

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

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

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

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

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

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

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

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

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

	(1)

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

· Корень не имеет предков

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

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

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



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

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

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

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

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

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

	(2)

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

	(3)



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

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

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

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

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

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

· Найти узел по ключу

· Вставить новый узел

· Удалить узел по ключу

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

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

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

Алгоритм:

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

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

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

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

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



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

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

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

Алгоритм:

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

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

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

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

· Если K = X:

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

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

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

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

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

· Удаляем m

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

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

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

· Удаляем m



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

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

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

Алгоритм:

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

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

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

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

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

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

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

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

Прямой порядок обхода:

1. Посетить корень дерева

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

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

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

1. Обойти левое поддерево

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

3. Посетить корень дерева

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

1. Обойти левое поддерево

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 - Описание структурных элементов формы главного меню

Наименование	Элемент	Назначение
label 1	Надпись (label)	Отображает название приложение.
button 1	Кнопка (button)	Открывает форму для работы с бинарным деревом поиска.
button 2	Кнопка (button)	Открывает форму для работы с деревом общего вида.
button 4	Кнопка (button)	Закрывает приложение.

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

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

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

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

Наименование	Элемент	Назначение.
panel1	Панель (panel)	Объединяет элементы управления деревом.
panel2	Панель (panel)	Используется как контейнер для pictureBox1.
pictureBox1	Элемент вывода изображения (pictureBox)	Отображает дерево в его текущем состоянии графически.
button1	Кнопка (button)	Функция «Добавить узел».
numericUpDown1	Регулятор числовых значений (numericUpDown)	Позволяет ввести или выбрать значение ключа для добавляемого узла.
button2	Кнопка (button)	Функция «Найти узел».
numericUpDown2	Регулятор числовых значений (numericUpDown)	Позволяет ввести или выбрать значение ключа для поиска узла.
button3	Кнопка (button)	Функция «Удалить узел».
numericUpDown3	Регулятор числовых значений (numericUpDown)	Позволяет ввести или выбрать значение ключа для удаления узла.
button4	Кнопка (button)	При нажатии создает дерево с количеством случайных узлов, указанном в numericUpDown4.
numericUpDown4	Регулятор числовых значений (numericUpDown)	Позволяет ввести или выбрать количество узлов для создания случайного дерева.
button5	Кнопка (button)	Функция «Удалить дерево».

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

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

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

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

Наименование	Элемент	Назначение
panel1	Панель (panel)	Объединяет элементы управления деревом.
panel2	Панель (panel)	Используется как контейнер для pictureBox1.
pictureBox1	Элемент вывода изображения (pictureBox)	Отображает дерево в его текущем состоянии графически.
button1	Кнопка (button)	Функция «Добавить узел».
numericUpDown1	Регулятор числовых значений (numericUpDown)	Позволяет ввести или выбрать значение ключа для добавляемого узла.
button2	Кнопка (button)	Функция «Найти узел».
numericUpDown2	Регулятор числовых значений (numericUpDown)	Позволяет ввести или выбрать значение ключа для поиска узла.
button3	Кнопка (button)	Функция «Удалить узел».

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

При разработке данного приложения были использованы только стандартные разработки C# и Windows Forms.

Описание пространств имен, задействованных в процессе разработки приложения, приведено в таблице 2.4:

Таблица 2.4 - Описание пространств имен приложения

Наименование	Описание
System	Содержит фундаментальные и базовые классы, определяющие часто используемые типы значений и ссылочных данных, события и обработчики событий, интерфейсы, атрибуты и исключения обработки.
TreeModeler	Пространство имен, созданное специально для разрабатываемого приложения.

Описание классов, созданных в процессе разработки приложения, приведено в таблице 2.5:

Таблица 2.5 - Описание классов приложения

Класс	Описание
BinaryTree	Класс бинарного дерева поиска. В нем определены основные свойства и функции БДП.
BinaryTreeNode	Класс узла бинарного дерева поиска.
BinaryTreeNodePosition	Класс для хранения координат узла бинарного дерева поиска.
GeneralTree	Класс дерева общего вида. В нем определены основные свойства и функции для работы с деревом общего вида.
GeneralTreeNode	Класс узла дерева общего вида.
GeneralTreeNodePosition	Класс для хранения координат узла дерева общего вида.

Далее будут рассмотрены свойства, поля и методы данных классов. Описание для класса BinaryTree приведено в таблице 2.6

Таблица 2.6 - Описание элементов класса BinaryTree

Строка объявления	Описание
public BinaryTreeNode Root	Свойство, указывающее на корневой узел дерева.
public int Height	Свойство для хранения высоты дерева.
public BinaryTreeNode Add(int data)	Метод, реализующий функцию «Добавить новый узел». Принимает на вход значение ключа, создает узел с таким ключом и добавляет его в дерево. Возвращает ссылку на созданный узел.
public BinaryTreeNode Find(int data)	Метод, реализующий функцию «Найти узел». Принимает на вход значение ключа и пытается найти в дереве узел с таким ключом. В случае успеха возвращает ссылку на этот узел.
public void Remove(int data)	Метод, реализующий функцию «Удалить узел». Принимает на вход значение ключа и пытается найти в дереве узел с таким ключом. В случае успеха вызывает один из четырех вспомогательных методов, в зависимости от его потомков.
public void RemoveLeaf(BinaryTreeNode node)	Первый вспомогательный метод, предназначен для удаления узла без потомков.
public void RemoveNodeWithRightChild(BinaryTreeNode node)	Второй вспомогательный метод, предназначен для удаления узла, у которого есть только правый потомок.
public void RemoveNodeWithLeftChild(BinaryTreeNode node)	Третий вспомогательный метод, предназначен для удаления узла, у которого есть только левый потомок
public void RemoveNodeWithTwoChildren(BinaryTreeNode node)	Четвертый вспомогательный метод, предназначен для удаления узла, у которого есть два потомка.
public int GetHeight(BinaryTreeNode node)	Метод принимает на вход корневой узел дерева и возвращает его высоту.



Описание элементов класса GeneralTree приведено в таблице 2.7:

Таблица 2.7 - Описание элементов класса GeneralTree

Строка объявления	Описание
public GeneralTreeNode Root	Свойство, указывающее на корневой узел дерева.
public void Add(int data, GeneralTreeNode selected)	Метод, реализующий функцию «Добавить новый узел». Принимает на вход значение ключа и ссылку на родительский узел, создает узел с таким ключом и добавляет его как дочерний узел для переданного родительского узла.
public GeneralTreeNode Find(int data, GeneralTreeNode node)	Метод, реализующий функцию «Найти узел». Рекурсивно обходит дерево в прямом порядке и ищет узел с переданным значением ключа. В случае успеха возвращает ссылку на этот узел.
public void Remove(GeneralTreeNode selected)	Метод, реализующий функцию «Удалить узел». Принимает на вход ссылку на узел и удаляет его из дерева.
public int GetHeight(GeneralTreeNode node)	Метод принимает на вход корневой узел дерева и возвращает его высоту.

Описание элементов класса BinaryTreeNode приведено в таблице 2.8:

Таблица 2.8 - Описание элементов класса BinaryTreeNode

Строка объявления	Описание
public BinaryTreeNode Parent	Ссылка на родительский узел.
public BinaryTreeNode LeftChild	Ссылка на левого потомка.
public BinaryTreeNode RightChild	Ссылка на правого потомка.
Строка объявления	Описание
public bool IsLeaf	Свойство указывает, является ли узел листом.
public bool IsLeftChild	Свойство указывает, является ли узел левым потомком.
public bool IsRigthChild	Свойство указывает, является ли узел правым потомком.
public int Data	Свойство, хранящее значение ключа

Описание элементов класса GeneralTreeNode представлено в таблице 2.9:



Таблица 2.9 - Описание элементов класса GeneralTreeNode

Строка объявления	Описание
public GeneralTreeNode Parent	Ссылка на родительский узел
public List<GeneralTreeNode> Children	Список ссылок на дочерние узлы
public int Data	Свойство, хранящее значение ключа

Описания элементов классов BinaryTreeNodePosition и GeneralTreeNodePosition представлены в таблицах 2.10 и 2.11 соответственно:

Таблица 2.10 - Описание элементов класса BinaryTreeNodePosition

Строка объявления	Описание
public BinaryTreeNode node	Ссылка на объект БДП
public float X	Свойство, хранящее текущую координату узла по X
public float Y	Свойство, хранящее текущую координату узла по Y

Таблица 2.11 - Описание элементов класса GeneralTreeNodePosition

Строка объявления	Описание
public BinaryTreeNode node	Ссылка на объект дерева общего вида
public float X	Свойство, хранящее текущую координату узла по X
public float Y	Свойство, хранящее текущую координату узла по Y

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

Приведенные ниже инструкции предоставляют исчерпывающую информацию по работе с данным приложением.

При запуске приложения откроется окно с главным меню приложения (рисунок 2.4):



Рисунок 2.4 - Главное меню приложения

При нажатии на кнопку «Бинарное дерево поиска» закроется главное меню и откроется форма для работы с БДП (рисунок 2.5):

Рисунок 2.5 - Форма работы с БДП

При нажатии на кнопки «Добавить узел», «Удалить узел» и «Удалить дерево» можно вносить изменения в БДП. Значение ключа для этих функций можно ввести в поля под соответствующими кнопками.

При внесении изменений дерево будет перерисовано. Также имеется возможность создать случайное дерево с заданным количеством узлов, нажав на кнопку «Создать дерево с кол-вом узлов». Пример случайно сгенерированного дерева изображен на рисунке 2.6:

Рисунок 2.6 - Пример случайного дерева

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

При нажатии на кнопку «Найти узел» приложение графически покажет процесс поиска узла с нужным значением ключа. Посещаемые узлы будут на время менять цвет границы на оранжевый, а найденный узел изменит цвет границы на красный. Примеры поиска изображены на рисунках 2.7 и 2.8 соответственно. программа дерево бинарный поиск



Рисунок 2.7 - Приложение в процессе поиска узла с ключом 42

Рисунок 2.8 - Приложение нашло узел с ключом 42



При нажатии на кнопку «Дерево общего вида» в главном меню откроется форма для работы с деревом общего вида (рисунок 2.9):

Рисунок 2.9 - Форма для работы с деревом общего вида

В данной форме у пользователя есть возможность выбрать нужный узел дерева, кликнув по нему правой кнопкой мыши. При выделении узел меняет цвет границы на фиолетовый. После выделения узла у пользователя есть возможность добавить для него дочерний узел или удалить его, нажав на соответствующие кнопки. Пример выделенного узла изображен на рисунке 2.10:

Рисунок 2.10 - Пример выделенного узла

Графический поиск и удаление дерева реализованы аналогичным образом, как в форме для работы с БДП.



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

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

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

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



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

1. Симонова, Е. В. Структуры данных в C#: линейные и нелинейные динамические структуры : учебное пособие / Е. В. Симонова. -- Санкт-Петербург : Лань, 2018. -- 152 с.

2. Папшев, С. В. Дискретная математика. Курс лекций для студентов естественнонаучных направлений подготовки : учебное пособие / С. В. Папшев. -- Санкт-Петербург : Лань, 2019. -- 192 с.

3. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы : учебное пособие / М. О. Асанов, В. А. Баранский, В. В. Расин. -- 3-е изд., стер. -- Санкт-Петербург : Лань, 2020. -- 364 с.

4. Тюкачев, Н. А. C#. Алгоритмы и структуры данных : учебное пособие / Н. А. Тюкачев, В. Г. Хлебостроев. -- 3-е изд., стер. -- Санкт-Петербург : Лань, 2018. -- 232 с.

5. Mehlhorn, K. Datenstrukturen und effiziente Algorithmen - Band 1: Sortieren und Suchen / K. Mehlhorn. - Stuttgart Teubner, 1988. - 317 s.



Приложение А

Листинг класса BinaryTree

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace TreeModeler

{

public class BinaryTree

{

public BinaryTreeNode Root { get; set; }

public int Height { get; set; }

public BinaryTreeNode Add(int data)

{

BinaryTreeNode node;

if (Root == null)

{

Root = new BinaryTreeNode(data, null);

return Root;

}

else

{

BinaryTreeNode current = Root;

while (true)

{

if (data < current.Data)

{

if (current.LeftChild != null)

{

current = current.LeftChild;

continue;

}

else

{

node = new BinaryTreeNode(data, current);

current.LeftChild = node;

return node;

}

}

else

{

if (current.RightChild != null)

{

current = current.RightChild;

continue;

}

else

{

node = new BinaryTreeNode(data, current);

current.RightChild = node;

return node;

}

}

}

}

}

public BinaryTreeNode Find(int data)

{

BinaryTreeNode result = null;

if (Root == null)

{

return null;

}

BinaryTreeNode current = Root;

while (true)

{

if (data == current.Data)

{

result = current;

break;

}

if (data < current.Data)

{

if (current.LeftChild != null)

{

current = current.LeftChild;

continue;

}

break;

}

if (data > current.Data)

{

if (current.RightChild != null)

{

current = current.RightChild;

continue;

}

break;

}

}

return result;

}

public void Remove(int data)

{

BinaryTreeNode node = Find(data);

if (node == null)

return;

if (node.IsLeaf)

RemoveLeaf(node);

else if (node.RightChild != null && node.LeftChild == null)

RemoveNodeWithRightChild(node);

else if (node.RightChild == null && node.LeftChild != null)

RemoveNodeWithLeftChild(node);

else

RemoveNodeWithTwoChildren(node);

}

public void RemoveLeaf(BinaryTreeNode node)

{

if (node == Root)

Root = null;

else if (node.IsLeftChild)

node.Parent.LeftChild = null;

else

node.Parent.RightChild = null;

node.Parent = null;

}

public void RemoveNodeWithRightChild(BinaryTreeNode node)

{

if (node == Root)

Root = node.RightChild;

else if (node.IsLeftChild)

node.Parent.LeftChild = node.RightChild;

else

node.Parent.RightChild = node.RightChild;

node.RightChild.Parent = node?.Parent;

node.Parent = null;

node.RightChild = null;

}

public void RemoveNodeWithLeftChild(BinaryTreeNode node)

{

if (node == Root)

Root = node.LeftChild;

else if (node.IsLeftChild)

node.Parent.LeftChild = node.LeftChild;

else

node.Parent.RightChild = node.LeftChild;

node.LeftChild.Parent = node?.Parent;

node.Parent = null;

node.LeftChild = null;

}

public void RemoveNodeWithTwoChildren(BinaryTreeNode node)

{

BinaryTreeNode rightMin = node.RightChild;

while (rightMin.LeftChild != null)

rightMin = rightMin.LeftChild;

if (rightMin.RightChild == null)

{

RemoveLeaf(rightMin);

}

else

{

RemoveNodeWithRightChild(rightMin);

}

if (node == Root)

{

Root = rightMin;

Root.LeftChild = node.LeftChild;

Root.RightChild = node.RightChild;

}

else

{

if (node.IsLeftChild)

node.Parent.LeftChild = rightMin;

else

node.Parent.RightChild = rightMin;

rightMin.LeftChild = node.LeftChild;

rightMin.RightChild = node.RightChild;

rightMin.Parent = node.Parent;

}

if (rightMin.RightChild != null)

rightMin.RightChild.Parent = rightMin;

rightMin.LeftChild.Parent = rightMin;

node.Parent = null;

node.LeftChild = null;

node.RightChild = null;

}

public int GetHeight(BinaryTreeNode node)

{

if (node == null)

return 0;

else

{

return 1 +

Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild));

}

}

}

}



Приложение Б

Листинг класса GeneralTree

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace TreeModeler

{

public class GeneralTree

{

public GeneralTreeNode Root { get; set; }

public void Add(int data, GeneralTreeNode selected)

{

GeneralTreeNode node;

if (selected == null)

{

if (Root == null)

{

node = new GeneralTreeNode(data, null);

Root = node;

}

}

else

{

node = new GeneralTreeNode(data, selected);

selected.Children.Add(node);

}

}

public GeneralTreeNode Find(int data, GeneralTreeNode node)

{

if (node.Data == data)

{

return node;

}

else

{

foreach (var child in node.Children)

{

if (Find(data, child) != null) return Find(data, child);

}

return null;

}

}

public void Remove(GeneralTreeNode selected)

{

if (selected == null)

return;

if (selected == Root)

{

Root = null;

return;

}

selected.Parent.Children.Remove(selected);

selected.Parent = null;

}

public int GetHeight(GeneralTreeNode node)

{

if (node == null)

return 0;

else

{

if (node.Children.Count == 0)

{

return 1;

}

else

{

return 1 + node.Children.Max(x => GetHeight(x));

}

}

}

}

}



Приложение В

Листинг класса BinaryTreeNode

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace TreeModeler

{

public class BinaryTreeNode

{

public BinaryTreeNode Parent { get; set; }

public BinaryTreeNode LeftChild { get; set; }

public BinaryTreeNode RightChild { get; set; }

public bool IsLeaf => (LeftChild == null) && (RightChild == null);

public bool IsLeftChild => Parent.LeftChild == this;

public bool IsRigthChild => Parent.RightChild == this;

public int Data { get; set; }

public BinaryTreeNode(int data, BinaryTreeNode parent)

{

Data = data;

Parent = parent;

}

}

}



Приложение Г

Листинг класса GeneralTreeNode

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace TreeModeler

{

public class GeneralTreeNode

{

public GeneralTreeNode Parent { get; set; }

public List<GeneralTreeNode> Children { get; set; }

public int Data { get; set; }

public GeneralTreeNode(int data, GeneralTreeNode parent)

{

Data = data;

Parent = parent;

Children = new List<GeneralTreeNode>();

}

}

}



Приложение Д

Листинг класса BinaryTreeNodePosition

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace TreeModeler

{

public class BinaryTreeNodePosition

{

public BinaryTreeNode node { get; set; }

public float X { get; set; }

public float Y { get; set; }

}

}



Приложение Е

Листинг класса GeneralTreeNodePosition

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace TreeModeler

{

public class GeneralTreeNodePosition

{

public GeneralTreeNode node { get; set; }

public float X { get; set; }

public float Y { get; set; }

}

}

Размещено на Allbest.ru

...