Программа, выполняющая построение бинарного дерева поиска по исходным данным

Программа, выполняющая построение бинарного дерева поиска по исходным данным

Содержание

Введение

. Использование бинарных деревьев для поиска данных

.1Бинарное дерево

1.2Способы обхода бинарного дерева

.3Средства языка С# для работы с бинарными деревьями

2. Алгоритмический анализ задачи

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

.2 Исходные данные

.3 Графические схемы алгоритмов работы с бинарным деревом

. Описание разработанного приложения

.1 Структура программного комплекса

.2 Инструкция пользователя

.3 Описание результатов

Заключение

Список использованных источников

Введение

В последнее время информационные технологии развиваются на более высоком уровне, чем раньше. Если мы говорим о ИТ, мы не можем не упомянуть о базах данных, развитие которых также не стоит на месте. Появление баз данных тридцать лет назад, очень облегчило работу многим предприятиям, работающим с большим количеством информации. Конечно, с тех пор произошли значительные изменения и в поисковых алгоритмах, и в техническом оснащении. Но, не смотря на все эти изменения, проблема поиска данных по сходству остается актуальной и теперь.

Язык С# - это очередная ступень бесконечной эволюции языков программирования. Его создание вызвано процессом усовершенствования и адаптации, который определял разработку компьютерных языков в течение последних лет. Подобно всем успешным языкам, которые увидели свет раньше, С# опирается на прошлые достижения постоянно развивающегося искусства программирования.

В языке С# (созданном компанией Microsoft для поддержки среды .NET Framework) проверенные временем средства усовершенствованы с помощью самых современных технологий. С# предоставляет очень удобный и эффективный способ написания программ для современной среды вычислительной обработки данных, которая включает операционную систему Windows, Internet, компоненты и пр.

В курсовой работе рассматривается один из методов поиска, а именно бинарные деревья. В курсовой работе нужно разработать программу на С#, которая будет заниматься построением бинарного дерева для исходных данных, поиском информации о товаре в бинарном дереве и редактирование исходных данных.

1. Использование бинарных деревьев для поиска данных

.1Бинарное дерево

Бинарное дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый - корнем дерева, и, возможно, другие элементы. Эти элементы делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Такие подмножества называются левым и правым поддеревьями исходного дерева. Каждый элемент бинарного дерева называется узлом. Будем предполагать, что каждый узел двоичного дерева имеет идентифицирующий его ключ. На рис.1.1.1 приведен пример бинарного дерева, у которого 9 узлов, A - корень дерева, B - корень левого поддерева, C - корень правого поддерева. Каждый узел двоичного дерева может иметь 0, 1 или 2 поддерева. Так на рис.1.1.1 левое поддерево с корнем C исходного бинарного дерева пусто. [1, стр. 303]

Рисунок 1.1.1 - Бинарное дерево

Если X - корень бинарного дерева и Y - корень его левого или правого поддерева, то говорят, что X - отец Y, а Y - левый или правый сын X. В примере на рис.1.1.1 A - отец для B и C, B - левый сын A, E - отец G, G - его левый сын. Узел, не имеющий сыновей, называется листом. В примере 1.1.1 листья: D, G, H, I. Два узла являются братьями, если они сыновья одного отца (B, C - братья). Глубина бинарного дерева определяется длиной самого длинного пути от корня к листу дерева (на рис.1.1.1 глубина дерева равна 3). Каждый узел бинарного дерева содержит информационное поле, а также два указателя (на левое и правое поддерево). Очевидно, что для доступа к узлам бинарного дерева необходимо задать указатель на его корень.

Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Ознакомившись с концепцией бинарного дерева, можно заметить, что не все деревья позволяют организовать эффективный поиск по ним. Такие деревья называются вырожденными и некоторые из них представлены на рисунке 1.1.2.[1, стр. 312]

Рисунок 1.1.2 - Вырожденное бинарное дерево

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

Описание множеств в виде списков позволяет использовать для множеств целевое утверждение, принадлежит определенное ранее для списков.

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

Представление множества бинарным деревом позволяет добиться лучшего результата. На рис. 1.1.3 приведен пример упорядоченного бинарного дерева.

Рисунок 1.1.3 - Упорядоченное бинарное дерево

