Бинарные деревья поиска, основные действия с ними. Сущность префиксного (прямого), инфиксного (симметричного) и постфиксного (обратного) обхода в глубину. Описание функций редактирования исходных данных. Листинг и текст программы Form 1 и Form 2.
Аннотация к работе
Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. При работе с двоичными деревьями поиска возможен случай, когда дерево поиска по сути примет вид линейного связанного списка (например, если элементы подавались на вход в порядке возрастания), в данном случае бинарное дерево поиска называется вырожденным[3]. Также к достоинству данного метода можно отнести быструю скорость нахождения элемента, так как будет происходит сравнивание текущего элемента (в бинарном дереве) с элементом который требуется найти и уже по свойствам организации бинарных деревьев следует «дойти» до необходимого элемента[7]. «Delete»-метод удаления элемента из бинарного дерева (описаны все 3 случая удаления элемента из дерева);В ходе работы были изучены теоретические сведения и закреплены знания, полученные ранее при изучении дисциплины «Конструирование программ и языки программирования». Программа была разработана на языке программирования C#, с организацией удобного пользовательского интерфейса. создано полноценное приложение (со всеми функциями) по работе с информацией, организованной в виде бинарного дерева и осуществления визуализации данной информации. К достоинствам программного продукта можно отнести: возможность выполнения операций таких как: поиск (по ключу и максимального элемента), удаление данных, чтение информации из файла в бинарное дерево, сохранение бинарного дерева в файл, отображение информации в двух видах («Таблица» и «Дерево»), изменение уже имеющейся информации, добавление данных уже в сформированное бинарное дерево;if (Data.Parent.Left != null && (Data.Value as Sportsman).COMPARETO(Data.Parent.Left.Value) == 0) //Определяем, для отца (удаляемого элемента) мы левый сын ? if (Data.Parent.Left != null && (Data.Value as Sportsman).COMPARETO(Data.Parent.Left.Value) == 0) //Определяем, для отца (удаляемого элемента) мы левый сын ? Table.Rows.Add((Data.Value as Sportsman).FIO_OUTPUT, (Data.Value as Sportsman).age_OUTPUT, (Data.Value as Sportsman).wins_OUTPUT, (Data.Value as Sportsman).view_OUTPUT); Table.Rows.Add((Data.Value as Sportsman).FIO_OUTPUT, (Data.Value as Sportsman).age_OUTPUT, (Data.Value as Sportsman).wins_OUTPUT, (Data.Value as Sportsman).view_OUTPUT); //Добавление в дерево Table.Rows.Add((Data.Value as Sportsman).FIO_OUTPUT, (Data.Value as Sportsman).age_OUTPUT, (Data.Value as Sportsman).wins_OUTPUT, (Data.Value as Sportsman).
Введение
В связи с быстрым развитием современных информационных технологий и программным обеспечением возникает проблема с хранением данных, и организацией входной и выходной информацией, а также с поиском необходимой информации.
Исходя из этого, с целью обеспечения потребностей пользователей создается программный продукт, основанный на методе организации данных «Бинарное дерево поиска», которое хранит информацию в строгой иерархии, что позволяет ускорить работу с информацией (манипуляцией), и особенно с поиском необходимой информации.
Организация данных с помощью бинарных деревьев поиска позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени.
Основной целью данной работы является изучение фундаментальной абстрактной структуры - дерево, а также программная реализация добавления данных в упорядоченное бинарное дерево. Кроме того, необходимо закрепить теоретические знания и практические навыки в программировании на языке высокого уровня C#.
В данном курсовом проекте главной целью является разработка справочно-информационной системы на языке программирования C#, который предоставляет способ организации данных в виде «Бинарного дерева». Более того в программу должен быть заложен принцип, удобства, простоты и качества, что подразумевает отсутствие у пользователя перечня определенных навыков, за исключением простейшей компьютерной этики.
Справочно-информационная система - это система, обеспечивающая поиск и отбор необходимых данных в некоторой базе данных.
Разрабатываемый программный продукт отлично подойдет для организаций, которые в своей профессиональной среде сталкиваются с большим количеством информации.
Исходя из задач, актуальностью создаваемой программы является сокращение времени работы, рациональное распределение времени, что позволяет выполнить большой объем работы за более короткие сроки.
1. Бинарные деревья поиска
1.1 Древовидная структура - «Бинарное дерево поиска»
Бинарное (двоичное) дерево поиска - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева[1], а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом поиска. Эти подмножества называются правым и левым поддеревьями исходного дерева (рисунок 1.1).
Рисунок 1.1 - Бинарное дерево поиска
На рисунке вышепоказан наиболее часто встречающийся способ представления бинарного дерева. Оно состоит из девяти узлов. Корнем дерева является узел А. Левое поддерево имеет корень В, а правое поддерево - корень С. Они соединяются соответствующими ветвями, исходящими из А. Отсутствие ветви означает пустое поддерево. Например, у поддерева с корнем С нет левого поддерева, оно пусто. Пусто и правое поддерево с корнем Е. Бинарные поддеревья с корнями D, G, H и I имеют пустые левые и правые поддеревья. Узел, имеющий пустые правое и левое поддеревья, называется листом. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правое и левое поддеревья, то дерево поиска называется строго бинарным.
Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку.
Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева.
1.2 Действия с бинарными деревьями поиска
Рассматривая действия над деревьями, можно сказать, что для построения дерева необходимо формировать узлы, и, определив предварительно место включения, включать их в дерево поиска. Количество узлов определяется необходимостью. Алгоритмвключения должен быть известен и постоянен[2]. Узлы дерева могут быть использованы для хранения какой-либо информации.
Далее необходимо осуществлять поиск заданного узла в дереве. Это можно организовать, например, последовательно обходя узлы дерева, причем каждый узел должен быть просмотрен только один раз.
Может возникнуть задача и уничтожения дерева в тот момент, когда необходимость в нем (в информации, записанной в его элементах) отпадает. В ряде случаев может потребоваться уничтожение поддерева.
Для того, чтобы совокупность узлов образовала дерево поиска, необходимо каким-то образом формировать и использовать связи узлов со своими предками и потомками. Все это очень напоминает действия над элементами списка[6].
1.3 Вырожденные деревья
При работе с двоичными деревьями поиска возможен случай, когда дерево поиска по сути примет вид линейного связанного списка (например, если элементы подавались на вход в порядке возрастания), в данном случае бинарное дерево поиска называется вырожденным[3]. В таком случае поиск элемента в дереве будет занимать линейное время. Одним из способов предотвращения подобной ситуации является балансировка дерева по мере добавления элементов.
2. Описание задачи и исходных данных
2.1 Постановка задачи
В курсовом проекте поставленной задачей является разработать справочно-информационную (Windows-приложение) систему на языке программирования C# выполняющее следующие функции: чтение из текстового файла информации об объектах класса согласно варианту (таблица 2.1). Количество записей не менее 50. Предусмотреть наличие в файле не корректных записей, которые в процессе работы программы не будут обрабатываться. Использовать регулярные выражения (предусмотреть проверку по возможности всех полей);
вывод исходных данных в виде таблицы;
визуализация хеш-таблицы или бинарного дерева;
поиск информации по заданному ключу или способу обхода;
редактирование исходных данных (вставка, удаление, замена) с внесением соответствующих изменений в хеш-таблицу или бинарное дерево поиска. Использовать регулярные выражения;
вывод справочной информации о программном продукте и об авторе;
демонстрация перегруженных операторов;
поиск максимального объекта.
2.2 Описание исходных данных
Исходными данными задачи являются: название предметной области, а точнее название класса и его основные поля указаны в таблице 2.1, которое выбирается согласно варианту выданному преподавателем;
текстовый файл с информацией об объектах класса согласно варианту. Количество записей не менее 50. Предусмотреть наличие в файле не корректных записей, которые в процессе работы программы не будут обрабатываться;
бинарное дерево поиска, ключ и способ обхода дерева указан в таблице 2.2.
Таблица 2.1- Описание класса
№ варианта Название класса Поля
14 Спортсмен ФИО, возраст, количество побед, вид спорта
Таблица 2.2 - Способ обхода бинарного дерева
№ варианта Ключ Способ обхода бинарного дерева Обход производить с помощью
14 ФИО Обход в глубину - сверху вниз (префиксный обход) Стека
На основе указанных исходных данных требуется выполнить следующее: создать класс согласно варианту. Класс должен содержать следующие элементы: описание полей класса (выделенное жирным курсивов поле оформить как перечисление);
конструкторы с параметрами и по умолчанию, а также необходимые свойства и методы;
перегрузку одного из бинарных операторов (указать точно какой выбран самостоятельно бинарный оператор и что реализует);
перегрузку одного из операторов отношения (указать точно какой выбран самостоятельно оператор отношения и что реализует);
перегрузку префиксного и постфиксного инкремента (указать назначение инкремента);
перегрузку операторов > (указать назначение операторов);
создание массива из объектов вашего класса;
функцию, определяющую максимальный объект (указать по какому признаку выбирается максимальный объект). Для сравнения использовать перегруженный оператор отношения;
предусмотреть обработку и инициализацию исключительных ситуаций;
Класс должен реализовывать интерфейс ICOMPARABLE;
разработать интерфейс Windows-приложения автоматизированной системы. Помимо самостоятельно выбранных элементов управления, обязательно могут присутствовать следующие элементы управления: MENUSTRIP, CONTEXTMENUSTRIP, Button, TEXTBOX,DATAGRIDVIEW, TEXTBOX, TOOLTIP, Panel, Label, COMBOBOX, OPENFILEDIALOG, SAVEFILEDIALOG, PICTUREBOX, CHECKBOX, REDIOBUTTON.
2.3 Анализ поставленной задачи
Обход в глубину производится рекурсивно либо с использованием стека. В обоих случаях можно обходить узлы дерева в различной последовательности[4]. Обход начинается от корня. Выделяют три наиболее важных порядка обхода в глубину: префиксный (прямой) обход - сначала обрабатывается текущий узел, затем левое и правое поддеревья;
инфиксный (симметричный) обход - сначала обрабатывается левое поддерево текущего узла, затем корень, затем правое поддерево;
постфиксный (обратный) обход - сначала обрабатываются левое и правое поддеревья текущего узла, затем сам узел.
Рисунок 2.1 - Бинарное дерево поиска
Исходя из рисунка 2.1 можно сделать следующие выводы: префиксный обход: A, B, D, H, E, C, F, I, J, G;
инфиксный обход: D, H, B, E, A, I, F, J, C, G;
постфиксный обход: H, D, E, B, I, J, F, G, C, A.
Основным из достоинств постфиксного обхода является - нахождение минимального элемента в бинарном дереве[5]. Так как первым условием данного обхода является: «Обход левого поддерева», а по условию организации бинарного дерева - самый левый элемент является минимальным.
Также к достоинству данного метода можно отнести быструю скорость нахождения элемента, так как будет происходит сравнивание текущего элемента (в бинарном дереве) с элементом который требуется найти и уже по свойствам организации бинарных деревьев следует «дойти» до необходимого элемента[7].
3. Описание разработанного приложения
3.1 Описание методов
В программе содержится множество методов, свойств и классов, каждый из которых выполняет свои функции и обеспечивает корректное выполнение всех действий.
Класс «Node» - узел бинарного дерева, содержит в себе следующие методы: «Add» - метод добавления узла в дерево поиска;
«Find_v1» -метод поиска элемента в бинарном дереве, способом обхода «В глубину - сверху вниз (префиксный обход)», по заданному ключу (введенным пользователем в отдельном окне);
«Shift» -метод для осуществления замены элементов в дереве;
«Delete» -метод удаления элемента из бинарного дерева (описаны все 3 случая удаления элемента из дерева);
«Max» - метод, осуществляющий поиск максимального элемента в дереве по средством операторов отношения и алгоритма организации бинарного дерева;
«Find_v2» -метод, осуществляющий сам «Обход» бинарного дерева способом «В глубину - сверху вниз (префиксный обход)»;
«Download» - метод загрузки бинарного дерева в компоненты «DATAGRIDVIEW»и «TREEVIEW»;
«Save» -метод сохранения (выгрузки) бинарного дерева в файл, по указанному пути пользователем.
Каждому из перечисленных методов выше (кроме Find_v2 и «Download») соответствует свой пункт в меню («MENUSTRIP»): пункт меню «Вставка» - вызывает метод «Add»;
«Поиск - Поиск элемента» - осуществляется выполнение метода «Find_v1»;
«Поиск - Поиск максимального элемента» - происходит выполнение метода «Max»;
«Изменение» - вызов метода «Shift»;
«Удаление» - осуществление метода «Delete».
Класс «Sportsman» - спортсмен (описанная предметная область с ее полями и названием класс), включает в себя основные методы: «COMPARETO» -переопределение метода интерфейса «ICOMPARABLE», который сравнивает текущий экземпляр с другим объектом того же типа и возвращает целое число, которое показывает, расположен ли текущий экземпляр перед, после или на той же позиции в порядке сортировки, что и другой объект;
«Compare_Enum» -метод, который осуществляет проверку наличиявида спорта считанного из файла в виде спорта указанным в перечислении «Enum».
3.2 Описание работы методов
Метод «Add» - вызывается при нажатии пунктов меню «Файл - Открыть» и «Данные - Вставка». Сам алгоритм работы данного метода представлен на рисунке 3.1.
Рисунок 3.1 - Блок схема метода «Add»
Метод «Find_v2» -осуществляет сам обход бинарного дерева (является практически основным методом программы). Данный метод не вызывается посредством меню, а выполняет роль второстепенного метода (подпрограммы) для остальных методов (таких как: «Find_v1», «Shift», «Delete»).
Алгоритм обхода (метод «Find_v2») представлен на рисунке 3.2.
Рисунок 3.2 - Блок схема метода «Find_v2»
Метод «Shift» - метод для осуществления замены элементов в дереве. Сам алгоритм заключается в следующем: произвести поиск элемента с помощью обхода (метода «Find_v2»);
заменить найденных элемент на новый элемент файле;
произвести перестройку дерева с помощью метода «Add», алгоритм которого представлен на рисунке 3.1.
Более подробно алгоритм работы метода «Shift» представлен на рисунке 3.3.
Рисунок 3.3 - Блок схема метода «Shift»
Метод «Max»-осуществляет поиск максимального элемента в дереве по средством операторов отношения. Алгоритм работы представлен на рисунке 3.4.
Рисунок 3.4 - Блок схема метода «Max»
Метод «Delete» - удаляет элемент из бинарного дерева. Удаление элемента в бинарном дереве включает в себя 3 случая[8]: удаляемый элемент не имеет сыновей, в данном случае такой элемент называется листом и заменяется просто на пустое значение. Данный случай представлен на рисунке 3.5 (удаляемый элемент выделен синим цветом).
Рисунок 3.5 - Удаление элемента из бинарного дерева (случай 1) удаляемый элемент имеет либо левого сына, либо правого, в этом случае достаточно поменять удаляемый элемент на его сына, удалить ссылку на сына и очистить память. Более наглядно данный случай можно увидеть на рисунке 3.6.
Рисунок 3.6 - Удаление элемента из бинарного дерева (случай 2) удаляемый элемент имеет и левого и правого сына. В данной ситуации требуется найти максимальный элемент из левого поддерева удаляемого элемента (либо минимальный элемент из правого поддерева удаляемого элемента) и переместить его на место удаляемого узла. Посмотреть этапы удаления элемента (имеющего двух потомков) из бинарного дерева можно на рисунке 3.7.
Рисунок 3.7 - Удаление элемента из бинарного дерева (случай 3)
Алгоритм работы метода «Delete» более подробно можно увидеть на рисунке 3.8, с выполнением всех ситуаций удаления элемента из бинарного дерева.
Рисунок 3.8 - Блок схема метода «Delete»
Метод «Find_v1»- метод поиска элемента в бинарном дереве, способом обхода «В глубину - сверху вниз (префиксный обход)», по заданному ключу. При использовании данному метода автоматически происходит запуск метода «Find_v2» - Обход (рисунок 3.2), в которой происходит поиск данному элемента и возвращает его обратно в «Find_v1» где происходят второстепенные действия (выделение найденного элемента в таблицу и дереве). Блок схема метода «Find_v1» представлена на рисунке 3.9.
Рисунок 3.9 - Блок схема метода «Find_v1»
Оставшиеся методы «Download» и «Save» - аналогичны методу «Find_v2», то есть такой же алгоритм, но вместо «Процессов» выполняемых после удовлетворения «Решения» происходит «Загрузка» (метод «Download») бинарного дерева в соответствующие компоненты справочно- информационной системы или «Выгрузка» (метод «Save») бинарного дерева в файл.
3.3 Структура программного продукта
Программа состоит из двух классов: класс «Node» - узел бинарного дерева, элемента класса отображены в таблице 3.1;
класс «Sportsman»- спортсмен (предметная область), элементы описаны в таблице 3.2.
Таблица 3.1 - Элементы класса «Node»
Имя Вид элемента Тип Спецификатор Описание
1 2 3 4 5
Value Поле T:ICOMPARABLE Public Содержимое узла бинарного дерева
Left Поле Node Private Ссылка на левого сына
Right Поле Node Private Ссылка на правого сына
Parent Поле Node Private Ссылка на отца
Node (T Value) Конструктор - public Инициализация поля «Value»
Add (T Value) Метод Void Public Добавлениеузлавбинарноедерево
Find_v1 (string Search) Метод Void Public Поиск элемента в бинарном дереве
Shift (string Search, string New) Метод Void Public Замена элемента в бинарном дереве
Delete (string Search) Метод Void Public Удаление элемента из бинарного дерева
Max (Node Data) Метод Node Public Поиск макс. элемента в дереве
Download (TREEVIEW Tree,DATAGRIDVIEW Table) Метод Void Public Загрузка бинарного дерева в «Таблицу» и «Дерево»
Save (string Path) Метод Void Public Сохранение бинарного дерева в файл
Find_v2 (string Search) Метод Node Public Обход бинарного дерева
Таблица 3.2 - Элементы класса «Sportsman»
Имя Вид элемента Тип Спецификатор Описание
1 2 3 4 5
FIO Поле string Private ФИО age Поле int Private Возраст wins Поле int Private Колво побед view Перечисление Enum Private Вид спорта
Sportsman ( string FIO, int age, int wins, string view) Конструктор - Public Инициализация полей: FIO, age, wins,view
4. Описание интерфейса
Интерфейс - совокупность возможностей, способов и методов взаимодействия двух систем (любых, а не обязательно являющиеся вычислительными или информационными), устройств или программ для обмена информацией между ними, определенная их характеристиками, характеристиками соединения, сигналов обмена и т. п. В случае, если одна из взаимодействующих систем - человек, чаще говорят лишь о второй системе, то есть об интерфейсе той системы, с которой человек взаимодействует[10].
Первый запуск программы вызывает следующее окно, в котором доступны лишь 2 пункта меню (и 3 пункта подменю), данное окно изображено на рисунке 4.1.
Рисунок 4.1 - Интерфейс справочно-информационной системы при первом запуске
Как видно по рисунку первоначально доступны лишь пункты меню «Файл» и «О программе», и каждой пункт меню содержит свои подпункты, которые изображены на рисунке 4.2.
Рисунок 4.2 - Первоначальные подпункты меню пунктов «Файл» и «О программе»
При первом запуске, в программном продукте возможны только следующие функции: «Файл - Открыть» - позволяет открыть файл *тхтформата для организации бинарного дерева и осуществления с данной информацией необходимых действий (таких как поиск, удаление и т.д.);
«О программе - Об авторе» - открывает окно, содержащее информацию об авторе программного продукта. Данное окно изображено на рисунке 4.3;
Рисунок 4.3 - Окно появляющееся при нажатии пункта меню «О программе - Об авторе»
«О программе - Справка» - при нажатии данного пункта появляется окно, которое содержит информацию по работе с данной справочно-информационной системой (рисунок 4.4).
Рисунок 4.4 - «О программе - Справка»
После открытия файла (для начало работы с информацией) «Файл - Открыть» интерфейс принимает следующую новую форму (пункты меню, расширение столбов таблицы, загрузка информации в программу и т.д.). Данное окно изображено на рисунке 4.5.
Рисунок 4.5 - Интерфейс программы после открытия файла
Если при считывании файла (информации в справочно-информационную систему) были обнаружены некорректные записи, то произойдет вызов окна, на котором изображено количество данных некорректных записей (рисунок 4.6).
Рисунок 4.6 - Окно отображающее количество некорректных записей
Рисунок 4.7 - Пункты меню после открытия файла
Становятся доступны следующие пункты меню (рисунок 4.7): «Файл - Сохранить» - сохранить в текущий открытый файл все бинарное дерево, со всеми изменениями;
«Файл - Сохранить как» - сохранить бинарное дерево со всеми изменениями в новый файл (указание пути сохранения файла предоставляется пользователю);
4.1 Описание функций редактирования исходных данных
«Данные - Вид»- позволяет изменить вид отображения информацию. Доступны 2 вида: «Таблица» (по умолчанию) и «Дерево» - визуализация информации в виде дереве (рисунок 4.8);
Рисунок 4.8 - Отображение информации в виде «Дерева»
«Данные - Вставка» - дает возможность пользователю добавить в бинарное дерево элемент. Как это происходит изображено на рисунке 4.9;
Рисунок 4.9 - Окно «Вставка»
«Данные - Поиск» - позволяет произвести поиск элемента по ключу (рисунок4.10), либо найти максимальный элемент в бинарном дереве (рисунок 4.11). После выполнения поиска (любым из предложенных) в «Таблице» (рисунок 4.12) и «Дереве» (рисунок 4.13) произойдет выделение найденных элементов;
Рисунок 4.12 - «Данные - Вид - Таблица» после выполнения метода «Данные - Поиск - Поиск элемента»
Рисунок 4.13 - «Данные - Вид - Дерево» после выполнения метода «Данные - Поиск - Поиск максимального элемента»
«Данные - Изменение» - позволяет изменить уже существующие элементы в бинарном дереве на указанный (в отдельном окне) новый элемент. При нажатии данного пункта меню, произойдет вызов нового окна «Изменение», в котором необходимо ввести «Старое значение» и «Новое значение», данное окно представлено на рисунке 4.15;
Рисунок 4.14 - Окно «Изменение»
«Данные - Удаление» - дает возможность удалить элемент из бинарного дерева. Работа с данным пунктом изображена на рисунке 4.16;
Рисунок 4.15 - Окно «Удаление»
При работе с такими пунктами меню как: «Данные - Вставка», «Данные - Поиск - Поиск элемента», «Данные - Изменение», «Данные - Удаление» предусмотрена система «Сохранение информации», то есть если в любом из окон (пунктов меню перечисленных выше) присутствует какая- либо информация, то будет сработана данная система и появится окно (рисунок 4.17) с запросом «В текстовом поле обнаружена информация, вы уверены что хотите выйти?» с возможностью ответа «Да» или «Нет». При нажатии на кнопку «Да» - произойдет выход из текущего окна без сохранения информации, при нажатии на кнопку «Нет» - произойдет возврат обратно в текущее окно.
Рисунок 4.16- Запрос о сохранение текущей информации
4.2 Работа с файлом
Если при работе со справочно-информационной системой (с открытым файлом) попытаться выполнить пункт «Файл - Открыть» (то есть открыть новый файл) или просто при нажатии на кнопку «Закрыть» (выход из программы), произойдет автоматический запуск окна (рисунок 4.18) с запросом «Сохранить информацию?», если будет нажата кнопка «Да» - произойдет сохранение бинарного дерева в текущий файл, кнопка «Нет» - означает закрыть программу без сохранения информации, то есть очистка текущей сессии (рисунок 4.19), кнопка «Отмена» - вернуться обратно в программу без выполнения каких либо действий.
Рисунок 4.17 - Окно с запросом о сохранении текущей информации
Рисунок 4.18 - Окно, сообщающее, что данная сессия обнулена
Вывод
В ходе работы были изучены теоретические сведения и закреплены знания, полученные ранее при изучении дисциплины «Конструирование программ и языки программирования». А так же были практически применены полученные знания при выполнении данной работы.
Созданная курсовая работа - отличное решение для организаций, которые в своей профессиональной среде сталкивается с большим количеством информации.
Программа была разработана на языке программирования C#, с организацией удобного пользовательского интерфейса.
В процессе выполнения курсового проекта были решены следующие задачи: изучена организация бинарных деревьев, их свойств;
реализовано бинарное дерево на языке программирования C#;
создано полноценное приложение (со всеми функциями) по работе с информацией, организованной в виде бинарного дерева и осуществления визуализации данной информации.
К достоинствам программного продукта можно отнести: возможность выполнения операций таких как: поиск (по ключу и максимального элемента), удаление данных, чтение информации из файла в бинарное дерево, сохранение бинарного дерева в файл, отображение информации в двух видах («Таблица» и «Дерево»), изменение уже имеющейся информации, добавление данных уже в сформированное бинарное дерево;
удобство интерфейса;
простота и надежность.
Результатом выполнения курсового проекта является сформированное «Бинарное дерево» которое можно отобразить в виде «Таблицы» и «Дерева», включающая в себя большое количество методов, таких как: «Find_v1», «Add», «Shift», «Delete», «Find_v2», «Save» и так далее.
Удобный пользовательский интерфейс бинарного дерева, а так же его простота - обеспечит легкое и быстрое получение нужной информации об интересующих пользователя вопросах.При выполнении поисказапрошенной информации, разработанный программный продукт выдаст всю найденную по запросу пользователя информацию без потерь и без показа лишней информации, что позволит пользователю сократить затраты времени на поиск необходимой информации.
Также данный программный продукт, со временем использования, можно будет оптимизировать путем: обновления алгоритма поиска (обхода бинарного дерева), улучшением функций редактирования исходных данных (вставка, удаления, замена).
Список литературы
бинарный дерево листинг программа
1. Левитин А.В. Алгоритмы: введение в разработку и анализ. - Москва: Издательский дом Вильямс, 2006. - 65 с.
2. Ахо А.В. Структуры данных и алгоритмы /Д.Д. Хопкрофт, Д.Д. Ульман. - Издательский дом Вильямс, 2000. - 92 с.
3. Джозеф А. C# 5.0. Справочник. Полное описание языка. - Издательский дом Вильямс, 2013. - 1008 с.
4. Скит Д. C#: программирование для профессионалов. - Издательский дом Вильямс, 2011. - 544 с.
5. CSHARP [Электронный ресурс]. - Режим доступа: . - Дата доступа: 20.05.2014.
6. Нейгел К. VISUALC#: полный курс. - Издательство «Диалектика», 2010. - 236 с.
7. Деревья выражений [Электронный ресурс]. - Режим доступа: . - Дата доступа: 22.05.2014.
8. Павловская Т.А. C#. Программирование на языке высокого уровня: учебник для вузов. - СПБ.: Питер, 2007. - 432 с.