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

В последнее время информационные технологии развиваются на более высоком уровне, чем раньше. Появление баз данных тридцать лет назад, очень облегчило работу многим предприятиям, работающим с большим количеством информации. Конечно, с тех пор произошли значительные изменения и в поисковых алгоритмах, и в техническом оснащении. В языке С# (созданном компанией Microsoft для поддержки среды .NET Framework) проверенные временем средства усовершенствованы с помощью самых современных технологий.Бинарное дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый - корнем дерева, и, возможно, другие элементы. Эти элементы делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. На рис.1.1.1 приведен пример бинарного дерева, у которого 9 узлов, A - корень дерева, B - корень левого поддерева, C - корень правого поддерева. Если X - корень бинарного дерева и Y - корень его левого или правого поддерева, то говорят, что X - отец Y, а Y - левый или правый сын X. Много путевое дерево представляет собой коллекцию узлов, организованных так, чтобы все узлы кроме корневого (мы будем называть узел в верхушке дерева корневым, а узел, который не имеет дочерних узлов - листовым, или просто листом) имели только один родительский узел и могли иметь ноль или больше дочерних узлов.Существуют четыре основных алгоритма обхода - обходом в ширину (pre-order), симметричным обходом (in-order), обходом в глубину (post-order) и обходом по уровням (level-order). Таким образом, мы посещаем корневой узел, левый дочерний узел корневого узла, правый дочерний узел корневого узла, левый дочерний узел левого дочернего узла корневого узла, правый дочерний узел левого дочернего узла корневого узла и т.д. При обходе в ширину вначале мы посещаем корневой узел, затем, используя алгоритм обхода в ширину, выполняем обход левого дочернего дерева, а затем таким же образом выполняем обход правого дочернего дерева. При обходе в глубину вначале выполняется обход в левого дочернего дерева с применением алгоритма обхода в глубину, затем таким же образом выполняется обход правого дочернего дерева, а затем посещается корневой узел.[1,312]В каждый узел дерева имеет поля, содержащие ссылки на левый и правый дочерний элемент, а так же на родительский элемент данного узла. Элемент TREEVIEW предназначен для иерахического отображения дерева.Узлы в TREEVIEW это экземпляры класса TREENODE.Свойства TREEVIEW CHECKBOXES-true,если рядом с узлами отображаются значки для выбора позиции Add(string text)-параметр text-строка,которая будет отражаться рядом с узлом Add(TREENODE node)-добавляет узел nodeРазработать Windows-приложение на языке С#, выполняющее следующие действия:-Чтение из текстового файла информации о товаре на складе (каждая строка файла должна содержать код товара, наименование, цену, количество на складе); -Построение для исходных данных бинарного дерева (ключ и способ обхода дерева указан в таблице 2.2.1);Исходными данными к программе является текстовый файл base.txt, содержащий множество записей информации о товарах. Каждая строка файла содержит наименование товара, код товара, цена товара и количество товара на складе.Суть алгоритма: пока не пуст список всех элементов будет выполняться цикл, в котором для каждого элемента списка будет найдено место, удовлетворяющее условию упорядоченности дерева, после чего элемент будет удален из списка всех элементов и добавлен в дерево. Метод public void replace(derevo el, int key)предназначен для замены элемента бинарного дерева по заданному ключу. Суть алгоритма: сначала из бинарного дерева удаляется заменяемый элемент, после чего в бинарное дерево добавляется элемент, на который должна быть произведена замена. Метод public derevo DELETEITEM(derevo k, int key)предназначен для удаления элемента бинарного дерева по заданному ключу.Для удаления нужного элемента из дерева сначала производится его поиск.Если элемент найден, то его удаление производится путем удаления из дерева всех ссылок на него и вставки на пустое место в дереве другого подходящего элемента.Графическая схема алгоритма представлена на рисунке 2.3.4Втаблице 3.1.1описаны элементы класса Binarnoe_derevo,а в таблице 3.1.2 1описаны элементы класса derevo. Имя Вид элемента Тип Спецификатор Описание k Поле derevo Public Объект представляющий бинарное дерево masssiv Поле ARRAYLIST Public static Все элементы дерева BUILDTREE() Метод void Public Построение бинарного дерева TREETODATAGRID(derevo vetv, ref int i, Form1 f) Метод void Public Вывод дерева в таблицу search(int key, ref bool flag, derevo v) Метод derevo Public Поиск элемента бинарного дерева replace(derevo el, int key) Метод void Public Замена элемента бинарного дерева DELETEITEM(derevo k, int key) Метод derevo Public Удаление элемента бинарного дерева TREETOTREEVIEW(Form1 f, derevo vetv) Метод void Public Визуализация бинарного дерева add(derevo el, bool flag, derevo prev) Метод void Public Добавление элемента бинарного дереваПункт

Содержание

Введение

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

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

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

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

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

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

2.2 Исходные данные

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

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

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

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

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

Заключение

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

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

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

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

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