Упорядочение приводит не к единственному варианту представления множества с помощью дерева. Будем называть линейным представление такого вида, как на рис. 1.1.4, и сбалансированным - такое, как на рис. 1.1.3.[1,308]

Рисунок 1.1.4 - Линейное представление

1.2 Способы обхода бинарного дерева

Процедуру перемещения по дереву называют обходом (traversal). Существуют четыре основных алгоритма обхода - обходом в ширину (pre-order), симметричным обходом (in-order), обходом в глубину (post-order) и обходом по уровням (level-order). Последний алгоритм - обход по уровням - наиболее прост для визуального представления, но наиболее сложен для кодирования. Этот алгоритм предполагает посещение каждого из узлов, начиная с корневого, и просмотр узлов сверху вниз, уровень за уровнем. На каждом уровне мы посещаем узлы слева направо. Таким образом, мы посещаем корневой узел, левый дочерний узел корневого узла, правый дочерний узел корневого узла, левый дочерний узел левого дочернего узла корневого узла, правый дочерний узел левого дочернего узла корневого узла и т.д.

При обходе в ширину вначале мы посещаем корневой узел, затем, используя алгоритм обхода в ширину, выполняем обход левого дочернего дерева, а затем таким же образом выполняем обход правого дочернего дерева. При обходе в глубину вначале выполняется обход в левого дочернего дерева с применением алгоритма обхода в глубину, затем таким же образом выполняется обход правого дочернего дерева, а затем посещается корневой узел.[1,312]

Симметричный обход дерева

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

В качестве примера рассмотрим следующее дерево представленное на рисунке 1.2.1:

·обход дерева в ширину: A, B, C, D, E, F, G, H, I, J

·симметричный обход дерева: D, H, B, E, A, I, F, J, C, G

·обход дерева в глубину: A, B, D, H, E, C, F, I, J, G

Рисунок 1.2.1-Бинарное дерево

1.3Средства языка С# для работы с бинарными деревьями

Язык C# предоставляет большие возможности для работы с бинарными деревьями. Фактически бинарное дерево представляет собой структуру, состоящую из множества узлов связанных ссылками. В каждый узел дерева имеет поля, содержащие ссылки на левый и правый дочерний элемент, а так же на родительский элемент данного узла. Элемент TreeView предназначен для иерахического отображения дерева.Узлы в TreeView это экземпляры класса TreeNode.Свойства TreeView

CheckBoxes -true,если рядом с узлами отображаются значки для выбора позиции

ImageList-отображает картинки рядом с узлами

SelectedNode-выбранный в текущий момент узел

Nodes -коллекция узлов TreeNode

Эта коллекция содержит следующие методы:

Add-добавление узла

Add(string text)-параметр text-строка,которая будет отражаться рядом с узлом

Add(TreeNode node)-добавляет узел node

Clear()-удаляет всех узлов из коллекции

Remove(TreeNode node)-удаляет узел node из коллекции

RemoveAt(int index)-удаляет узел с индексом index из коллекции

Insert(int index,TreeNode node)-вставляет узел node на место определенное индексом index

Свойства TreeNode:

FirstNode-указывает первый узел

FullPath-указывает путь

NextNode-указывает следующий брат-узла

PrevNode-предыдущий узел-брат

Parent-содержит ссылку на узел-родитель или null, если узел корневой

ImageIndex-задает номер изображения

Text-текст отображаемый в TreeView

SelectedImageIndex-номер изображения для использования при выборе узла.[2,350]

программа бинарный дерево

2. Алгоритмический анализ задачи

Разработать Windows-приложение на языке С#, выполняющее следующие действия:

Чтение из текстового файла информации о товаре на складе (каждая строка файла должна содержать код товара, наименование, цену, количество на складе);

Вывод исходных данных в виде таблицы;

Построение для исходных данных бинарного дерева (ключ и способ обхода дерева указан в таблице 2.2.1);

Визуализация бинарного дерева;

Редактирование исходных данных (вставка, удаление, замена) с внесением соответствующих изменений в бинарное дерево;

Поиск информации о товарах по заданному ключу с использованием бинарного дерева.

.2 Исходные данные

Исходными данными к программе является текстовый файл base.txt, содержащий множество записей информации о товарах. Каждая строка файла содержит наименование товара, код товара, цена товара и количество товара на складе.

Файл находится в директории WindowsFormsApplication1\bin\Debug\

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

