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