Таблица 2.2.1 - Исходные данные

КлючСпособ обхода бинарного дерева Код товараСимметричный обход

2.3 Графические схемы алгоритмов работы с бинарным деревом

Метод public void buildTree() предназначен для построения бинарного дерева. Суть алгоритма: пока не пуст список всех элементов будет выполняться цикл, в котором для каждого элемента списка будет найдено место, удовлетворяющее условию упорядоченности дерева, после чего элемент будет удален из списка всех элементов и добавлен в дерево. Графическая схема алгоритма представлена на рисунке 2.3.1

Рисунок 2.3.1-Графическая схема алгоритма построения бинарного дерева

Метод public void replace(derevo el, int key)предназначен для замены элемента бинарного дерева по заданному ключу. Суть алгоритма: сначала из бинарного дерева удаляется заменяемый элемент, после чего в бинарное дерево добавляется элемент, на который должна быть произведена замена. Графическая схема алгоритма представлена на рисунке 2.3.2

Рисунок 2.3.2-Графическая схема алгоритма замены элемента в бинарном дереве

Метод public derevo search(int key, ref bool flag, derevo v)предназначен для поиска элемента бинарного дерева по заданному ключу. Суть алгоритма: вначале выполняется обход левого дочернего дерева корневого узла с применением алгоритма симметричного обхода, а затем симметричный обход правого дочернего дерева. Графическая схема алгоритма представлена на рисунке 2.3.3

Метод public derevo deleteItem(derevo k, int key)предназначен для удаления элемента бинарного дерева по заданному ключу.Для удаления нужного элемента из дерева сначала производится его поиск.Если элемент найден, то его удаление производится путем удаления из дерева всех ссылок на него и вставки на пустое место в дереве другого подходящего элемента.Графическая схема алгоритма представлена на рисунке 2.3.4

Рисунок 2.3.3-Графическая схема алгоритма поиска элемента бинарного дерева

Рисунок 2.3.4-Графическая схема алгоритма удаления элемента из бинарного дерева

3. Описание разработанного приложения

.1 Структура программного комплекса

Программа состоит из 2 классов: Binarnoe_derevo, derevo. Втаблице 3.1.1описаны элементы класса Binarnoe_derevo,а в таблице 3.1.2 1описаны элементы класса derevo.

Таблица 3.1.1 - Элементы класса Binarnoe_derevo.

ИмяВид элементаТипСпецификаторОписаниеkПолеderevoPublicОбъект представляющий бинарное деревоmasssivПолеArrayListPublic staticВсе элементы дереваBinarnoe_derevo(string[s])Конструктор-PublicОпределение параметровbuildTree()МетодvoidPublicПостроение бинарного дереваtreeToDatagrid(derevo vetv, ref int i, Form1 f)МетодvoidPublicВывод дерева в таблицуsearch(int key, ref bool flag, derevo v)МетодderevoPublicПоиск элемента бинарного дереваreplace(derevo el, int key)МетодvoidPublicЗамена элемента бинарного дереваdeleteItem(derevo k, int key)МетодderevoPublicУдаление элемента бинарного дереваtreeToTreeView(Form1 f, derevo vetv)МетодvoidPublicВизуализация бинарного дереваadd(derevo el, bool flag, derevo prev)МетодvoidPublicДобавление элемента бинарного дерева

Таблица 3.1.2 - Элементы класса Element.

ИмяВид элементаТипСпецификаторОписаниеlevaia_verchinaПолеderevoPrivateЛевый элементpravaia_verchinaПолеderevoPrivateПравый элементverchinaПолеderevoPrivateРодительский элементkodПолеIntPrivateКод продуктаnameПолеStringPrivateНаименование продуктаchenaПолеIntPrivateЦена продуктаkolictectvoПолеintPrivateКол-во оставшегося продуктаNameсвойствоstringPublicВозвращает наименование продуктаChenaсвойствоintPublicВозвращает ценуKolichectvoсвойствоintPublicВозвращает кол-воKodсвойствоintPublicВозвращает кодLeftсвойствоderevoPublicВозвращает левый элементRightсвойствоderevoPublicВозвращает правый элементVerhсвойствоderevoPublicВозвращает родительский элементpublic derevo (derevo parent, int code, string naimenovanie, int price, int count)Конструктор с параметрами-Public-public derevo()Конструктор без параметров-Public-

.2 Инструкция пользователя

Данная программа позволяет обработать базу данных с использованием хеширования. Для запуска программы следует запустить файл WindowsFormsApplication1\bin\Debug\WindowsFormsApplication1.exe или WindowsFormsApplication1.sln (если установлен Microsoft Visual C#2010) и в запустившейся программе нажать функциональную клавишу F5.

Затем следовать указаниям на экране (рисунок 3.2.1.)

Пункт меню «Меню» содержит:

«Новый»

«Чтение из файла»

«Сохранение в файл»

«Выход» (Выход из программы)

На рисунке 3.2.2 изображено меню при выборе пункта «Новый» (Создание новой БД)

На рисунке 3.2.3 изображено меню при выборе пункта «Чтение из файла» (диалог для выбора открываемого файла)

Рисунок 3.2.1 - Главное меню программы

Рисунок 3.2.2-создание новой записи

Рисунок 3.2.3-чтение из файла

На рисунке 3.2.4 изображено меню при выборе пункта «Сохранение в файл» (Диалог для выбора местоположения сохраняемого файла)

Рисунок 3.2.4-сохранение данных в файл

Пункт меню «Редактирование» содержит:

«Вставка»

«Удаление»

«Замена»

«Поиск»

На рисунке 3.2.5 изображено меню при выборе пункта «Вставка» (позволяет добавить элемент)

Рисунок 3.2.5-добавление элемента

На рисунке 3.2.6 изображено меню при выборе пункта «Удаление» (позволяет удалить элемент)

Рисунок 3.2.6-удаление элемента

На рисунке 3.2.7 изображено меню при выборе пункта «Замена» (позволяет заменить элемент).

Рисунок 3.2.7-замена элемента

На рисунке 3.2.8 изображено меню при выборе пункта «Поиск» (позволяет найти данные с помощью бинарного дерева).

Рисунок 3.2.8-Поиск элемента

Пункт меню «Справка» выводит краткие теоретические сведения .

Пункт меню «Об авторе» выводит информацию о создателе программы.

Пункт меню «Инструкция пользователя» выводит информацию о пунктах меню.

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

Для открытия уже существующей базы, можно нажать «Чтение из файла»

Для добавления информации необходимо нажать «Вставить ». Появится новое окно. В нем пользователь должен заполнить все поля и нажать кнопку «Добавить».

При удалении в открытом окне пользователь должен ввести параметр для удаления и нажать кнопку «Удалить».

Для замены, заполняет все поля (вносит данные о товаре, которого хочет изменить данные), а также вводить код товара, который хочет изменить и нужно нажать кнопку «Заменить ».

Для того, чтобы осуществить поиск нужно нажать «Поиск». В поле для ввода пользователь вводит код товара и нажимает кнопку «Поиск». Если данные по введённому коду имеются, то они выводятся в таблицу, иначе выводится соответствующее сообщение.

3.3 Описание результатов

Задача, поставленная в курсовой работе, выполнена. Программа читает записи из текстового файла, строит бинарное дерево, и осуществляет поиск по ключу. Так же программа добавляет, удаляет и заменяет данные о товарах.

При неверном вводе или выборе данных программа выдаёт соответствующее сообщение.

Таким образом, добавление данных о товаре происходит лишь в том случае, когда все поля в окне добавления будут заполнены. Удаление - если будет введен ключ для удаления. Замена произойдёт лишь в том случае, если пользователь заполнит все поля.

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

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

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

Список использованных источников

1.Дж. Бакнелл. Фундаментальные алгоритмы и структуры данных в Delphi - Москва:DiaSoft, 2003. - 557с.

.Фаронов В.В. Программирование на языке C# - СПб.:Питер, 2007. - 240 с.

3.Павловская Т.А. C#. Программирование на языке высокого уровня. Учебник для вузов - СПб.: Питер, 2007. - 432 с.

4.Агуров П.В. - С#. Сборник рецептов. - СПб.: БХВ-Петербург, 2007. - 432 с.

. Седжвик Роберт. - Фундаментальные алгоритмы на С++. Анализ/ Структуры данных/ Сортировка/ Поиск: Пер. с англ./ Роберт Седжвик - К.: Издательство «ДиаСофт», 2001 - 688 с.